[Back]

M. Bichler, B. Bliem, M. Moldovan, M. Morak, S. Woltran:
"Treewidth-Preserving Modeling in ASP";
Report No. DBAI-TR-2016-97, 2016; 37 pages.

For ground ASP programs where an appropriate graph representation has bounded treewidth, algorithms that exploit this bound on the treewidth theoretically only require linear time for checking existence of an answer set. However, in practice such algorithms are hardly competitive against state-of-the-art CDCL-based solvers, which do not explicitly rely on bounded treewidth. In this work we investigate the hypothesis that CDCL-based solvers leverage small treewidth implicitly. We identify modeling constructs in non-ground ASP that signi cantly blow up the treewidth in the grounding and we give guidelines for modeling problems in non-ground ASP such that grounding preserves small treewidth of the input. We also experimentally show that a non-ground rule decomposition technique can decrease the treewidth of the grounding substantially. Finally, we identify a class of non-ground ASP programs that preserves bounded treewidth in the sense that the treewidth of the grounding only depends on the treewidth and the degree of the input graph instead of its size.

Project Head Stefan Woltran:
START