Enumerating Potential Maximal Cliques via SAT and ASP

Tuukka Korhonen, Jeremias Berg, Matti JärvisaloIJCAI 2019 · DOI

TL;DR

This paper proposes using declarative solvers (SAT and ASP) to enumerate "potential maximal cliques" (PMCs), a crucial but computationally expensive step in algorithms for computing graph treewidth and generalized hypertreewidth. By replacing specialized PMC enumeration with these constraint-based methods, the authors achieve significant speedups, particularly with a novel lazy SAT approach, making these graph-theoretic computations more practical.

What Problem Does This Paper Address?

Computing the treewidth of a graph is a fundamental problem in graph theory with applications in areas like constraint satisfaction, knowledge representation, and probabilistic reasoning. While exact algorithms exist, determining treewidth is NP-hard. A prominent exact algorithm, the Bouchitté-Todinca (BT) algorithm, relies on dynamic programming over "potential maximal cliques" (PMCs). However, enumerating these PMCs is a known bottleneck, especially for certain graph structures like "melon graphs," where the number of PMCs can grow exponentially. This limits the practical applicability of the BT algorithm. The paper aims to overcome this bottleneck by exploring declarative approaches (SAT and ASP) for PMC enumeration, which can potentially handle these challenging cases more efficiently.

Methods

The core contribution is the development and evaluation of three declarative approaches for enumerating PMCs:

  • Direct SAT Encoding: This method translates the conditions for a set of vertices to be a PMC into a Boolean Satisfiability (SAT) problem. It uses propositional variables to represent vertex inclusion in a potential PMC and auxiliary variables to encode connectivity constraints.
  • Direct ASP Encoding: Similar to the SAT approach, this method uses Answer Set Programming (ASP) to encode the PMC conditions. ASP's declarative nature and built-in support for cardinality constraints are leveraged.
  • Lazy SAT Approach: This is a novel hybrid approach. It starts with a basic SAT encoding of PMC conditions and iteratively adds constraints related to minimal separators of the graph. When the SAT solver finds a candidate set of vertices that is not a PMC, it identifies a "violating pair" and uses a minimal separator to rule out this candidate and similar ones in future iterations. This lazy addition of constraints is key to its efficiency.

These declarative methods are integrated into an iterative variant of the BT algorithm. Instead of enumerating all PMCs at once, this iterative approach enumerates PMCs of increasing size (up to a bound related to the treewidth) as needed by the dynamic programming phase. This is particularly beneficial for graphs with low treewidth.

Datasets

The paper evaluates its methods on:

  • Melon Graphs: These are synthetically generated graphs specifically designed to exhibit exponential growth in the number of minimal separators and PMCs. They are used to demonstrate the scalability limitations of traditional methods and the improvements offered by the declarative approaches.
  • Benchmark Instances: The authors use a collection of 589 graphs for treewidth and 265 for generalized hypertreewidth from various sources, including the PACE 2016 and 2017 challenges. These represent a diverse set of real-world and challenging graph structures.

Key Insights and Ideas

  • PMC Enumeration as a Bottleneck: The paper clearly establishes that PMC enumeration is the primary performance bottleneck in the Bouchitté-Todinca algorithm for treewidth and generalized hypertreewidth.
  • Declarative Solvers as a Viable Alternative: SAT and ASP solvers, traditionally used for different problem classes, can be effectively adapted to solve the PMC enumeration problem, offering a more flexible and potentially more efficient alternative to specialized algorithms.
  • The Power of Laziness: The lazy SAT approach, which incrementally adds constraints based on minimal separators only when a violation is detected, significantly outperforms the direct SAT and ASP encodings and the original specialized PMC enumeration algorithm, especially on challenging instances.
  • Iterative BT for Efficiency: Combining declarative PMC enumeration with an iterative BT algorithm (which only enumerates PMCs up to a certain size as needed) provides a substantial performance boost, particularly for graphs with low treewidth.
  • Generalization to Hypergraphs: The core ideas are shown to be adaptable to generalized hypertreewidth by modifying the PMC definition to consider edge covers instead of just vertex counts.

Key Results

  • Melon Graph Performance: The original PMC enumeration struggled with melon graphs beyond n=10. The lazy SAT approach could determine treewidth for n=200 within 7.5 minutes, demonstrating a dramatic improvement.
  • Benchmark Instance Performance: On a large set of benchmark graphs, the lazy SAT approach solved 343 treewidth instances compared to 308 solved by the original Triangulator implementation. ASP also showed improvement over the original method. Direct SAT was found to be not competitive.
  • Scalability: The lazy SAT and ASP methods could determine treewidth for graphs with up to 559 nodes, whereas the direct SAT method was limited to 125 nodes.
  • Minimal Separator Insight: The lazy SAT approach's effectiveness is visualized by showing that it enumerates far fewer minimal separators than the total number of minimal separators in the graph, highlighting its targeted search.

Limitations and Future Work

  • Direct SAT Limitations: The direct SAT encoding was found to be less competitive than the other declarative approaches, likely due to the complexity of encoding path existence and connectivity.
  • Future Work: The authors suggest that further improvements in SAT and ASP solvers could lead to even greater efficiency gains. They also highlight that harnessing declarative solvers opens up new avenues for improving triangulation-based graph optimization problems. The paper implicitly suggests that exploring more sophisticated lazy or iterative strategies could yield further benefits.

Summary updated

BibTeX
@inproceedings{korhonen2019enumerating,
  author = {Tuukka Korhonen and Jeremias Berg and Matti Järvisalo},
  title = {{Enumerating Potential Maximal Cliques via SAT and ASP}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/156},
}
Figure