Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-51825-7_19
Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_292348.pdf
Created from the Publication Database of the Vienna University of Technology.