On the Power of k -Consistency
On the Power of k -Consistency
复制标题
论 k 一致性的力量
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
V. Dalmau
中科院分区：
文献类型：
--
作者：
Albert Atserias;A. Bulatov;V. Dalmau
约束满足问题的k-一致性算法粗略地通过寻找至多k个变量的所有部分解，并迭代地删除那些不能扩展为多个变量的部分解的方法来进行。已知，如果编码约束范围的结构的核心树宽至多为k，则k-一致性算法总是正确的。我们证明了与此完全相反：如果编码约束范围的结构的核心不具有至多k个树宽，则k-一致性算法并不总是正确的。这就是k-一致性算法在结构上的精确能力。
The k-consistency algorithm for constraint-satisfaction problems proceeds, roughly, by finding all partial solutions on at most k variables and iteratively deleting those that cannot be extended to a partial solution by one more variable. It is known that if the core of the structure encoding the scopes of the constraints has treewidth at most k, then the k-consistency algorithm is always correct. We prove the exact converse to this: if the core of the structure encoding the scopes of the constraints does not have treewidth at most k, then the k-consistency algorithm is not always correct. This characterizes the exact power of the k-consistency algorithm in structural terms.