Department of Mathematics
and Statistics
Concordia University
4pm Tuesday 6 July 2004
Room 2511, JCMB, King's Buildings
Constraint satisfaction problems (CSP) provide a general framework for the study of many well-known computational problems including graph colourability and k-satisfiability problems. The general CSP is equivalent to the homomorphism problem between relational structures. For example, the k-colouring problem can be expressed as the problem of deciding whether a given graph admits a homomorphism (i.e., edge-preserving mapping) to a complete graph with k vertices. Feder and Vardi have conjectured a dichotomy for problems of the form CSP(B) with a fixed structure B: given a structure A, is there a homomorphism from A to B? The conjecture states that, depending on the structure B, the problem CSP(B) is either in P or NP-complete. This conjecture has been refined by Bulatov, Jeavons and Krokhin who have initiated an algebraic approach to the problem that has proved quite fruitful. In particular, they provide a useful hardness criterion for CSP's.
Every problem CSP(B) can be encoded as the retraction problem Ret(H) for a fixed reflexive digraph H: given a digraph G containing H, is there a homomorphism from G to H which fixes H? We will show how the criterion mentioned above allows one to employ certain simple topological properties of digraphs which can be used to identify hard retraction and constraint satisfaction problems.
Since reflexive digraphs appear naturally as inferred constraints in a wide range of CSPs, this result provides a flexible tool to prove hardness results. We present applications of this method to various problems such as retraction problems for digraphs and partially ordered sets and strong hypergraph colouring.