[Back]

J. Fichte, M. Hecher:
"Treewidth and Counting Projected Answer Sets";
Talk: LPNMR 2019 - Logic Programming and Nonmonotonic Reasoning, 15th International Conference, Philadelphia, USA; 2019-06-03 - 2019-06-07; in: "Logic Programming and Nonmonotonic Reasoning - 15th International Conference, LPNMR 2019", Springer, 11481 (2019), ISBN: 978-3-030-20527-0; 105 - 119.

In this paper, we introduce novel algorithms to solve projected
answer set counting (#PAs). #PAs asks to count the number of answer sets with respect to a given set of projection atoms, where
multiple answer sets that are identical when restricted to the projection atoms count as only one projected answer set. Our algorithms exploit small treewidth of the primal graph of the input instance by dynamic programming (DP).
We establish a new algorithm for head-cycle-free (HCF) programs and
lift very recent results from projected model counting to #PAs when the input is restricted to HCF programs. Further, we show how established DP algorithms for tight, normal, and disjunctive answer set programs can be extended to solve #PAs. Our algorithms run in polynomial time while requiring double exponential time in the treewidth for tight, normal, and HCF programs, and triple exponential time for disjunctive programs.
Finally, we take the exponential time hypothesis (ETH) into account
and establish lower bounds of bounded treewidth algorithms for #PAs.
Under ETH, one cannot significantly improve our obtained worst-case
runtimes.

Treewidth and Counting Projected Answer Sets

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

Project Head Stefan Woltran:
START