2010/06/29 by Robert Ganian, Ganian, Robert, Petr Hliněný +4
Computer Science · #Advanced Graph Theory Research #Bayesian Modeling and Causal Inference #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Machine Learning and Algorithms #cs.DM #cs.LO
paper · pdf · doi:10.48550/arxiv.1006.5621
arxiv created 2010/06/29 · openalex publication_date 2010/06/29 · arxiv updated 2010/06/30 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
We provide a parameterized polynomial algorithm for the propositional model\ncounting problem #SAT, the runtime of which is single-exponential in the\nrank-width of a formula. Previously, analogous algorithms have been known --≠.g.~[Fischer, Makowsky, and Ravve] -- with a single-exponential dependency on\nthe clique-width of a formula. Our algorithm thus presents an exponential\nruntime improvement (since clique-width reaches up to exponentially higher\nvalues than rank-width), and can be of practical interest for small values of\nrank-width. We also provide an algorithm for the MAX-SAT problem along the same\nlines.\n