Introduction
Tree decomposition is a cornerstone of graph theory, providing a structural framework to solve complex combinatorial problems efficiently. The goal is to minimize the treewidth, a measure of how "tree-like" a graph is. While finding the optimal treewidth is NP-hard, the state-of-the-art TW-SLIM approach uses SAT solvers to iteratively improve existing decompositions. However, TW-SLIM's performance is highly dependent on its configuration parameters, which often need to change as the decomposition evolves.
The Problem: Evolving Instances
Standard algorithm configuration tools assume a static problem instance. In the context of local search for tree decomposition, the "instance" is the current decomposition itself. As the solver reduces the treewidth, the characteristics of the graph—and thus the optimal SAT solver settings—shift. A configuration that is effective at the start of the process may become inefficient or even counterproductive as the decomposition becomes "thinner."
Methods: From Clustering to Cascades
To address the "evolving instance" problem, the authors developed the Iterative Cascading Policy (ICP). This multi-stage approach bridges the gap between offline learning and real-time adaptation.
1. Clustering-Based Offline Configuration (CC)
The researchers first used SMAC (a Bayesian optimization tool) to identify high-performing configurations across a diverse training set of 2,664 graphs. Using constrained K-means clustering based on features like bag size and graph density, they grouped these instances into 30 distinct clusters to capture the variety of problem structures.
2. The Iterative Cascading Policy (ICP)
The core innovation is the organization of these 30 cluster-optimized configurations into a cascade—a prioritized linear sequence.
- Execution: The solver attempts configurations in the cascade one by one.
- Reset: If a configuration successfully improves the decomposition, the "best-so-far" solution is updated, and the solver restarts the cascade from the beginning.
- Dynamic Adaptation (ICP-dyn): In its most advanced form, the policy re-sorts the cascade order after every improvement based on the updated features of the new decomposition.
Key Results and Insights
The ICP approach was evaluated against a benchmark of over 3,000 graphs from sources like PACE challenges and road networks. The results demonstrate a significant leap in performance:
- Performance Boost: At a 7,800-second timeout, the ICP-sta method achieved a total width reduction ($T\Sigma$) of 728, representing an 82.9% improvement over the hand-tuned defaults of TW-SLIM (398).
- Efficiency: ICP variants outperformed standard portfolio selectors like AutoFolio by roughly 40%, highlighting the advantage of the iterative cascading structure over one-shot selection.
- Robustness: The system proved effective even at short timeouts (100s), quickly identifying "low-hanging fruit" improvements.
Conclusion
The success of the Iterative Cascading Policy underscores the importance of accounting for evolving problem instances in local search. By combining structured trial-and-error with offline clustering, ICP provides a robust framework for optimizing complex, multi-parameter solvers. Future research may explore the application of ICP to other Large Neighborhood Search (LNS) frameworks to determine if these benefits generalize across different combinatorial domains.
Summary updated