Author: Slivovsky, Friedrich; Szeider, Stefan
Title: A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth Cord-id: qqwxt1se Document date: 2020_6_26
ID: qqwxt1se
Snippet: 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 [Formula: see text]. We improve this factor to [Formula: see text] by utilizing fast algorithms for computing the zeta transform and covering product of functions representing partial model counts, thereby achieving the same runni
Document: 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 [Formula: see text]. We improve this factor to [Formula: see text] 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.
Search related documents:
Co phrase search for related documents- Try single phrases listed below for: 1
Co phrase search for related documents, hyperlinks ordered by date