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 definining constraint satisfaction problems is via homomorphisms between relational structures. Our goal is to understand the computational complexity of constraint satisfaction problems.
Head of Activity
Faculty
Research
Past Members
Selected Publications

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