Resolution complexity of perfect matching principles for sparse graphs

DOI10.1007/978-3-319-20297-6_15MaRDI QIDQ3194719zbMATH OpenOpenAlexFDO

Authors Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-20297-6_15

Mathematics Subject Classification ID

Complexity of proofs (03F20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Tight lower bounds on the resolution complexity of perfect matching principles
• Resolution lower bounds for perfect matching principles
• Resolution proofs of matching principles
• The resolution complexity of random graph \(k\)-colorability
• The resolution complexity of independent sets and vertex covers in random graphs

Cited in

(5)

• Resolution proofs of matching principles
• Resolution lower bounds for perfect matching principles
• Tight lower bounds on the resolution complexity of perfect matching principles
• Fine-grained complexity for sparse graphs
• Perfect matching in random graphs is as hard as Tseitin

This page was built for publication: Resolution complexity of perfect matching principles for sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194719)