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

DOI10.1007/s00037-007-0230-0zbMath1137.68030OpenAlexW2079758416MaRDI 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 setvertex coverproof complexityhardness of approximationresolution proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity of proofs (03F20)

Related Items (9)

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 ⋮ Cutting planes cannot approximate some integer programs ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Parameterized Bounded-Depth Frege Is Not Optimal ⋮ Limitations of restricted branching in clause learning ⋮ Unnamed Item ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ Large clique is hard on average for resolution

This page was built for publication: The resolution complexity of independent sets and vertex covers in random graphs