Cliques enumeration and tree-like resolution proofs

DOI10.1016/j.ipl.2018.03.001zbMath1476.68112OpenAlexW2790492047WikidataQ61732571 ScholiaQ61732571MaRDI QIDQ1708271

Massimo Lauria

Publication date: 5 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.03.001

zbMATH Keywords

cliqueresolutiondecision treetheory of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Complexity of proofs (03F20)

Uses Software

• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Near optimal seperation of tree-like and general resolution
• A combinatorial characterization of treelike resolution space
• The intractability of resolution
• Optimality of size-width tradeoffs for resolution
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The complexity of proving that a graph is Ramsey
• Non-Ramsey graphs are \(c\log n\)-universal
• Space bounds for resolution
• A characterization of tree-like resolution size
• The resolution complexity of independent sets and vertex covers in random graphs
• A combinatorial characterization of resolution width
• Pebble Games, Proof Complexity, and Time-Space Trade-offs
• Narrow proofs may be spacious
• Parameterized Bounded-Depth Frege Is not Optimal
• From small space to small width in resolution
• Space Complexity in Propositional Calculus
• The Pebbling Problem is Complete in Polynomial Space
• The relative efficiency of propositional proof systems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Short proofs are narrow—resolution made simple
• GRASP: a search algorithm for propositional satisfiability
• Reducibility among Combinatorial Problems
• Finding, minimizing, and counting weighted subgraphs
• Clique is hard on average for regular resolution
• The Monotone Complexity of $k$-Clique on Random Graphs
• The Complexity of Propositional Proofs
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Parameterized Complexity of DPLL Search Procedures
• Concentration of Measure for the Analysis of Randomized Algorithms
• On the complexity of \(k\)-SAT

This page was built for publication: Cliques enumeration and tree-like resolution proofs