Introduction
Many NP-hard problems, such as frequency assignment or protein structure prediction, become tractable when the underlying graph exhibits a small treewidth. The standard algorithmic approach involves constructing a tree decomposition and applying dynamic programming (DP) to solve the problem incrementally. While the theoretical complexity is exponential in the decomposition's width ($k$), practical performance often varies wildly between different decompositions of the same width. This paper, originally presented at IJCAI 2015, introduces a machine learning framework to identify high-quality decompositions, significantly reducing execution times.
The Challenge of Tree Decomposition Quality
In practice, solvers typically utilize the first tree decomposition generated by a heuristic. However, practitioners have observed that two decompositions with identical width can lead to runtimes differing by orders of magnitude. This suggests that "width" is an incomplete metric for predicting DP performance. The authors aim to move beyond width-minimization by characterizing the structural features of decompositions that influence the computational overhead of DP solvers.
Methodology: An ML-Driven Selection Pipeline
The authors propose a "select-the-best" architecture that augments the standard solving process with an intelligent selection layer.
The pipeline consists of four main stages:
- Pool Generation: A randomized min-fill heuristic quickly generates a set of ten candidate tree decompositions for a given graph.
- Feature Extraction: The system extracts 70 structural features from each decomposition. These include bag-level metrics (e.g., average bag size, connectivity within bags) and tree-level metrics (e.g., number of join nodes, vertex sharing between bags).
- Runtime Prediction: Regression models—ranging from Linear Regression to Neural Networks—are trained to predict the solver's runtime based on these features.
- Selection: The decomposition with the lowest predicted runtime is selected for the final DP execution.
Experimental Evaluation
The framework was evaluated using two DP solvers, D-FLAT and SEQUOIA, across three NP-hard domains: 3-Colorability (3-COL), Minimum Dominating Set (MDS), and Connected Vertex Cover (CVC). Training was conducted on 900 decompositions from random Erdős-Rényi graphs, while testing included both random instances and 21 real-world transit networks (e.g., metro systems in London and Vienna).
Results and Discussion
The ML-based selection strategy yielded substantial performance gains. On the D-FLAT solver, the approach reduced average runtimes by approximately 20%, with speedups exceeding 40% for specific problem-model combinations like 3-Colorability using regression trees.
Key findings include:
- Generalization: Models trained on simple random graphs performed effectively on complex real-world transit networks, particularly for the MDS problem.
- Ranking Efficacy: The success of the approach relies more on the model's ability to correctly rank candidates rather than its absolute predictive accuracy.
- Efficiency: The overhead of generating multiple decompositions and running the ML model is negligible (milliseconds) compared to the potential hours saved during DP execution.
Conclusion
By shifting the focus from problem-instance features to the structural features of the decomposition itself, this research demonstrates that machine learning can effectively bridge the gap between theoretical complexity and practical solver performance. Future work may involve integrating these ML insights directly into the decomposition construction process, moving from selection to "ML-aware" generation.
Summary updated