Backdoors into heterogeneous classes of SAT and CSP

DOI10.1016/j.jcss.2016.10.007zbMath1356.68097arXiv1509.05725OpenAlexW2246468915MaRDI QIDQ730498

Stefan Szeider, Neeldhara Misra, Stanislav Živný, Serge Gaspers, Sebastian Ordyniak

Publication date: 28 December 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

satisfiabilityconstraint satisfactionparameterized complexitybackdoor set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

Tractability in constraint satisfaction problems: a survey ⋮ Solving Problems on Graphs of High Rank-Width ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ SAT backdoors: depth beats size ⋮ CSP beyond tractable constraint languages ⋮ Solving problems on graphs of high rank-width ⋮ Backdoor Sets for CSP. ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Parameterised complexity of model checking and satisfiability in propositional dependence logic ⋮ Backdoors to planning ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• Tractability in constraint satisfaction problems: a survey
• Fundamentals of parameterized complexity
• Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
• Hypertree decompositions and tractable queries
• Constraint satisfaction with bounded treewidth revisited
• Backdoor sets of quantified Boolean formulas
• Constraints, consistency and closure
• Augmenting tractable fragments of abstract argumentation
• Characterizations of several Maltsev conditions.
• Backdoors to Satisfaction
• The Tractability of CSP Classes Defined by Forbidden Patterns
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Solving Problems on Graphs of High Rank-Width
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
• Tradeoffs in the Complexity of Backdoor Detection
• Backdoors in the Context of Learning
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• Combining Treewidth and Backdoors for CSP.
• Meta-kernelization using Well-structured Modulators
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of satisfiability problems
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: Backdoors into heterogeneous classes of SAT and CSP