2026-07-25T15:15:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2854 2024-03-06T10:33:36Z ddc:004 open_access

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width Ganian, Robert Hlinený, Petr Obdrzálek, Jan propositional model counting; satisfiability; rank-width; clique-width ; parameterized complexity We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known --e.g. [Fischer, Makowsky, and Ravve]-- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian and Petr Hlinený and Jan Obdrzálek 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.73 urn:nbn:de:0030-drops-28541 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.73 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode