[Back]

J. Fichte, M. Hecher:
"Counting with Bounded Treewidth: Meta Algorithm and Runtime Guarantees";
Talk: NMR 2020 - 18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING, Rhodes, Greece; 2020-09-12 - 2020-09-18; in: "18th INTERNATIONAL WORKSHOP ON NON-MONOTONIC REASONING", (2020), 9 - 18.

In this paper, we present a meta result to construct algorithmsfor solution counting in various formalisms in knowledge rep-resentation and reasoning (KRR). Our meta algorithm em-ploys small treewidth of the input instance, which yieldspolynomial-time solvability in the input size for instancesof bounded treewidth when considering variousdecision prob-lemsin graph theory, reasoning, and logic. For many results,there are explicit dynamic programming algorithms or resultsbased on the well-known Courcelle´s theorem that allow todecide a problem in time linear in the input size and somefunction in the treewidth. We follow this line of research,however, consider a much more elaborate question: countingandprojected solution counting (PSC). PSC is a natural gener-alization to counting all solutions where we consider multipleindistinguishable solutions as one single solution.Our meta result allows to extend already existing given dy-namic programming (DP) algorithms by introducing only asingle-exponential blowup in the runtime on top of the ex-isting DP algorithm. The technique is widely applicable forproblems in KRR. Exemplarily, we present an application toprojected solution counting on QBFs, which often also servesas a canonical counting problem for the polynomial hierarchy.Finally, we present a list of problems on which our result isapplicable and where the single-exponential blowup causedby the approach cannot be avoided under ETH (exponentialtime hypothesis). This completes the picture of recently ob-tained results in argumentation, answer set programming, andepistemic logic programming.

Project Head Stefan Woltran:
START