Solving d-SAT via Backdoors to Small Treewidth

DOI10.1137/1.9781611973730.43MaRDI QIDQ5363089zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Backdoor treewidth for SAT
• Backdoors into heterogeneous classes of SAT and CSP
• Efficient data structures for backtrack search SAT solvers
• Backdoors to acyclic SAT
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
• Strong backdoors to nested satisfiability
• scientific article; zbMATH DE number 4080977

Cited in

(17)

• Backdoor treewidth for SAT
• Backdoors to acyclic SAT
• Strong backdoors to nested satisfiability
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Decomposing SAT Instances with Pseudo Backbones
• Bidimensionality and kernels
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Improved fixed-parameter algorithm for the minimum weight 3-SAT problem
• Backdoor sets for CSP
• A Retrospective on (Meta) Kernelization
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• Upper and lower bounds for weak backdoor set detection
• On the Parameterized Complexity of Clique Elimination Distance
• scientific article; zbMATH DE number 7724246 (Why is no real title available?)
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
• Decremental sensitivity oracles for covering and packing minors
• Backdoors into heterogeneous classes of SAT and CSP

This page was built for publication: Solving d-SAT via Backdoors to Small Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363089)