Data reduction and exact algorithms for clique cover
Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier · ACM Journal of Experimental Algorithmics · 2008
To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop 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.