Better algorithms for satisfiability problems for formulas of bounded rank-width

• Autoři: GANIAN Robert; HLINĚNÝ Petr; OBDRŽÁLEK Jan
• Rok publikování: 2010
• Druh: Článek ve sborníku
• Konference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
• Fakulta / Pracoviště MU: Fakulta informatiky

www

• DOI
• http://www.fsttcs.org/

• Doi: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.73
• Obor: Informatika
• Klíčová slova: propositional model counting; satisfiability; rank-width; clique-width; parameterized complexity
• Popis: 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.

Související projekty

• Vysoce paralelní a distribuované výpočetní systémy
• Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
• Strukturální teorie grafů a parametrizovaná složitost
• Parameterized Algorithms and Width measures on Graphs
• Rozsáhlé výpočetní systémy: modely, aplikace a verifikace