The resolution complexity of independent sets and vertex covers in random graphs

DOI10.1007/s00037-007-0230-0zbMath1137.68030MaRDI QIDQ2474203

Ashish Sabharwal, Russell Impagliazzo, P. W. Beame

Publication date: 5 March 2008

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0230-0

zbMATH Keywords

independent set; vertex cover; proof complexity; hardness of approximation; resolution proof

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

03F20: Complexity of proofs

Related Items

Unnamed Item, Constructing concrete hard instances of the maximum independent set problem, Parameterized Complexity of DPLL Search Procedures, Cutting planes cannot approximate some integer programs, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Cliques enumeration and tree-like resolution proofs, Large clique is hard on average for resolution, Limitations of restricted branching in clause learning, Parameterized Bounded-Depth Frege Is Not Optimal