Known Algorithms for Edge Clique Cover are Probably Optimal
- 1 January 2016
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 45 (1) , 67-83
Abstract
In the Edge Clique Cover (ECC) problem, given an undirected graph $G$ and an integer $k$, we ask whether one can choose $k$ cliques in $G$ such that each edge of $G$ is contained in at least one of the chosen cliques. Gramm et al. [ACM J. Exp. Algorithmics, 13 (2008)] have shown a set of simple rules that reduce the number of vertices of $G$ to $2^k$ while preserving the answer to the instance at hand, that is, they have shown a kernel for the problem with at most $2^k$ vertices. No algorithm is known with significantly better running time bound than a brute-force search on this kernel. 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 instance of $3$-CNF-SAT with $n$ variables and $m$ clauses to an equivalent ECC instance $(G,k)$ with $k = \mathcal{O}(\log n)$ and $|V(G)| = \mathcal{O}(n + m)$. Consequently, there is no $2^{2^{o(k)}}{\rm poly}(n)$ time algorithm for the ECC problem, unless the Exponential Time...
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Strong computational lower bounds via parameterized complexityJournal of Computer and System Sciences, 2006
- Efficiently covering complex networks with cliques of similar verticesTheoretical Computer Science, 2006
- Bipartite structure of all complex networksInformation Processing Letters, 2004
- An Algorithm for a Letter-Based Representation of All-Pairwise ComparisonsJournal of Computational and Graphical Statistics, 2004
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Linear time algorithms on circular-arc graphsInformation Processing Letters, 1991
- Applications of edge coverings by cliquesDiscrete Applied Mathematics, 1985
- On a clique covering problem of orlinDiscrete Mathematics, 1982
- Covering edges by cliques with regard to keyword conflicts and intersection graphsCommunications of the ACM, 1978