School Seminars and Colloquia

Constraint Satisfaction Problems and Universal Algebra

Discrete Structures and Algorithms (Seminar)

by Marcel Jackson


Institution: School of Engineering and Mathematical Sciences, La Trobe University, Melbourne
Date: Mon 7th March 2011
Time: 4:15 PM
Location: Hercus Theatre (L105, 1st floor) David Caro Building (Physics) The University of Melbourne

Abstract: It is well known that the task of deciding whether or not a finite graph is 2-colourable is rather easy, while the task of deciding whether or not a finite graph is 3-colourable is a familiar NP-complete problem. These problems fall into the general class of computational problems that ask for the existence of a function from some given combinatorial object (the vertices of the graph to be coloured) into some fixed domain (the colours) subject to preservation of certain given constraints (adjacent vertices are coloured differently). In other words, they are constraint satisfaction problems.

A very large number of natural computational problems can be interpreted as constraint satisfaction problems, and classifying the computational complexity of CSPs has received quite intense attention over the past decade. Each CSP (with fixed target domain) is solvable in the class NP, but a very influential conjecture of Feder and Vardi is that a dichotomy holds: such a problem is either NP-complete or is solvable in polynomial time.

This talk will be aimed at a general audience: we introduce the basic notions and the practical and theoretical motivations for studying the complexity of CSPs, with a particular focus on introducing the techniques from universal algebra that have informed most recent progress on the dichotomy conjecture.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au