Treewidth with a quantifier alternation revisited

DOI10.4230/LIPICS.IPEC.2017.26zbMATH Open1443.68073MaRDI QIDQ5111886FDOQ5111886

Valia Mitsou, Michael Lampis

Publication date: 27 May 2020

Recommendations

• QBF as an alternative to Courcelle's theorem
• Bounded-width QBF is PSPACE-complete
• On the exact complexity of evaluating quantified \(k\)-CNF
• Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings
• Bounded-width QBF is PSPACE-complete

zbMATH Keywords

treewidthexponential time hypothesisquantified SAT

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Cites Work

• Fixed-Parameter Tractable Reductions to SAT
• Which problems have strongly exponential complexity?
• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms for propositional model counting
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• Satisfiability of acyclic and almost acyclic CNF formulas
• Constraint satisfaction with bounded treewidth revisited
• When Trees Grow Low: Shrubs and Fast MSO1
• The polynomial-time hierarchy
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Bounded-width QBF is PSPACE-complete
• The complexity of first-order and monadic second-order logic revisited
• Model counting for CNF formulas of bounded modular treewidth
• Complexity and Approximability of Parameterized MAX-CSPs
• Principles and Practice of Constraint Programming – CP 2004
• Model Checking Lower Bounds for Simple Graphs
• Solving #SAT and MAXSAT by Dynamic Programming
• Parameterized complexity classes beyond para-NP
• Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
• Using decomposition-parameters for QBF: mind the prefix!

Cited In (11)

• Grundy Distinguishes Treewidth from Pathwidth
• Title not available (Why is that?)
• Solving projected model counting by utilizing treewidth and its limits
• Lower Bounds for QBFs of Bounded Treewidth
• Title not available (Why is that?)
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Tight double exponential lower bounds
• Default logic and bounded treewidth
• Default logic and bounded treewidth
• Using decomposition-parameters for QBF: mind the prefix!
• Does Treewidth Help in Modal Satisfiability?

This page was built for publication: Treewidth with a quantifier alternation revisited

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