Computational Short Cuts in Infinite Domain Constraint Satisfaction

DOI10.1613/jair.1.13787zbMath1502.68273arXiv2211.10144OpenAlexW4309587002MaRDI QIDQ5870497

Victor Lagerkvist, Sebastian Ordyniak, Peter Jonsson

Publication date: 9 January 2023

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

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

zbMATH Keywords

constraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tractability in constraint satisfaction problems: a survey
• An initial study of time complexity in infinite-domain constraint satisfaction
• Backdoors into heterogeneous classes of SAT and CSP
• Backdoor sets of quantified Boolean formulas
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Backdoors for linear temporal logic
• Constants and finite unary relations in qualitative constraint reasoning
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• Augmenting tractable fragments of abstract argumentation
• Relation algebras of intervals
• Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Backdoors to planning
• Backdoors to tractable answer set programming
• Parametrized complexity theory.
• Backdoors to Satisfaction
• A Model-Theoretic View on Qualitative Constraint Reasoning
• Integer Programming with a Fixed Number of Variables
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Complexity of Infinite-Domain Constraint Satisfaction
• On Random Ordering Constraints
• The complexity of temporal constraint satisfaction problems
• The NP-Completeness of Some Edge-Partition Problems
• The Inverse Satisfiability Problem
• Reasoning about temporal relations
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Scheduling with AND/OR Precedence Constraints
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Backdoor Sets for CSP.
• A Proof of the CSP Dichotomy Conjecture

This page was built for publication: Computational Short Cuts in Infinite Domain Constraint Satisfaction