Ganian, R., Pokrývka, F., Schidler, A., Simonov, K., & Szeider, S. (2022). Weighted Model Counting with Twin-Width. In K. S. Meel & O. Strichman (Eds.), 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) (pp. 1–17). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAT.2022.15
25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)
2-Aug-2022 - 5-Aug-2022
Number of Pages:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl
parameterized complexity; SAT; twin-width; weighted model counting
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, including treewidth and clique-width. In this paper, we investigate the use of twin-width for solving the propositional satisfiability problem (SAT) and propositional model counting. We particularly focus on Bounded-ones Weighted Model Counting (BWMC), which takes as input a CNF formula F along with a bound k and asks for the weighted sum of all models with at most k positive literals. BWMC generalizes not only SAT but also (weighted) model counting. We develop the notion of “signed” twin-width of CNF formulas and establish that BWMC is fixed-parameter tractable when parameterized by the certified signed twin-width of F plus k. We show that this result is tight: it is neither possible to drop the bound k nor use the vanilla twin-width instead if one wishes to retain fixed-parameter tractability, even for the easier problem SAT. Our theoretical results are complemented with an empirical evaluation and comparison of signed twin-width on various classes of CNF formulas.
Parameterisierte Analyse in der Künstlichen Intelligenz: Y1329-N (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) New Frontiers for Parameterized Complexity: P31336-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) SAT-Basierende lokale Verbesserungsmethoden: P32441-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)