---
title: "Taming Treewidth DP with Modulators: A General Booster for Graph Heuristics"
authors:
  - "Jialiang Li"
  - "Aneta Neumann"
  - "Frank Neumann"
  - "Hung Nguyen"
  - "Mingyu Guo"
doi: "10.24963/ijcai.2026/701"
url: "https://ijcai.org/proceedings/2026/701"
pdf: "https://ijcai.org/proceedings/2026/0701.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "6299-6307"
track: "Main Track"
keywords:
  - "Search: Combinatorial search and optimisation"
  - "Search: Search and machine learning"
  - "Search: Heuristic search"
---

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

Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen, Mingyu Guo

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 6299-6307. DOI: [10.24963/ijcai.2026/701](https://doi.org/10.24963/ijcai.2026/701)

## 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.