Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier · 2006
To cover the edges of a graph with a minimum number of cliques is an NP-complete problem with many applications. The state-of-the-art solving algorithm is a polynomial-time heuristic from the 1970's. We present an improvement of this heuristic. Our main contribution, however, is the development of efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.