Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
Tractable Classes of Binary CSPs Defined by Excluded Topological Minors
复制标题
DOI：
--
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
D. Cohen;Martin C. Cooper;P. Jeavons;Stanislav Živný
中科院分区：
文献类型：
--
作者：
D. Cohen;Martin C. Cooper;P. Jeavons;Stanislav Živný
二元约束满足问题（CSP）是判定一组变量是否存在满足指定约束的赋值。CSP实例可以表示为标记图（称为微观结构），对约束的形式及其施加位置进行编码。我们认为，通过限制所允许的形式的微观结构定义的子问题。以前考虑过的一种限制形式是禁止某些指定的子结构（模式）。这捕获了CSP的一些易于处理的类，但没有捕获众所周知的非循环性属性。在本文中，我们介绍了一个二进制CSP实例的拓扑子的概念。通过禁止某些模式作为拓扑未成年人，我们得到了一个紧凑的机制来表达几个新的听话的类，包括新的概括类的无环实例。
The binary Constraint Satisfaction Problem (CSP) is to decide whether there exists an assignment to a set of variables which satisfies specified constraints between pairs of variables. A CSP instance can be presented as a labelled graph (called the microstructure) encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of the microstructure. One form of restriction that has previously been considered is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture the well-known property of acyclicity. In this paper we introduce the notion of a topological minor of a binary CSP instance. By forbidding certain patterns as topological minors we obtain a compact mechanism for expressing several novel tractable classes, including new generalisations of the class of acyclic instances.