Logic in Computer Science (LICS 2005)

Paper: On Digraph Coloring Problems and Treewidth Duality (at LICS 2005)

Authors: Albert Atserias

Abstract

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 quantifier-free. 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 seem to 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 Nesetril and Tardif shows that it is semi-decidable, given H, whether the H-coloring problem 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.

BibTeX

  @InProceedings{Atserias-OnDigraphColoringPr,
    author = 	 {Albert Atserias},
    title = 	 {On Digraph Coloring Problems and Treewidth Duality},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2005},
    year =	 2005,
    editor =	 {Prakash Panangaden},
    month =	 {June}, 
    pages =      {106--115},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }