The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs
复制标题
随机图中独立集和顶点覆盖的解析复杂度
DOI：
--
复制
发表时间：
2007
影响因子：
1.4
通讯作者：
Ashish Sabharwal
中科院分区：
文献类型：
--
作者：
P. Beame;R. Impagliazzo;Ashish Sabharwal
我们考虑了这样一个问题：一个具有n个顶点和平均度的粗略Δ的图不包含一个大小为k的独立集。对于随机选择的图和n/3的k≤，我们证明了这样的证明几乎必然要求大小为n/Δ6的指数大小。特别地，这意味着对于常数度图，这意味着一个2Ω(N)的下界，并且对于Δ≈n1/6，表明几乎总是没有像n/3那么大的k的短可分解性证明，尽管最大独立集可能小得多，大约是N5/6的大小。我们的结果表明，对于不太密集的图，几乎所有独立集问题的实例都很难解决。此外，它还给出了基于分辨率的搜索算法在Δ/(6lnΔ)的因子内寻找或逼近最大独立集所需时间的无条件指数下界。我们还给出了问题的相对简单的上界，并证明了它们对于穷举回溯算法类是紧的。对于随机图上的顶点覆盖问题，我们给出了类似的复杂性结果，特别地，证明了基于多项式时间分解的方法不能在3/2的因子内实现逼近。
Abstract.We consider the problem of providing a resolution proof of the statement that a given graph with n vertices and average degree roughly Δ does not contain an independent set of size k. For randomly chosen graphs and k ≤ n/3, we show that such proofs asymptotically almost surely require size roughly exponential in n/Δ6. This, in particular, implies a 2Ω (n) lower bound for constant degree graphs, and for Δ ≈ n1/6, shows that there are almost always no short resolution proofs for k as large as n/3 even though a maximum independent set is likely to be much smaller, roughly n5/6 in size. Our result implies that for graphs that are not too dense, almost all instances of the independent set problem are hard for resolution. Further, it provides an unconditional exponential lower bound on the running time of resolution-based search algorithms for finding a maximum independent set or approximating it within a factor of Δ/(6 ln Δ). We also give relatively simple upper bounds for the problem and show them to be tight for the class of exhaustive backtracking algorithms. We deduce similar complexity results for the related vertex cover problem on random graphs, proving, in particular, that no polynomial-time resolution-based method can achieve an approximation within a factor of 3/2.