AAAI Publications, Sixteenth International Conference on Principles of Knowledge Representation and Reasoning

Font Size: 
Exploiting Treewidth for Counting Projected Answer Sets
Johannes K. Fichte, Markus Hecher

Last modified: 2018-09-24

Abstract


Answer Set Programming (ASP) is an active research area of artificial intelligence. We consider the problem projected answer set counting (#PDA) for disjunctive propositional ASP. #PDA 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 approach exploits small treewidth of the primal graph of the input instance. Finally, we state a hypothesis (3ETH) that one cannot solve 3-QBF in polynomial time in the instance size while being significantly better than triple exponential in the treewidth. Taking 3ETH into account, we show that one can not expect to solve #PDA significantly better than triple exponential in the treewidth.

Keywords


Parameterized Algorithms;Tree Decompositions;Multi-Pass Dynamic Programming;Projected Answer Set Counting;Answer Set Programming

Full Text: PDF