Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics

Abstract

Treewidth is a fundamental graph invariant that quantifies how tree-like

a given graph is. It is extensively used with dynamic programming to

design fixed-parameter tractable algorithms for many NP-hard graph

combinatorial optimization problems. However, despite broad theoretical

applicability, treewidth dynamic programming (TDP) does not scale in

practice beyond graphs with very small treewidth. Rather than applying

TDP as a standalone technique, we demonstrate that TDP can serve as a

broadly applicable enhancer for a wide range of graph combinatorial

optimization algorithms. Our framework leverages the concept of

treewidth modulators, which refer to vertex sets whose removal

significantly reduces the treewidth. We further propose an empirically

efficient procedure for generating such treewidth modulators. To enhance

an algorithm ?, we use ? to heuristically make decisions on the

modulators vertices, after which the remaining decisions outside the

treewidth modulators become scalable for TDP.

To demonstrate the general applicability of our proposed framework. We

experimented with three classic graph combinatorial optimization models:

Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP

to enhance algorithms across diverse paradigms, including evolutionary

search, greedy heuristics, and graph-neural-network-based heuristics.

For all combinations of optimization models and base algorithms, TDP

significantly improves performance over the original methods. In many

settings, TDP-enhanced greedy heuristics are competitive with, and

sometimes clearly outperform, state-of-the-art commercial solvers.