KNOWN ALGORITHMS FOR EDGE CLIQUE COVER ARE PROBABLY OPTIMAL
KNOWN ALGORITHMS FOR EDGE CLIQUE COVER ARE PROBABLY OPTIMAL
复制标题
DOI：
10.1137/130947076
复制
发表时间：
2016-01-01
影响因子：
1.6
通讯作者：
Pilipczuk, Michal
中科院分区：
文献类型：
--
作者：
Cygan, Marek;Pilipczuk, Marcin;Pilipczuk, Michal
在边CLIQUE COVER（ECC）问题中，给定一个无向图G和一个整数k，我们问是否可以在G中选择k个团，使得G的每条边包含在至少一个所选的团中。Gramm等人[ACM J. Exp. 13（2008）]已经给出了一组简单的规则，这些规则将G的顶点数减少到2（k），同时保留手头实例的答案，也就是说，他们已经给出了至多2（k）个顶点的问题的核。没有一个算法比这个内核上的蛮力搜索具有更好的运行时间限制。在本文中，我们证明了Gramm等人的方法本质上是最优的：我们提出了一个多项式时间算法，该算法将具有n个变量和m个子句的3-CNF-SAT的任意实例减少到等价的ECC实例（G，k），其中k = O（log n），垂直条V（G）垂直条= O（n + m）。因此，对于ECC问题没有2（2 o（k））poly（n）时间算法，除非指数时间假设失败。此外，我们的约简还意味着，除非P = NP，否则ECC问题不允许次指数核，即，大小为2（o（k））的核。
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 = O(log n) and vertical bar V (G)vertical bar = O(n + m). Consequently, there is no 2(2o(k)) poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. Moreover, our reduction also implies that, unless P = NP, the ECC problem does not admit a subexponential kernel, i.e., a kernel of size 2(o(k)).