Personal tools
You are here: Home Events Abstract Archives 2004 Hard Constraint Satisfaction Problems and Homotopy Groups of Graphs

Hard Constraint Satisfaction Problems and Homotopy Groups of Graphs

Benoit Larose 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.

Document Actions