Binary constraint satisfaction problems defined by excluded topological minors
Binary constraint satisfaction problems defined by excluded topological minors
复制标题
由排除的拓扑次要定义的二元约束满足问题
DOI：
10.1016/j.ic.2018.09.013
复制
发表时间：
2019
影响因子：
1
通讯作者：
Cohen D
中科院分区：
文献类型：
--
作者：
Cohen D
二元约束满足问题（CSP）是确定是否存在满足变量对之间指定约束的一组变量的赋值。二进制 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 binary CSP instance can be presented as a labelled graph encoding both the forms of the constraints and where they are imposed. We consider subproblems defined by restricting the allowed form of this graph. One type of restriction is to forbid certain specified substructures (patterns). This captures some tractable classes of the CSP, but does not capture classes defined by language restrictions, or the well-known structural property of acyclicity.We extend the notion of pattern and introduce the notion of a topological minor of a binary CSP instance. By forbidding afiniteset of patterns from occurring as topological minors we obtain a compact mechanism for expressing novel tractable subproblems of the CSP, including new generalisations of the class of acyclic instances.