F. Slivovsky, S. Szeider:

"A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth";

Talk: Theory and Applications of Satisfiability Testing, Alghero, Italien; 2020-07-03 - 2020-07-10; in: "Theory and Applications of Satisfiability Testing - SAT 2020", LNCS, 12178 (2020), ISBN: 978-3-030-51824-0; 267 - 276.

The propositional model counting problem (#SAT) is known

to be fixed-parameter-tractable (FPT) when parameterized by the width

k of a given tree decomposition of the incidence graph. The running time

of the fastest known FPT algorithm contains the exponential factor of

4k. We improve this factor to 2k by utilizing fast algorithms for computing

the zeta transform and covering product of functions representing

partial model counts, thereby achieving the same running time as FPT

algorithms that are parameterized by the less general treewidth of the

primal graph. Our new algorithm is asymptotically optimal unless the

Strong Exponential Time Hypothesis (SETH) fails.

http://dx.doi.org/10.1007/978-3-030-51825-7_19

https://publik.tuwien.ac.at/files/publik_292348.pdf

Created from the Publication Database of the Vienna University of Technology.