Known algorithms for EDGE CLIQUE COVER are probably optimal

Authors:
  • MCMarek Cygan
    Marek Cygan
  • MPMarcin Pilipczuk
    Marcin Pilipczuk
  • MPMichał Pilipczuk
    Michał Pilipczuk

Abstract
In the EDGE CLIQUE COVER problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on k-element universe. Gramm et al. [JEA 2008] shown a set of simple rules that reduce the number of vertices of G to 2^k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent EDGE CLIQUE COVER instance (G,k) with k = O(log n) and |V(G)| = O(n + m).