On digraph coloring problems and treewidth duality
On digraph coloring problems and treewidth duality
复制标题
关于有向图着色问题和树宽对偶性
DOI：
10.1016/j.ejc.2007.11.004
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Albert Atserias
中科院分区：
文献类型：
--
作者：
Albert Atserias
众所周知，每个约束满足问题（CSP）减少，实际上是多项式等价的，一个有向图着色问题。通过仔细分析这些结构，我们发现这种归约是不受量词限制的。利用这一点，我们说明了权力的逻辑方法CSP解决两个altutures关于树宽对偶的有向图的情况下。问题的关键在于，这些类似于一般CSP的证明方法在很久以前就被分解为有向图的证明技术解决了。我们还完全刻画了那些CSP是一阶可定义的，并表明它们与那些具有有限树对偶的CSP相吻合。将这个结果与Nešetzil和Tardif的一个较早的结果相结合，表明存在所有模板结构的可计算列表，这些模板结构的CSP可以在完全一阶逻辑中定义。最后，我们提供了一些易处理的CSP的新的宽度下界。新颖之处在于，我们的边界是底层实例的树宽的紧函数。作为推论，我们得到了一个新的证明，即存在无有界树宽对偶的易处理的CSP。
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 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 of Nešetřil 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.