Solving infinite-domain CSPs using the patchwork property

DOI10.1016/J.ARTINT.2023.103880arXiv2107.01428OpenAlexW3176144513MaRDI QIDQ6157211FDOQ6157211

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

Publication date: 19 June 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

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.

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)

Cites Work

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

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)