SAT backdoors: depth beats size

DOI10.1016/j.jcss.2024.103520arXiv2202.08326OpenAlexW4391018231WikidataQ129687810 ScholiaQ129687810MaRDI QIDQ6152185

Stefan Szeider, Jan Dreier, Sebastian Ordyniak

Publication date: 11 March 2024

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

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

zbMATH Keywords

satisfiabilityparameterized algorithmsSATbackdoorelimination distance

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Backdoors to q-Horn
• Graph isomorphism parameterized by elimination distance to bounded degree
• Sparsity. Graphs, structures, and algorithms
• Backdoors into heterogeneous classes of SAT and CSP
• Constraint satisfaction with bounded treewidth revisited
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• Backdoor treewidth for SAT
• Algorithms for propositional model counting
• Tree-depth, subgraph coloring and homomorphism bounds
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
• Combining Treewidth and Backdoors for CSP.
• Deciding First-Order Properties of Nowhere Dense Graphs
• Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
• On the Unreasonable Effectiveness of SAT Solvers
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

This page was built for publication: SAT backdoors: depth beats size