Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete

DOI10.1007/978-3-540-74456-6_16zbMath1147.68530OpenAlexW1510911673MaRDI QIDQ3525565

Jaroslav Nešetřil, Mark H. 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)

Related Items (4)

Colouring, constraint satisfaction, and complexity ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Characterizations of several Maltsev conditions.

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