English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The edge clique cover (ECC) problem -- where the goal is to find a minimumcardinality set of cliques that cover all the edges of a graph -- is a classicNP-hard problem that has received much attention from both the theoretical andexperimental algorithms communities. While small sparse graphs can be solvedexactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], largerinstances can currently only be solved inexactly using heuristics with unknownoverall solution quality. We revisit computing minimum ECCs exactly in practiceby combining data reduction for both the ECC \emph{and} vertex clique cover(VCC) problems. We do so by modifying the polynomial-time reduction of Kou etal. [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 theECC problem. Our experiments show that combining data reduction for bothproblems (which we call \emph{synergistic data reduction}) enables findingexact minimum ECCs orders of magnitude faster than the technique of Gramm etal., and allows solving large sparse graphs on up to millions of vertices andedges that have never before been solved. With these new exact solutions, weevaluate the quality of recent heuristic algorithms on large instances for thefirst time. The most recent of these, \textsf{EO-ECC} by Abdullah et al. [ICCS2022], solves 8 of the 27 instances for which we have exact solutions. It isour hope that our strategy rallies researchers to seek improved algorithms forthe ECC problem.

Solving Edge Clique Cover Exactly via Synergistic Data Reduction