License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.61
URN: urn:nbn:de:0030-drops-187148
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18714/
Go to the corresponding LIPIcs Volume Portal

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

Solving Edge Clique Cover Exactly via Synergistic Data Reduction

pdf-format:
LIPIcs-ESA-2023-61.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{hevia_et_al:LIPIcs.ESA.2023.61,
  author =	{Hevia, Anthony and Kallus, Benjamin and McClintic, Summer and Reisner, Samantha and Strash, Darren and Wilson, Johnathan},
  title =	{{Solving Edge Clique Cover Exactly via Synergistic Data Reduction}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{61:1--61:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18714},
  URN =		{urn:nbn:de:0030-drops-187148},
  doi =		{10.4230/LIPIcs.ESA.2023.61},
  annote =	{Keywords: Edge clique cover, Vertex clique cover, Data reduction, Degeneracy}
}

Keywords: Edge clique cover, Vertex clique cover, Data reduction, Degeneracy
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023
Supplementary Material: Software (Source Code): https://github.com/darrenstrash/Redu3ECC

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI