Title :
The Dichotomy for Conservative Constraint Satisfaction Problems Revisited
Author_Institution :
Dept. of Math. & Stat., McMaster Univ., Hamilton, ON, Canada
Abstract :
A central open question in the study of non-uniform constraint satisfaction problems (CSPs) is the dichotomy conjecture of Feder and Vardi stating that the CSP over a fixed constraint language is either NP-complete, or tractable. One of the main achievements in this direction is a result of Bulatov (LICS´03) confirming the dichotomy conjecture for conservative CSPs, that is, CSPs over constraint languages containing all unary relations. Unfortunately, the proof is very long and complicated, and therefore hard to understand even for a specialist. This paper provides a short and transparent proof.
Keywords :
computational complexity; constraint theory; operations research; CSP; NP-complete problems; conservative constraint satisfaction problems revisited dichotomy; constraint languages; dichotomy conjecture; fixed constraint language; Absorption; Algebra; Argon; Complexity theory; Computers; Polynomials; conservative algebra; constraint satisfaction problem; dichotomy theorem; list homomorphism problem;
Conference_Titel :
Logic in Computer Science (LICS), 2011 26th Annual IEEE Symposium on
Conference_Location :
Toronto, ON
Print_ISBN :
978-1-4577-0451-2
Electronic_ISBN :
1043-6871
DOI :
10.1109/LICS.2011.25
