Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Model counting for CNF formuals of bounded module treewidth
Paulusma, D.; Slivovksy, F.; Szeider, S.
Authors
F. Slivovksy
S. Szeider
Contributors
Natacha Portier
Editor
Thomas Wilke
Editor
Abstract
The modular treewidth of a graph is its treewidth after the contraction of modules. Modular treewidth properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments of a CNF formula whose incidence graph has bounded modular treewidth can be computed in polynomial time. This provides new tractable classes of formulas for which #SAT is polynomial. In particular, our result generalizes known results for the treewidth of incidence graphs and is incomparable with known results for clique-width (or rank-width) of signed incidence graphs. The contraction of modules is an effective data reduction procedure. Our algorithm is the first one to harness this technique for #SAT. The order of the polynomial time bound of our algorithm depends on the modular treewidth. We show that this dependency cannot be avoided subject to an assumption from Parameterized Complexity.
Citation
Paulusma, D., Slivovksy, F., & Szeider, S. (2013). Model counting for CNF formuals of bounded module treewidth. In N. Portier, & T. Wilke (Eds.), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (55-66). https://doi.org/10.4230/lipics.stacs.2013.55
Conference Name | 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) |
---|---|
Conference Location | Kiel, Christian-Albrechts-Universität zu Kiel, Germany |
Publication Date | Jan 1, 2013 |
Deposit Date | Mar 11, 2013 |
Publicly Available Date | Mar 29, 2024 |
Pages | 55-66 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series Number | 20 |
Series ISSN | 1868-8969 |
Book Title | 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). |
ISBN | 9783939897507 |
DOI | https://doi.org/10.4230/lipics.stacs.2013.55 |
Keywords | Satisfiability, Model Counting, Parameterized Complexity. |
Public URL | https://durham-repository.worktribe.com/output/1156230 |
Additional Information | Conference dates: Feb 27–Mar 2, 2013 |
Files
Published Conference Proceeding
(646 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nd/4.0/
Copyright Statement
This article is available under a CC-BY-ND licence. See http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search