Logic in Computer Science (LICS 2003)

Paper: Tractable conservative Constraint Satisfaction Problems (at LICS 2003)

Authors: Andrei A. Bulatov

Abstract

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.

BibTeX

  @InProceedings{Bulatov-Tractableconservati,
    author = 	 {Andrei A. Bulatov},
    title = 	 {Tractable conservative Constraint Satisfaction Problems},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {321--},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }