Treewidth in non-ground answer set solving and alliance problems in graphs

Abstract

Many practically relevant problems are at the second level of the polynomial hierarchy and thus highly intractable; yet programs solving them are often surprisingly efficient in practice even on large instances. One of the reasons is that problem instances occurring in the real world frequently have certain structural properties that sometimes allow us to avoid the worst-case running times. The goal of this thesis is to gain new insights into solving such hard problems by exploiting the structural parameter treewidth. For solving problems up to the second level of the polynomial hierarchy, Answer Set Programming (ASP) has become popular due to its convenient language and efficient solvers. In ASP, the usual workflow is to write an ASP encoding for a problem and transform it together with a problem instance into a so-called ground program, which is then given to a solver that computes the solutions. Recent work has shown that the performance of state-of-the-art ASP solvers benefits greatly from the ground program having small treewidth. Unfortunately grounding, that is, the transformation of the instance into a ground program, is a complicated, implementation-dependent task, so it is not clear under which circumstances the ground program has small treewidth. The influence of grounding on the treewidth has largely been neglected in research so far. A particularly interesting class of graph problems for research on ASP are alliance problems. These ask for groups of vertices that help each other out in a certain way. Some alliance problems are at the second level of the polynomial hierarchy and require advanced modeling techniques for encoding them in ASP. However, important alliance problems lacked a complexity analysis, in particular with regard to treewidth. Our contributions are the following: We show how ASP users can take advantage of small treewidth implicitly, that is, without having to write a program that deliberately exploits treewidth. For this, we define classes of non-ground ASP programs that guarantee that grounding preserves bounded treewidth. Moreover, we present a methodology for designing algorithms that explicitly take treewidth into account. This is especially targeted at problems at the second level of the polynomial hierarchy and can substantially improve performance compared to naive approaches. We illustrate some of our techniques for alliance problems in graphs, where we also settle several long-standing questions regarding complexity.