Backdoors into heterogeneous classes of SAT and CSP
From MaRDI portal
Publication:730498
DOI10.1016/J.JCSS.2016.10.007zbMATH Open1356.68097arXiv1509.05725OpenAlexW2246468915MaRDI QIDQ730498FDOQ730498
Stefan Szeider, Neeldhara Misra, S. Zivny, Serge Gaspers, Sebastian Ordyniak
Publication date: 28 December 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Abstract: In this paper we extend the classical notion of strong and weak backdoor sets for SAT and CSP by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong and weak backdoor sets into heterogeneous base classes for SAT and CSP.
Full work available at URL: https://arxiv.org/abs/1509.05725
Recommendations
- Backdoors to acyclic SAT
- From backdoor key to backdoor completability: improving a known measure of hardness for the satisfiable CSP
- Strong backdoors to nested satisfiability
- Solving d-SAT via Backdoors to Small Treewidth
- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
- Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
- Combining treewidth and backdoors for CSP
- Backdoors to tractable answer set programming
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- The Tractability of CSP Classes Defined by Forbidden Patterns
- Principles and practice of constraint programming. 20th international conference, CP 2014, Lyon, France, September 8--12, 2014. Proceedings
- Backdoors to Satisfaction
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- The complexity of satisfiability problems
- Constraints, consistency and closure
- Characterizations of several Maltsev conditions.
- Tractability in constraint satisfaction problems: a survey
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Tractability and Learnability Arising from Algebras with Few Subpowers
- A Simple Algorithm for Mal'tsev Constraints
- Hypertree decompositions and tractable queries
- Constraint satisfaction with bounded treewidth revisited
- Backdoor sets of quantified Boolean formulas
- Tradeoffs in the Complexity of Backdoor Detection
- Backdoors in the Context of Learning
- Augmenting tractable fragments of abstract argumentation
- Matched formulas and backdoor sets
- Solving Problems on Graphs of High Rank-Width
- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
- Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
- Combining Treewidth and Backdoors for CSP.
- Meta-kernelization using Well-structured Modulators
Cited In (20)
- Backdoor DNFs
- Strong backdoors for default logic
- Tractability in constraint satisfaction problems: a survey
- Title not available (Why is that?)
- SAT backdoors: depth beats size
- Parameterised complexity of model checking and satisfiability in propositional dependence logic
- Backdoors to planning
- CSP beyond tractable constraint languages
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- Solving d-SAT via Backdoors to Small Treewidth
- Decomposing SAT Instances with Pseudo Backbones
- Strong backdoors for default logic
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- ALIAS: a modular tool for finding backdoors for SAT
- Solving problems on graphs of high rank-width
- Backdoor Sets for CSP.
- Solving Problems on Graphs of High Rank-Width
- A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
This page was built for publication: Backdoors into heterogeneous classes of SAT and CSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730498)
