CSP beyond tractable constraint languages

DOI10.1007/s10601-023-09362-3OpenAlexW4387536908MaRDI QIDQ6154179

Jan Dreier, Stefan Szeider, Sebastian Ordyniak

Publication date: 14 February 2024

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-023-09362-3

zbMATH Keywords

CSPtractable classconstraint languagebackdoor depthrecursive backdoor

Mathematics Subject Classification ID

Artificial intelligence (68Txx) Theory of computing (68Qxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Tractability in constraint satisfaction problems: a survey
• Graph isomorphism parameterized by elimination distance to bounded degree
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• Hypertree decompositions and tractable queries
• Backdoors into heterogeneous classes of SAT and CSP
• Characterising tractable constraints
• A comparison of structural CSP decomposition methods
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• Complexity of conservative constraint satisfaction problems
• The Tractability of CSP Classes Defined by Forbidden Patterns
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Combining Treewidth and Backdoors for CSP.
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Parameterized Complexity of Elimination Distance to First-Order Logic Properties
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems
• Parameterized Algorithms

This page was built for publication: CSP beyond tractable constraint languages