Name
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 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 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 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00037-007-0230-0 | Computational Complexity |
Keywords | Field | DocType |
vertex covers,related vertex cover problem,n vertex,independent set problem,size k,independent sets,constant degree graph,. resolution,short resolution proof,hardness of approximation,maximum independent set,random graphs,vertex cover,resolution complexity,average degree,independent set,resolution proof,proof complexity,lower bound,independent,upper bound,search algorithm,resolution,random graph,polynomial time | Discrete mathematics,Combinatorics,Random graph,Upper and lower bounds,Independent set,Vertex cover,Proof complexity,Almost surely,Feedback vertex set,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
16 | 3 | 1420-8954 |
Citations | PageRank | References |
11 | 0.51 | 29 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Beame | 1 | 2234 | 176.07 |
| Russell Impagliazzo | 2 | 5444 | 482.13 |
| Ashish Sabharwal | 3 | 1063 | 70.62 |