Solving infinite-domain CSPs using the patchwork property

DOI10.1016/J.ARTINT.2023.103880MaRDI QIDQ6157211zbMATH OpenOpenAlexFDO

Authors Konrad Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov

Publication date 19 June 2023

Published in Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.01428

zbMATH Keywords

treewidthlower boundparameterized complexityconstraint satisfaction probleminfinite domain

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Abstract: 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$(Gamma)$ 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 $Gamma$. We improve this bound to $f(w)cdot{n}^{O(1)}$, where the function $f$ only depends on the language $Gamma$, 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.

Cites work

• scientific article; zbMATH DE number 1630007 (Why is no real title available?)
• scientific article; zbMATH DE number 3860390 (Why is no real title available?)
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 3080680 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A complexity dichotomy for poset constraint satisfaction
• A model-theoretic view on qualitative constraint reasoning
• A proof of the CSP dichotomy conjecture
• A survey of homogeneous structures
• A tableau algorithm for description logics with concrete domains and general TBoxes
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Branching interval algebra: an almost complete picture
• Can you beat treewidth?
• Complexities of Relational Structures
• Complexity of Finding Embeddings in a k-Tree
• Complexity of infinite-domain constraint satisfaction
• Computational phylogenetics. An introduction to designing methods for phylogeny estimation
• Constants and finite unary relations in qualitative constraint reasoning
• Constraint Satisfaction Problems on Intervals and Lengths
• Constraint satisfaction with bounded treewidth revisited
• Datalog and constraint satisfaction with infinite templates
• Decomposition and tractability in qualitative spatial and temporal reasoning
• Description logics with concrete domains and general concept inclusions revisited
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Expressive power and complexity in algebraic logic
• Extension properties of Boolean contact algebras
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Fundamentals of parameterized complexity
• Graph minors. III. Planar tree-width
• Graph theory
• Handbook of constraint programming.
• Homogenizable relational structures
• Homogenizable structures and model completeness
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Maintaining knowledge about temporal intervals
• Non-dichotomies in Constraint Satisfaction Complexity
• Non-homogenizable classes of finite structures
• Nonserial dynamic programming
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• On the homogeneous countable Boolean contact algebra.
• Parametrized complexity theory.
• Point algebras for temporal reasoning: Algorithms and complexity
• Reasoning about partially ordered events
• Reasoning about temporal relations
• Recursive conditioning
• Relation algebras of intervals
• SAT vs. search for qualitative temporal reasoning
• Satisfiability problems on intervals and unit intervals
• Scheduling with AND/OR Precedence Constraints
• Slightly superexponential parameterized problems
• Temporal constraint networks
• The complexity of phylogeny constraint satisfaction problems
• The complexity of reconstructing trees from qualitative characters and subtrees
• The complexity of temporal constraint satisfaction problems
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
• The mutual exclusion problem
• The universal homogeneous binary tree
• Tractability Results in the Block Algebra
• Which problems have strongly exponential complexity?
• “Sometimes” and “not never” revisited

Cited in

(1)

• Computational Short Cuts in Infinite Domain Constraint Satisfaction

This page was built for publication: Solving infinite-domain CSPs using the patchwork property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6157211)