Treewidth with a quantifier alternation revisited

DOI10.4230/LIPICS.IPEC.2017.26MaRDI QIDQ5111886zbMATH OpenFDO

Authors Michael Lampis, Valia Mitsou

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2017.26

zbMATH Keywords

exponential time hypothesisquantified SATtreewidth

Mathematics Subject Classification ID

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

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

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Algorithms for propositional model counting
• Bounded-width QBF is PSPACE-complete
• Complexity and Approximability of Parameterized MAX-CSPs
• Constraint satisfaction with bounded treewidth revisited
• Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
• Fixed-parameter tractable reductions to SAT
• Model checking lower bounds for simple graphs
• Model counting for CNF formulas of bounded modular treewidth
• On the complexity of k-SAT
• Parameterized algorithms
• Parameterized complexity classes beyond para-NP
• Principles and Practice of Constraint Programming – CP 2004
• Satisfiability of acyclic and almost acyclic CNF formulas
• Solving #SAT and MAXSAT by Dynamic Programming
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The polynomial-time hierarchy
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Using decomposition-parameters for QBF: mind the prefix!
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Which problems have strongly exponential complexity?

Cited in

(19)

• Using decomposition-parameters for QBF: mind the prefix!
• Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?
• Solving projected model counting by utilizing treewidth and its limits
• Bounded-width QBF is PSPACE-complete
• Tractable QBF by knowledge compilation
• Grundy Distinguishes Treewidth from Pathwidth
• Lower Bounds for QBFs of Bounded Treewidth
• Grundy distinguishes treewidth from pathwidth
• Does Treewidth Help in Modal Satisfiability?
• Default logic and bounded treewidth
• Default logic and bounded treewidth
• Tight double exponential lower bounds
• Core stability in additively separable hedonic games of low treewidth
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Hedonic games and treewidth revisited
• Fine-grained meta-theorems for vertex integrity
• Minimum stable cut and treewidth
• Hitting meets packing: how hard can it be?
• Core stability in additively separable hedonic games of low treewidth

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)