The Impact of Treewidth on ASP Grounding and Solving

Bernhard Bliem, Marius Moldovan, Michael Morak, Stefan WoltranIJCAI 2017 · DOI

TL;DR

This paper investigates how the "treewidth" of a logic program affects the performance of Answer Set Programming (ASP) solvers. They demonstrate experimentally that higher treewidth significantly slows down solvers. To address this, they introduce "connection-guarded programs," a new class of encodings that provably limit the treewidth increase during the grounding process, leading to more efficient solving.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful declarative programming paradigm used for solving complex problems. The typical ASP solving process involves two main steps: grounding (transforming a general program into a propositional one) and solving (finding stable models of the propositional program). While significant progress has been made in solver efficiency, the influence of structural properties of the ground program on solving time has not been thoroughly explored. Specifically, the paper focuses on "treewidth," a graph-theoretic measure of how "tree-like" a program's structure is. High treewidth can indicate complex interdependencies, potentially hindering solvers. The authors aim to quantify this impact and propose a way to mitigate it through better program encoding.

Methods

The paper employs a two-pronged approach:

  1. Experimental Evaluation: They designed a specific ASP problem (deciding valid assignments in capacitated graphs) and generated instances with controlled treewidth but uniform grounding size. This allowed them to isolate the effect of treewidth on the performance of state-of-the-art ASP solvers (clasp and WASP).
  2. Theoretical Contribution: They introduce and formally define the class of "connection-guarded programs." This class is designed to ensure that the treewidth of the ground program does not grow excessively beyond the treewidth of the input instance. The proof of this property relies on Monadic Second-Order (MSO) transductions, a formal framework for describing graph transformations. They demonstrate that connection-guarded programs are expressive enough to encode problems from the second level of the polynomial hierarchy.

Datasets

The paper does not introduce new datasets in the traditional sense. Instead, they generate custom benchmark instances for their experiments. These instances are based on a specific problem (capacitated graph assignment) and are constructed to have:

  • A uniform grounding size.
  • A uniform structure.
  • Variable treewidth.
  • A controlled number of answer sets (specifically, unsatisfiable instances were used to isolate the solving time).

The instances are described as "grid-tree instances," which are combinations of grids and binary trees.

Key Insights and Ideas

  • Treewidth is a critical performance factor: The experiments clearly show a strong, almost exponential, correlation between the treewidth of a ground ASP program and the time it takes for solvers to find solutions. This means that even for programs of the same size, those with higher treewidth are significantly harder to solve.
  • Encoding matters for treewidth: The way a problem is encoded in non-ground ASP can drastically affect the treewidth of the resulting ground program. The paper provides an example where a naive encoding leads to high treewidth, while a more careful one keeps it low.
  • Connection-guarded programs offer a solution: The introduction of connection-guarded programs provides a principled way to design ASP encodings that limit the treewidth explosion during grounding. This is a significant step towards building more efficient ASP systems and models.
  • MSO transductions are a powerful tool: The paper demonstrates the utility of MSO transductions for formally analyzing how graph transformations (like ASP grounding) affect graph properties such as treewidth.

Key Results

  • Experimental: Average solving time for ASP solvers (clasp and WASP) increases drastically with the treewidth of the ground program, even when the grounding size is kept constant. For instance, running times can be substantially longer for small programs with high treewidth than for larger programs with small treewidth.
  • Theoretical: The class of connection-guarded programs is defined. It is proven that if an input instance has bounded treewidth and degree, then the ground program resulting from a connection-guarded ASP program also has bounded treewidth and degree.
  • Expressiveness: Connection-guarded programs are shown to be expressive enough to encode problems in $\Sigma_2$-complete complexity class, indicating they are not overly restrictive in terms of expressiveness.

Limitations and Future Work

  • Limitations:
    • The experimental evaluation was conducted on a specific problem (capacitated graph assignment) and a particular type of instance (grid-tree). While the results are indicative, they might not generalize perfectly to all ASP problems or instance types.
  • The theoretical proofs for connection-guarded programs rely on a simplified model of grounding. While the authors argue that state-of-the-art grounders produce subgraphs of this model (which preserves treewidth properties), this is an assumption.
  • The condition of bounded degree for the input instance is necessary for the treewidth preservation guarantee, which might limit its applicability in some scenarios.
  • Future Work:
    • Investigate alternative classes of ASP programs that also preserve small treewidth.
  • Explore the practical implications of connection-guarded programs for modeling real-world problems.
  • Further analyze the relationship between treewidth and ASP solving performance across a wider range of problems and solvers.

Summary updated

BibTeX
@inproceedings{bliem2017impact,
  author = {Bernhard Bliem and Marius Moldovan and Michael Morak and Stefan Woltran},
  title = {{The Impact of Treewidth on ASP Grounding and Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/118},
}
Figure