Backdoors to Satisfaction
From MaRDI portal
Publication:2908542
DOI10.1007/978-3-642-30891-8_15zbMath1358.68133DBLPconf/birthday/GaspersS12arXiv1110.6387OpenAlexW1732327014WikidataQ60060022 ScholiaQ60060022MaRDI QIDQ2908542
Publication date: 5 September 2012
Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.6387
Related Items (21)
Backdoors to Normality for Disjunctive Logic Programs ⋮ Structural decompositions for problems with global constraints ⋮ A Basic Parameterized Complexity Primer ⋮ Structural parameterizations with modulator oblivion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Disjunctive closures for knowledge compilation ⋮ Backdoor Sets for CSP. ⋮ Backdoors for linear temporal logic ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Parameterized Enumeration for Modification Problems ⋮ Strong Backdoors for Default Logic ⋮ Backdoors to planning ⋮ Backdoors to tractable answer set programming ⋮ Backdoors into Two Occurrences ⋮ Computational Short Cuts in Infinite Domain Constraint Satisfaction ⋮ Backdoors to q-Horn
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Stable assignment with couples: parameterized complexity and local search
- On approximating minimum vertex cover for graphs with perfect matching
- Nested satisfiability
- Graph theoretical structures in logic programs and default theories
- Finding odd cycle transversals.
- Improved upper bounds for vertex cover
- On finding short resolution refutations and small unsatisfiable subsets
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- Backdoor sets for DLL subsolvers
- Improved algorithms for feedback vertex set problems
- A kernelization algorithm for \(d\)-hitting set
- Argumentation in artificial intelligence
- Computational properties of argument systems satisfying graph-theoretic constraints
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Backdoor sets of quantified Boolean formulas
- How to reason defeasibly
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Variable and term removal from Boolean formulae
- An abstract, argumentation-theoretic approach to default reasoning
- Effective use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors.
- Conjunctive-query containment and constraint satisfaction
- Augmenting tractable fragments of abstract argumentation
- Coherence in finite argument systems.
- On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Resolution for quantified Boolean formulas
- On the computational cost of disjunctive logic programming: Propositional case
- Parameterized complexity and local search approaches for the stable marriage problem with ties
- Permanents, Pfaffian orientations, and even directed circuits
- Logic programs with stable model semantics as a constraint programming paradigm
- Algorithms for propositional model counting
- Fixed-parameter approximation: conceptual framework and approximability results
- On probabilistic inference by weighted model counting
- Solving \#SAT using vertex covers
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Vertex Cover: Further Observations and Further Improvements
- Backdoors to Acyclic SAT
- Strong Backdoors to Nested Satisfiability
- Satisfiability of Acyclic and Almost Acyclic CNF Formulas.
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- A fixed-parameter algorithm for the directed feedback vertex set problem
- On Parameterized Approximability
- Parameterized Approximation Problems
- Tradeoffs in the Complexity of Backdoor Detection
- CNF-Satisfiability Test by Counting and Polynomial Average Time
- Renaming a Set of Clauses as a Horn Set
- ON DISJOINT CYCLES
- Properties and Complexity of Some Formal Inter-agent Dialogues
- Feedback Vertex Set in Mixed Graphs
- The Good, the Bad, and the Odd: Cycles in Answer-Set Programs
- Parameterized and Exact Computation
- Theory and Applications of Satisfiability Testing
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- The complexity of satisfiability problems
- Symbolic and Quantitative Approaches to Reasoning with Uncertainty
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
This page was built for publication: Backdoors to Satisfaction
