Model counting for formulas of bounded clique-width

DOI10.1007/978-3-642-45030-3_63MaRDI QIDQ2872132zbMATH OpenOpenAlexFDO

Authors Friedrich Slivovsky, Stefan Szeider

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We show that #SAT is polynomial-time tractable for classes of CNF formulas whose incidence graphs have bounded symmetric clique-width (or bounded clique-width, or bounded rank-width). This result strictly generalizes polynomial-time tractability results for classes of formulas with signed incidence graphs of bounded clique-width and classes of formulas with incidence graphs of bounded modular treewidth, which were the most general results of this kind known so far.

Recommendations

• Model counting for CNF formulas of bounded modular treewidth
• Model counting for CNF formulas of bounded modular treewidth
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Solving \#SAT using vertex covers
• Solving #SAT Using Vertex Covers

Cited in

(12)

• Complexity and approximability of parameterized MAX-CSPs
• Solving \#SAT using vertex covers
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Better algorithms for satisfiability problems for formulas of bounded rank-width
• Model counting for CNF formulas of bounded modular treewidth
• Model counting for CNF formulas of bounded modular treewidth
• On compiling CNFs into structured deterministic DNNFs
• Sum-of-Products with Default Values: Algorithms and Complexity Results
• Tractable QBF by knowledge compilation
• A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
• Solving #SAT Using Vertex Covers
• Direct access for conjunctive queries with negations

This page was built for publication: Model counting for formulas of bounded clique-width

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