[Back]

M. Hecher, J. Fichte:
"Exploiting Treewidth for Counting Projected Answer Sets";
Talk: International Workshop on Non-Monotonic Reasoning (NMR), Tempe, Arizona, USA; 2018-10-27 - 2018-10-29; in: "17th International Workshop on Non-Monotonic Reasoning (NMR)", AAAI Press, (2018), 1 - 10.

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 projected atoms, where multiple answer sets that are identical when restricted to the projected 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 programs and lift very recent results from projected model counting to #PAS when the input is restricted to head-cycle-free programs. Further, we show how established DP algorithms for disjunc-tive answer set programs can be extended to solve #PAS. Our algorithms run in time double exponential for head-cycle-free programs and triple exponential in the treewidth for disjunctive programs and polynomial in the input size of the instance. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algo-rithms for #PAS. In particular, one can not expect (under ETH) to solve #PAS for head-cycle-free or disjunctive programs in polynomial time in the instance size while being single or double exponential in the treewidth, respectively.

Project Head Stefan Woltran:
START