The Impact of Treewidth on ASP Grounding and Solving

The Impact of Treewidth on ASP Grounding and Solving

Bernhard Bliem, Marius Moldovan, Michael Morak, Stefan Woltran

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 852-858. https://doi.org/10.24963/ijcai.2017/118

In this paper, we aim to study how the performance of modern answer set programming (ASP) solvers is influenced by the treewidth of the input program and to investigate the consequences of this relationship. We first perform an experimental evaluation that shows that the solving performance is heavily influenced by the treewidth, given ground input programs that are otherwise uniform, both in size and construction. This observation leads to an important question for ASP, namely, how to design encodings such that the treewidth of the resulting ground program remains small. To this end, we define the class of connection-guarded programs, which guarantees that the treewidth of the program after grounding only depends on the treewidth (and the degree) of the input instance. In order to obtain this result, we formalize the grounding process using MSO transductions.
Keywords:
Knowledge Representation, Reasoning, and Logic: Automated Reasoning and Theorem Proving
Knowledge Representation, Reasoning, and Logic: Non-monotonic Reasoning