A Practical Algorithm for Finding Optimal Triangulations

AAAI 1997

TL;DR

This paper introduces QUICKTREE, a novel algorithm for finding optimal triangulations of graphs. This is crucial for efficiently solving complex problems in AI, such as Bayesian network inference and constraint satisfaction, by reducing the computational complexity associated with these tasks.

What Problem Does This Paper Address?

Many problems in Artificial Intelligence, like Bayesian network inference and constraint satisfaction, become computationally intractable on general graphs. A common strategy to make these problems tractable is to transform the input graph into a "triangulated" or "chordal" graph. This process, called triangulation, adds edges to the original graph to eliminate chordless cycles longer than three. However, not all triangulations are created equal. The "optimal triangulation" is one that minimizes the size of its largest clique (a complete subgraph). The size of this largest clique minus one is known as the treewidth of the graph, a fundamental measure of its complexity. Finding an optimal triangulation is an NP-complete problem, and existing algorithms are either impractical for moderately sized graphs or have exponential time complexity in the treewidth. This paper addresses the need for a practical algorithm that can find optimal triangulations for graphs of realistic sizes, which were previously computationally prohibitive.

Methods

The paper introduces an algorithm called QUICKTREE that employs a dynamic programming approach to construct optimal triangulations. The core idea is to break down the problem into smaller, manageable subproblems (fragments of the graph) and then combine their optimal triangulations to build up the optimal triangulation of the entire graph.

Key methodological aspects include:

  • Dynamic Programming with Simultaneous Composition: Unlike previous methods that used "simple composition," QUICKTREE uses "simultaneous composition." This involves identifying "k-regular sets of separators" (sets of minimal separators with specific properties) and combining optimal triangulations of the resulting fragments and a "base clique."
  • Fragment Generation: The algorithm first identifies minimal separators of the graph with a size up to the target treewidth k. These separators are then used to define "fragments" of the graph.
  • Validity Graph and Maximal Cliques: To find k-regular sets of separators, the algorithm constructs a "validity graph." Maximal cliques in this validity graph correspond to k-regular sets of separators.
  • Heuristics for Phase 1: To improve the performance of the initial phase (finding minimal separators), the authors employ two heuristics: ignoring separators whose clique is already formed and ordering vertex pairs by decreasing mutual distance.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetically generated graphs for evaluation. These graphs are created by:

  • Starting with a random clique tree where all maximal cliques have the same size.
  • Randomly dropping 30%, 40%, or 50% of the edges. This generation method ensures that the graphs have a bounded treewidth, allowing the authors to test their algorithm on graphs where an optimal triangulation is known to exist within a certain size.

Key Insights and Ideas

  • Practicality for Moderate Treewidths: The most significant insight is that QUICKTREE makes finding optimal triangulations practical for graphs with treewidths up to 10 and up to 100 nodes, a significant improvement over prior methods.
  • Bottleneck Identification: The experiments reveal that the most time-consuming part of the algorithm is Phase 1, which involves finding all minimal separators. This highlights an area for future optimization.
  • Heuristics Improve Performance: The introduced heuristics for finding minimal separators significantly improve the algorithm's practical performance, even though the theoretical complexity of Phase 1 remains high.
  • Simultaneous Composition Efficiency: The paper demonstrates that simultaneous composition, a more complex combination strategy, is effective and necessary for achieving optimal triangulations in practical scenarios.

Key Results

  • QUICKTREE successfully triangulated graphs with up to 100 nodes and a treewidth of 10 in a reasonable time frame.
  • For graphs with 100 nodes and 30% edge dropout (treewidth 10), the algorithm took over 10 hours, indicating the practical limit of their current implementation.
  • The algorithm's performance is highly dependent on the number of minimal separators. Graphs with fewer minimal separators are processed much faster.
  • The experimental results show that the number of minimal separators needed for the dynamic programming phase (Rk) is often much smaller than the total number of minimal separators found (R).

Limitations and Future Work

  • Phase 1 Bottleneck: The primary limitation acknowledged is the computational cost of Phase 1 (finding minimal separators), which remains a bottleneck for larger graphs.
  • Improving Separator Finding: The authors suggest that developing a more efficient algorithm for generating minimal separators of size at most k could significantly improve QUICKTREE's overall performance.
  • Extending to Other Applications: The paper notes that the algorithm can be modified to accommodate variants of the optimization problem, such as minimizing weighted sums of clique sizes, which is relevant for Bayesian network inference.
  • Availability of Code: The authors mention that their code is under development and will be made available, facilitating further research and application.

Summary updated

BibTeX
@inproceedings{1997practical,
  title = {{A Practical Algorithm for Finding Optimal Triangulations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure