Constraint Satisfaction Problems

Computational problems from many different application areas can be seen as constraint satisfaction problems. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or interpreting a visual image, can all be seen in this way. In any constraint satisfaction problem there is a collection of variables which all have to be assigned values, subject to specified constraints. An equivalent way of defining constraint satisfaction problems is via homomorphisms between relational structures. Our goal is to understand the computational complexity of constraint satisfaction problems.

Selected Publications

View All

• Minimal Weighted Clones with Boolean Support

  Peter G. Jeavons‚ Andrius Vaicenavičius and Stanislav Živný

  In Takahiro Hanyu, editor, Proceedings of the 46th IEEE International Symposium on Multiple−Valued Logic‚ ISMVL 2016‚ Sapporo‚ Japan‚ May 18−20‚ 2016. Pages 90–95. IEEE Computer Society. May, 2016.

  Details about Minimal Weighted Clones with Boolean Support | BibTeX data for Minimal Weighted Clones with Boolean Support | Link to Minimal Weighted Clones with Boolean Support

• Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

  David A. Cohen‚ Martin C. Cooper‚ Peter Jeavons and Stanislav Živný

  In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15). Pages 1945–1951. AAAI Press. 2015.

  Details about Tractable Classes of Binary CSPs Defined by Excluded Topological Minors | BibTeX data for Tractable Classes of Binary CSPs Defined by Excluded Topological Minors | Download (pdf) of Tractable Classes of Binary CSPs Defined by Excluded Topological Minors

• The complexity of valued constraint satisfaction

  Peter Jeavons‚ Andrei Krokhin and Stanislav Živný

  In Bulletin of the European Association for Theoretical Computer Science (EATCS). Vol. 113. Pages 21−55. 2014.

  Errata can be found here.

  Details about The complexity of valued constraint satisfaction | BibTeX data for The complexity of valued constraint satisfaction | Link to The complexity of valued constraint satisfaction