Constructing templates with tree duality
Jan Foniok
ETH Zurich

Consider the H-colouring problem, a special but fairly generic  
constraint satisfaction problem: for a fixed digraph H, called a  
template, the H-colouring problem is to decide for an input digraph G  
whether there exists a homomorphism from G to H ("G -> H").  
Computational complexity of H-colouring depends on H. For instance, if  
H is the complete graph on 3 vertices, H-colouring is the same as 3- 
colouring. It was conjectured by Feder and Vardi (1999) that any H- 
colouring is either polynomial or NP-complete, that is, it never  
belongs to any class strictly between P and NP (the "dichotomy  
conjecture").

In this talk I concentrate on a tractable case: templates with "tree  
duality". These are the templates H for which the (polynomial) arc- 
consistency algorithm works. Equivalently, for any G, if G does not  
admit a homomorphism to H ("G -/-> H"), then there exists an oriented  
tree T (an "obstruction") such that T -> G but T -/-> H.

How does one construct a template with tree duality? For any finite  
set of trees t there is a "dual" H, a template, for which an  
obstruction can always be found in t (Nesetril & Tardif, 2000). I will  
show that taking arc graphs preserves tree duality (but not the  
existence of a finite complete set of obstructions). The arc graph is  
a special case of a right adjoint in the category of digraphs, and  
indeed, all right adjoints preserve tree duality. In some cases, we  
can explicitly describe the tree obstructions.

Based on joint work with Claude Tardif.