Document Open Access Logo

Solving Edge Clique Cover Exactly via Synergistic Data Reduction

Authors Anthony Hevia , Benjamin Kallus, Summer McClintic , Samantha Reisner, Darren Strash , Johnathan Wilson

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.61.pdf
  • Filesize: 1.15 MB
  • 19 pages

Document Identifiers

Author Details

Anthony Hevia
  • Hamilton College, Clinton, NY, USA
Benjamin Kallus
  • Dartmouth College, Hanover, NH, USA
Summer McClintic
  • Hamilton College, Clinton, NY, USA
Samantha Reisner
  • Hamilton College, Clinton, NY, USA
Darren Strash
  • Hamilton College, Clinton, NY, USA
Johnathan Wilson
  • Hamilton College, Clinton, NY, USA

Acknowledgements

We thank the anonymous reviewers for their insightful feedback, David Swartz from Hamilton College for technical support, and Adam Chrisman, Caitlin Matwijec-Walda, and Jon Matwijec-Walda for a cozy space to work at The Copper Easel and Superofficial in Rome, NY.

Cite AsGet BibTex

Anthony Hevia, Benjamin Kallus, Summer McClintic, Samantha Reisner, Darren Strash, and Johnathan Wilson. Solving Edge Clique Cover Exactly via Synergistic Data Reduction. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.61

Abstract

The edge clique cover (ECC) problem - where the goal is to find a minimum cardinality set of cliques that cover all the edges of a graph - is a classic NP-hard problem that has received much attention from both the theoretical and experimental algorithms communities. While small sparse graphs can be solved exactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], larger instances can currently only be solved inexactly using heuristics with unknown overall solution quality. We revisit computing minimum ECCs exactly in practice by combining data reduction for both the ECC and vertex clique cover (VCC) problems. We do so by modifying the polynomial-time reduction of Kou et al. [Commun. ACM 1978] to transform a reduced ECC instance to a VCC instance; alternatively, we show it is possible to "lift" some VCC reductions to the ECC problem. Our experiments show that combining data reduction for both problems (which we call synergistic data reduction) enables finding exact minimum ECCs orders of magnitude faster than the technique of Gramm et al., and allows solving large sparse graphs on up to millions of vertices and edges that have never before been solved. With these new exact solutions, we evaluate the quality of recent heuristic algorithms on large instances for the first time. The most recent of these, EO-ECC by Abdullah et al. [ICCS 2022], solves 8 of the 27 instances for which we have exact solutions. It is our hope that our strategy rallies researchers to seek improved algorithms for the ECC problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Packing and covering problems
Keywords
  • Edge clique cover
  • Vertex clique cover
  • Data reduction
  • Degeneracy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Wali M. Abdullah and Shahadat Hossain. A sparse matrix approach for covering large complex networks by cliques. In Derek Groen, Clélia de Mulatier, Maciej Paszynski, Valeria V. Krzhizhanovskaya, Jack J. Dongarra, and Peter M. A. Sloot, editors, Computational Science - ICCS 2022 - 22nd International Conference, London, UK, June 21-23, 2022, Proceedings, Part III, volume 13352 of Lecture Notes in Computer Science, pages 505-517. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-08757-8_43.
  2. Wali M. Abdullah, Shahadat Hossain, and Muhammad. A. Khan. Covering large complex networks by cliques - A sparse matrix approach. In D. Marc Kilgour, Herb Kunze, Roman Makarov, Roderick Melnik, and Xu Wang, editors, Recent Developments in Mathematical, Statistical and Computational Sciences, pages 117-127. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-63591-6_11.
  3. Faisal N. Abu-Khzam, Michael R. Fellows, Michael A. Langston, and W. Henry Suters. Crown structures for vertex cover kernelization. Theor. Comput. Syst., 41(3):411-430, 2007. URL: https://doi.org/10.1007/s00224-007-1328-0.
  4. Tokuya Akiba and Yoichi Iwata. Branch-and-reduce exponential/FPT algorithms in practice: A case study of vertex cover. Theor. Comput. Sci., 609, Part 1:211-225, 2016. URL: https://doi.org/10.1016/j.tcs.2015.09.023.
  5. Alper Atamtürk, George L. Nemhauser, and Martin W.P. Savelsbergh. Conflict graphs in solving integer programming problems. European Journal of Operational Research, 121(1):40-55, 2000. URL: https://doi.org/10.1016/S0377-2217(99)00015-6.
  6. Mathieu Blanchette, Ethan Kim, and Adrian Vetta. Clique cover on sparse networks. In 2012 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pages 93-102. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611972924.10.
  7. Thomas Bläsius, Philipp Fischbeck, Lars Gottesbüren, Michael Hamann, Tobias Heuer, Jonas Spinner, Christopher Weyand, and Marcus Wilhelm. A branch-and-bound algorithm for cluster editing. In Christian Schulz and Bora Uçar, editors, 20th International Symposium on Experimental Algorithms (SEA 2022), volume 233 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SEA.2022.13.
  8. Robert C. Brigham and Ronald D. Dutton. On clique covers and independence numbers of graphs. Discrete Mathematics, 44(2):139-144, 1983. URL: https://doi.org/10.1016/0012-365X(83)90054-7.
  9. David Chalupa. Construction of near-optimal vertex clique covering for real-world networks. Computing and Informatics, 34(6):1397-1417, 2015. URL: http://www.cai.sk/ojs/index.php/cai/article/view/1276.
  10. Lijun Chang, Wei Li, and Wenjie Zhang. Computing a near-maximum independent set in linear time by reducing-peeling. Proc. 2017 ACM International Conference on Management of Data (SIGMOD '17), pages 1181-1196, 2017. URL: https://doi.org/10.1145/3035918.3035939.
  11. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210-223, 1985. URL: https://doi.org/10.1137/0214017.
  12. Alessio Conte, Roberto Grossi, and Andrea Marino. Large-scale clique cover of real-world networks. Information and Computation, 270:104464, 2020. URL: https://doi.org/10.1016/j.ic.2019.104464.
  13. Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Magnus Wahlström. Clique cover and graph separation: New incompressibility results. ACM Trans. Comput. Theory, 6(2), May 2014. URL: https://doi.org/10.1145/2594439.
  14. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs in near-optimal time. ACM J. Exp. Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2543629.
  15. Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, and Mathias Weller. What is known about vertex cover kernelization? In Hans-Joachim Böckenhauer, Dennis Komm, and Walter Unger, editors, Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, pages 330-356. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98355-4_19.
  16. Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, and Darren Strash. Engineering kernelization for maximum cut. In Proc. 2020 Symposium on Algorithm Engineering and Experiments (ALENEX), pages 27-41. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976007.3.
  17. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  18. Serge Gaspers and Edward J. Lee. Faster graph coloring in polynomial space. In Yixin Cao and Jianer Chen, editors, Proc. 23rd International Computing and Combinatorics Conference (COCOON 2017), volume 10392 of LNCS, pages 371-383. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-62389-4_31.
  19. Jens Gramm, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. Data reduction and exact algorithms for clique cover. J. Exp. Algorithmics, 13, February 2009. URL: https://doi.org/10.1145/1412228.1412236.
  20. John E. Hopcroft and Richard M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. URL: https://doi.org/10.1137/0202019.
  21. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. Linear-time FPT algorithms via network flow. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1749-1761. SIAM, 2014. URL: https://dl.acm.org/doi/10.5555/2634074.2634201.
  22. Adalat Jabrayilov and Petra Mutzel. New integer linear programming models for the vertex coloring problem. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 640-652. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_47.
  23. Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, pages 85-103. Springer US, Boston, MA, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  24. Mikko Koivisto. An O^*(2ⁿ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 583-590, 2006. URL: https://doi.org/10.1109/FOCS.2006.11.
  25. Lawrence T. Kou, Larry J. Stockmeyer, and C. K. Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM, 21(2):135-139, February 1978. URL: https://doi.org/10.1145/359340.359346.
  26. Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. Finding near-optimal independent sets at scale. Journal of Heuristics, 23(4):207-229, August 2017. URL: https://doi.org/10.1007/s10732-017-9337-x.
  27. Don R. Lick and Arthur T. White. k-degenerate graphs. Canadian Journal of Mathematics, 22(5):1082-1096, 1970. URL: https://doi.org/10.4153/CJM-1970-125-1.
  28. Anuj Mehrotra and Michael A. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8(4):344-354, 1996. URL: https://doi.org/10.1287/ijoc.8.4.344.
  29. George L. Nemhauser and Leslie E. Trotter Jr. Vertex packings: Structural properties and algorithms. Math. Program., 8(1):232-248, 1975. URL: https://doi.org/10.1007/BF01580444.
  30. Darren Strash. On the power of simple reductions for the maximum independent set problem. In Thang N. Dinh and My T. Thai, editors, Computing and Combinatorics (COCOON'16), volume 9797 of LNCS, pages 345-356. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-42634-1_28.
  31. Darren Strash and Louise Thompson. Effective data reduction for the vertex clique cover problem. In Cynthia A. Phillips and Bettina Speckmann, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, VA, USA, January 9-10, 2022, pages 41-53. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977042.4.
  32. Ahammed Ullah. Clique cover of graphs with bounded degeneracy. CoRR, abs/2108.09851, 2021. URL: https://arxiv.org/abs/2108.09851.
  33. Johan M.M. van Rooij and Hans L. Bodlaender. Exact algorithms for dominating set. Discrete Applied Mathematics, 159(17):2147-2164, 2011. URL: https://doi.org/10.1016/j.dam.2011.07.001.
  34. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact