Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429776 | Journal of Computer and System Sciences | 2016 | 10 Pages |
Abstract
Conservative constraint satisfaction problems (CSPs) constitute an important particular case of the general CSP, in which the allowed values of each variable can be restricted in an arbitrary way. Problems of this type are well studied for graph homomorphisms. A dichotomy theorem characterizing conservative CSPs solvable in polynomial time and proving that the remaining ones are NP-complete was proved by Bulatov (2003) in [4]. Its proof, however, is quite long and technical. A shorter proof of this result based on the absorbing subuniverses technique was suggested by Barto (2011) in [1]. In this paper we give a short elementary proof of the dichotomy theorem for conservative CSPs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andrei A. Bulatov,