On Digraph Coloring Problems and Treewidth Duality
Albert Atserias · 2006
It is known that every constraint-satisfaction problem (CSP) reduces, and is in fact polynomially equivalent, to a digraph coloring problem. By carefully analyzing the constructions, we observe that the reduction is quantifierfree. Using this, we illustrate the power of the logical approach to CSPs by resolving two conjectures about treewidth duality in the digraph case. The point is that the analogues of these conjectures for general CSPs were resolved long ago by proof techniques that break down for digraphs. We also completely characterize those CSPs that are first-order definable and show that they coincide with those that have finitary tree duality. The combination of this result with an older result by Neˇsetˇril and Tardif shows that there is a computable listing of all template structures whose CSP is definable in full first-order logic. Finally, we provide new width lower bounds for some tractable CSPs. The novelty is that our bounds are a tight function of the treewidth of the underlying instance. As a corollary we get a new proof that there exist tractable CSPs without bounded treewidth duality. ∗ This work was partially supported by CICYT TIN2004-04343 and by the European Commision through the RTN COMBSTRU HPRN-CT2002-00278. 1 1