Small Unsatisfiable Subsets in Constraint Satisfaction
Small Unsatisfiable Subsets in Constraint Satisfaction
复制标题
约束满足中不可满足的小子集
DOI：
10.1109/ictai.2014.72
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Stefan Szeider
中科院分区：
文献类型：
--
作者：
Ronald de Haan;Iyad A. Kanj;Stefan Szeider
在计算机科学和人工智能中，寻找一组约束的小的不可满足子集的问题是非常重要的。我们研究的问题，确定是否一个给定的约束满足问题（CSP）的实例有一个不可满足的子集的大小最多k从参数化的复杂性的角度来看。我们发现，找到一个CSP实例的小的不可满足的子集的问题是困难的CNF公式比相应的问题。此外，我们表明，这个问题是不固定参数听话的限制问题时，任何最大听话的布尔约束语言（问题是非平凡的）。我们发现，即使当任何变量的最大出现次数是由一个常数，限制，导致固定参数的情况下，CNF公式的易处理性的限制有界的问题是困难的。最后，我们发现小的不可满足的子集的问题，以确定变量分配的问题，已经强制执行了少量的约束（骨干），或已经排除了少量的约束（反骨干）。
The problem of finding small unsatisfiable subsets of a set of constraints is important for various applications in computer science and artificial intelligence. We study the problem of identifying whether a given instance to the constraint satisfaction problem (CSP) has an unsatisfiable subset of size at most k from a parameterized complexity point of view. We show that the problem of finding small unsatisfiable subsets of a CSP instance is harder than the corresponding problem for CNF formulas. Moreover, we show that the problem is not fixed-parameter tractable when restricting the problem to any maximal tractable Boolean constraint language (for which the problem is nontrivial). We show that the problem is hard even when the maximum number of occurrences of any variable is bounded by a constant, a restriction which leads to fixed-parameter tractability for the case of CNF formulas. Finally, we relate the problem of finding small unsatisfiable subsets to the problem of identifying variable assignments that are enforced already by a small number of constraints (backbones), or that are ruled out already by a small number of constraints (anti-backbones).