Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

DOI10.1007/978-3-540-74456-6_16MaRDI QIDQ3525565zbMATHOpenAlexFDO

Authors J. Nešetřil, Mark Siggers

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_16

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• A proof of the CSP dichotomy conjecture
• scientific article; zbMATH DE number 1670830
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Forbidden lifts (NP and CSP for combinatorialists)

Cited in

(8)

• Easy NP-hardness Proofs of Some Subset Choice Problems
• NP for Combinatorialists
• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Colouring, constraint satisfaction, and complexity
• Characterizations of several Maltsev conditions.
• Sublinear P system solutions to NP-complete problems
• Forbidden lifts (NP and CSP for combinatorialists)

This page was built for publication: Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

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