A Complete Anytime Algorithm for Treewidth

Vibhav Gogate, Rina DechterUAI 2004

TL;DR

This paper introduces QuickBB, a novel "anytime" algorithm for computing the exact treewidth of a graph. QuickBB significantly outperforms existing complete algorithms in terms of speed and can provide better upper bounds for challenging graphs, making it a valuable tool for AI and related fields where treewidth is a critical parameter.

What Problem Does This Paper Address?

Many powerful algorithms in Artificial Intelligence (AI), Operations Research, and other fields rely on graph decompositions, particularly tree decompositions. The efficiency of these algorithms often depends exponentially on the "treewidth" of the graph, which is a measure of how tree-like the graph is. Computing the exact treewidth is an NP-complete problem, meaning that for large graphs, finding the optimal solution can be computationally infeasible. While heuristic algorithms can quickly provide approximate treewidths, they can be exponentially inaccurate. Existing exact algorithms, like QuickTree, are often too slow for practical use on many real-world problems. This paper addresses the need for a complete (exact) algorithm that is also "anytime" – meaning it can be interrupted at any point to provide the best solution found so far – and is significantly faster than prior exact methods.

Methods

The core of QuickBB is a Branch and Bound (B&B) algorithm that searches the space of perfect elimination orderings (PEOs). A PEO is a specific ordering of vertices that, when used to triangulate a graph, results in a triangulation with the minimum possible treewidth.

Key novelties and techniques include:

  • QuickBB Algorithm: A complete anytime B&B algorithm for computing treewidth.
  • Minor-Min-Width (MMW) Lower Bound: A new lower bound for treewidth derived from graph minor theory. This bound is shown to be superior to existing lower bounds like those based on maximum cardinality search.
  • Pruning and Propagation Techniques: The algorithm incorporates advanced pruning and propagation rules, inspired by graph minor theory and graph isomorphism, to cut down the search space effectively.
  • Graph Reduction Techniques: Simplicial and almost simplicial vertex rules are used to simplify the graph at each state of the B&B search, reducing the branching factor and potentially increasing pruning opportunities.
  • Edge Addition Rule: A rule that adds edges to the graph if two vertices share a large number of common neighbors, which can create new simplicial vertices and improve pruning.
  • Anytime Property: The B&B nature allows QuickBB to be stopped at any time and return the best upper bound found so far, making it useful even when exact computation is not feasible within a given time limit.

Datasets

The paper evaluates QuickBB on several types of graphs:

  • Randomly Generated Graphs: Generated using a parametric model (n, m) where 'n' is the number of vertices and 'm' is the number of edges.
  • Randomly Generated Partial k-trees: Generated using a parametric model (n, k, p) which constructs a k-tree and then removes 'p' percent of edges.
  • Bayesian Network Repository: A collection of benchmark networks used in AI research.
  • Dimacs Graph Coloring Challenge Instances: A set of challenging graph instances from a well-known benchmark suite.

Key Insights and Ideas

  • The Power of Lower Bounds: The paper demonstrates that a strong lower bound (like MMW) is crucial for the efficiency of B&B algorithms. A better lower bound allows for more aggressive pruning of the search space.
  • Graph Minors for Treewidth: Leveraging graph minor theory provides a principled way to derive effective lower bounds and pruning rules, going beyond simpler heuristic approaches.
  • Anytime Algorithms are Practical: For NP-hard problems, anytime algorithms are often more practical than pure exact algorithms. QuickBB's ability to provide good upper bounds even when it doesn't fully terminate is a significant advantage.
  • QuickBB Outperforms QuickTree: The empirical results show a substantial speedup of QuickBB over the previously state-of-the-art complete algorithm, QuickTree, on various graph types. This suggests QuickBB is a more scalable exact treewidth algorithm.
  • Min-Fill as a Strong Heuristic: The min-fill heuristic, while not exact, consistently provides upper bounds very close to the optimal treewidth for the tested random graphs, serving as a good initial bound for the B&B search.

Key Results

  • Speedup: QuickBB is consistently faster than QuickTree. For example, on random graphs with 100 vertices and treewidth bounded by 10, QuickBB is up to 50 times faster.
  • Improved Upper Bounds: QuickBB was able to find better upper bounds on treewidth for some graphs in the Dimacs benchmarks and Bayesian Network repository, including cases where optimal treewidth was previously unknown or difficult to compute.
  • Scalability: QuickBB scales better than QuickTree, successfully computing treewidth for larger graphs (e.g., 200 vertices) and more complex partial k-trees where QuickTree failed to terminate.
  • Lower Bound Effectiveness: The MMW lower bound consistently outperformed the MCSLB (Maximum Cardinality Search Lower Bound) in empirical tests.

Limitations and Future Work

  • Time Complexity: While QuickBB is significantly faster than previous exact algorithms, its worst-case time complexity is still exponential (O(nn-k)). The authors note that QuickBB favors problems with higher treewidth and suggest future work to achieve a complexity closer to O(nk+2), which would favor problems with lower treewidth.
  • Further Empirical Testing: The authors suggest conducting more rigorous empirical tests on other benchmark suites like CSPLIB, SATLIB, and random probabilistic networks.
  • Algorithmic Improvements: Exploring further algorithmic improvements to reduce the time complexity and enhance pruning capabilities remains an open area.

Summary updated

BibTeX
@inproceedings{gogate2004complete,
  author = {Vibhav Gogate and Rina Dechter},
  title = {{A Complete Anytime Algorithm for Treewidth}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2004},
}
Figure