| c ○ Birkhäuser Verlag, Basel 0000 computational complexity THE RESOLUTION COMPLEXITY OF INDEPENDENT SETS AND VERTEX COVERS IN RANDOM GRAPHS (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 ∆ ≈ n 1/6, shows that proofs must be quite large for k up to n/3 even though a maximum independent set is likely to be much smaller, roughly n 5/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 log ∆). 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. | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||