Solving infinite-domain CSPs using the patchwork property
Solving infinite-domain CSPs using the patchwork property
复制标题
使用拼凑属性求解无限域 CSP
DOI：
10.1016/j.artint.2023.103880
复制
发表时间：
2023
影响因子：
14.4
通讯作者：
Dabrowski K
中科院分区：
文献类型：
--
作者：
Dabrowski K
约束满足问题（CSP）在计算机科学和人工智能中有着重要的应用。特别是，无限域CSP已被广泛用于人工智能的子领域，如时空推理。由于约束满足是一个计算困难的问题，许多工作一直致力于确定有效解决的限制性问题。一种方法是限制变量和约束的交互，一种非常成功的方法是限制底层原始图的树宽。Bodirsky & Dalmau [J. Comput.系统Sci. 79（1），2013]和Huang et al. [Artif.内特尔195，2013]证明了CSP（Γ）可以在nf（w）时间内求解（其中n是实例的大小，w是原始图的树宽，f是可计算函数）。对于基本关系具有patchwork性质的CSP，我们将此界改进为f（w）n O（1），其中函数f只依赖于语言Γ.因此，这样的问题是固定参数易处理的，我们的算法是渐近快于以前的。此外，我们的方法是不限于二进制的约束，所以它是适用于严格较大的一类问题比黄等人。然而，存在自然的问题，所涵盖的Bodirsky & Dalmau的算法，但不是我们的，我们开始调查的方式，推广我们的结果，以更大的语言家族。我们还分析了我们的算法的运行时间，并表明它是最佳的（指数时间假设下），如艾伦的区间代数的某些语言。
The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci. 79 (1), 2013] and Huang et al.[Artif. Intell. 195, 2013] proved that CSP (Γ) can be solved in n f (w) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f (w)⋅ n O (1), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.