loading...
Tractable conservative Constraint Satisfaction Problems
Ottawa, Canada June 22-June 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2003.121007218th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Andrei A. Bulatov, Oxford University Computing Laboratory
In a constraint satisfaction problem (CSP) the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages which give rise to tractable CSPs from those which do not.
We achieve this goal for the widely used variant of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the LIST H-COLORING problem is polynomial time solvable.
Citation:
Andrei A. Bulatov, "Tractable conservative Constraint Satisfaction Problems," lics, pp.321, 18th Annual IEEE Symposium on Logic in Computer Science (LICS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.