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

1 Introduction

Treewidth (TW) is a prominent graph invariant that measures the similarity between a given graph and an exact tree, whose value can be calculated via a tree decomposition process. Many NP-hard graph combinatorial optimization problems become easy for special graph instances with small treewidths.

According to the well-known Courcelle's Theorem [Courcelle, 1990], there is a general way to construct treewidth dynamic programs (TDP) [Downey et al., 2013] that can optimally solve a wide spectrum of hard graph problems in linear time for graphs with bounded treewidths. These problems include but are not limited to independent set, vertex cover, 3-coloring, TSP and etc [Bodlaender, 1988]. These problems are referred to as fixed-parameter tractable parameterized by treewidth. Their time complexities are of the form O(f(TW) · n), where f(TW) is a constant factor generally exponential in TW when it comes to NP-hard problems. 1 That is, despite its general applicability and the impressive "linear" time complexity, TDP is practically not scalable, unless we restrict to special graph instances with tiny treewidths.

We take the Maximum Independent Set (MIS) as an example. There exists a treewidth dynamic program with complexity O(2TW n). Going by real-world graphs [Maniu et al., 2019], for a power network with treewidth 10, the above TDP is certainly scalable. For a road network with treewidth 50, the above TDP becomes not scalable due to the large constant factor 250 . Again, it is expected that TDP is not scalable, as MIS is, after all, an NP-hard problem.

In summary, the advantage of TDP is its broad applicability and its disadvantage is its limited practically scalability. Instead of applying TDP as a standalone technique, we propose to apply TDP to enhance existing graph optimization algorithms. We employ the concept of treewidth modulator. It is a vertex deletion problem [Lewis and Yannakakis, 1980], with the goal of deleting as few vertices as possible to bring down the treewidth to below a desired threshold (i.e., to a threshold that makes TDP scalable). Our usage of treewidth modulator certainly does not involve actually deleting any vertices, as otherwise that would be modifying the original optimization model and/or the solution space. We use the treewidth modulator as a backdoor [Williams et al., 2003], which is a concept borrowed from SAT (Boolean satisfiability). For SAT, it is known that hard instances can become much easier by fixating assignments to a small subset of variables. The assignments for reducing computational difficulty are called the backdoor. We apply TDP to enhance an existing graph optimization algorithm A as follows. (Our approach is broadly applicable to many optimization models, which is why our presentation intentionally avoids referencing a specific model. The readers are welcome to adopt Maximum Independent Set as an example, if it aids in understanding.) We use A to make decisions within the treewidth modulator. We refer to these decisions as the advice string, which serves to significantly reduce the TDP search space (i.e., it is the "backdoor" to TDP). We propose a modified version of TDP that takes as input an advice string, and focuses on generating the decisions outside of the treewidth modulator, which is scalable (as it is effectively equivalent to working on the remaining graph after vertex deletion). Essentially, our modified version of TDP produces the optimal solution conditional on the advice string. The above interpretation also shows that for any existing algorithm A, the TDP enhanced version of A never performs worse than A itself in terms of solution quality.

1 For O(f(TW) · n), if f is polynomial in TW, then the whole expression becomes polynomial in n as TW < n.

1.1 Summary of contributions

• We propose a general framework on using TDP to enhance existing graph combinatorial optimization algorithms. We experimented on three different graph optimization models, including Maximum Independent Set, Minimum Vertex Cover, and Max Cut. We apply TDP to enhance algorithms following a variety of paradigms, including (1+1)EA evolutionary algorithm, greedy, and graph neural networks based heuristics. For all combinations of optimization models and existing algorithms, TDP significantly enhances the existing algorithms.
• Our framework builds on the efficient generation of treewidth modulators. Optimal treewidth modulator generation is known to be notoriously difficult. We propose a scalable variant called Optimal Treewidth Modulator on a Given Tree Decomposition. We prove that our variant is still NP-hard, but it is empirically cheap, costing only 1 second on average in our experiments.
• For easy graph datasets, TDP enhanced (1+1)EA almost always reaches the optimal solution, and it is significantly superior to standalone (1+1)EA in terms of wall-clock time and number of iterations before hitting optimality.
• In many scenarios with hard graph datasets, TDP enhanced greedy heuristics are competitive with, and sometimes clearly outperform, the solutions by GUROBI. Our pure Python implementation manages to reach better solutions while using less time than GUROBI.
• TDP enhanced graph neural networks based heuristics outperform standalone graph neural networks based heuristics. Furthermore, we observe the following common phenomenon in training. The network quickly stagnates on decisions within the treewidth modulator. Effectively, we have already entered into a local optimum. Afterwards, there is a prolonged period of minor improvements on decisions outside the treewidth modulator. That is, judging by the cost function, it is decreasing and therefore appears to be learning. However, the decisions outside the treewidth modulator are not worth the training efforts as they can be optimally and efficiently derived via TDP. In other words, our framework can function as an early detection test to prevent such wasteful training.

RelatedWork. Treewidth modulator is related to the forbidden minor problem, which has been extensively studied in the parameterized complexity community [Cygan et al., 2011; Baste et al., 2020; Jansen et al., 2021]. To the best of our knowledge, efficient algorithms for acquiring optimal treewidth modulators appear highly improbable by many conjectures [Baste et al., 2020]. Even the fixed-parameter tractable results are based on the precondition of finite graph collections, but yet, exhibit a superexponential growth rate. The progress on treewidth modulators serves more for theoretical interests. In this paper, we do not pursue the exact calculation of treewidth modulators. Instead, we adopt a more practical approach by proposing an empirically scalable heuristic. Despite the resemblance between treewidth modulator and strong backdoor, the difference has already been clarified in [Fomin et al., 2015]. In terms of algorithm design, other research focused on parameterized approximation scheme [Lampis, 2013], which shares the same interest on accelerating treewidth dynamic programming, but via algebraic operations and non-trivial hand-crafted rules.

2 Preliminary

In this paper, we follow the standard notations and terminologies in graph theory and parameterized complexity. Contents marked by (⋆) are deferred to the appendix.

Notations. Given a graph G = (V,E), we note |V | = n, |E| = m. We define the induced subgraph by a subset S ⊆ V as G[S]. The neighbors of a vertex or a set of vertices are denoted by N[·] (inclusion-wise) and N(·) (exclusion-wise). We define the boundary of S as ∂G(S) = {v ∈ S : ∃u ∈ V \ S, (u, v) ∈ E}. We focus on vertex selection problems, which involve searching for a solution within the binary combinatorial space 2n . We represent an arbitrary assignment within the space as s ∈ 2n . Unless otherwise specified, we assume maximization objective, such as maximizing the number of vertices selected subject to feasibility.

We start by introducing a few relevant concepts from parameterized complexity:

Definition 1 (Fixed-parameter Tractable). For a problem L ⊆ Σ∗ ×N, if there exists an algorithm A that can determine whether an instance (x, k) ∈ Σ∗ ×N in time f(k) · |x|O(1) , where f is a computable function, then the problem is fixedparameter tractable (FPT) parameterized by k.

In our context, we focusing on using the treewidth (TW) as the parameter, which is formally defined below. We say a graph combinatorial optimization problem is FPT parameterized by TW if we have an algorithm with complexity O(f(TW) · nO(1) ). That is, if the graph instances have bounded treewidths, then the algorithm is polynomial-time.

Definition 2 (Tree Decomposition [Cygan et al., 2020]). A tree decomposition is a mapping from G to a pair T = (T, {Xt}t∈V (T)), where T is a tree and every tree node t ∈ V (T) corresponds to a subset of vertices from the original graph, denoted as Xt ⊆ V (G). Xt is often referred to as a bag. For valid tree decomposition, we must have:

• The union of all bags contains all the vertices from the original graph: ⋃︁t∈V (T ) Xt = V (G);

• For any edge (u, v) in the original graph, there must exist at least one bag that contains both u and v: ∀(u, v) ∈ E(G), ∃t ∈ T with {u, v} ⊆ Xt;
• For any vertex u from the original graph, all bags containing u must form a subtree of T : ∀u ∈ V (G), Tu = {t ∈ V (T )|u ∈ Xt} is a connected component of T .

The width of a tree decomposition T = (T, {Xt}t∈V (T)) is defined by

The optimal treewidth of a graph G is denoted by TW∗ , which is the minimum width of all valid tree decompositions of G. We denote the tree decomposition producing the minimum treewidth as T ∗ .

It should be noted that the computation of the minimum treewidth is proven NP-hard [Robertson and Seymour, 1984], hard to approximate [Wu et al., 2014], and hard even for special graph classes [Bodlaender et al., 2023]. For practical purposes, treewidth dynamic programming does not require the minimum treewidth. It can be based on sub-optimal treewidth values obtained via polynomial-time tree decomposition heuristics. In our presentation, treewidth refers to a heuristically generated value.

The following theorem proves that bounded treewidth implies linear-time algorithms for many problems.

Theorem 1 (Courcelle's Theorem [Courcelle, 1990]). Given a monadic second order logic (MSO) formula φ, and a graph instance G. Then, there exists a linear-time algorithm (in time f(|φ|, k)) to decide if G satisfies φ if TW(G) is bounded by k.

Problems such as 3-coloring, Hamiltonian cycle, independent set, and vertex cover are all expressible by MSO. According to the above theorem, they all are linear-time solvable for graph instances with bounded treewidths. There is also a systematic way to construct treewidth dynamic programs for these problems. Theoretically, this sounds nice, but practically, direct application of TDP is often not scalable due to the inevitable exponential constant factor in the treewidth. We apply TDP as a broadly applicable tool to enhance existing graph optimization algorithms. Our framework employs a similar concept to treewidth modulator.

Definition 3 (Treewidth Modulator [Cygan et al., 2011]). Let η ≥ 0 be an integer and G be a graph. A set Mη ⊂ V (G) is called an η-treewidth modulator in G if TW ∗ (G\Mη) ≤ η. We useM∗η (G) to denote the optimal treewidth modulator to a target width value η with the minimum size (i.e., we want to minimize the number of vertices deleted |Mη|).

We use M∗ to denote the task of generating the optimal treewidth modulator M∗η (G), which is NP-hard due to its hereditary property [Lewis and Yannakakis, 1980]. Its hardness can also be easily illustrated via the following example.

Example 1. When η = 1, M∗ is equivalent to feedback vertex set. When η = 0, M∗ is equivalent to vertex cover.

Despite a long series of existing theoretical works onM∗ , such as [Baste et al., 2020], there do not exist scalable exact algorithms, approximation algorithms, or even practically useful bounds. In this paper, we propose a variant of M∗

called Treewidth Modulator on a Given Tree Decomposition. 2 Our variant was designed for practical scalability - it is still NP-hard, but its exact solution takes only 1 second on average in our experiments.

Definition 4. (Treewidth Modulator on a Given Tree Decomposition) Given a graph G and a tree decomposition of G denoted as T = (T, {Xt}t∈V (T)) and a parameter k. We simply delete vertices from the existing bags (the Xt) and do not regenerate the tree structure T. That is, after deleting Y ⊆ V (G), the resulting tree decomposition is T ′ = (T, {Xt \ Y }t∈V (T)) and the resulting treewidth is maxt∈V (T) |Xt \ Y | - 1. We want to decide whether there exists a vertex set Y ⊆ V (G), |Y | ≤ k, whose deletion will reduce the width of T ′ to at most η.

We use M to denote the above variant. 3 The idea behind it is simple. Instead of regenerating tree decomposition after vertex deletion, we reuse the same tree decomposition by simply removing vertices from its existing bags. We first show that the deleting vertices from a tree decomposition's existing bags indeed results in a valid tree decomposition.

Proposition 1 (⋆). Given a graph G and a tree decomposition of G denoted as T = (T, {Xt}t∈V (T)), where T is a tree and every tree node t ∈ V (T) corresponds to a subset of vertices from the original graph, denoted as Xt ⊆ V (G).

For any set of vertices Y ⊆ V (G), after deleting Y from T without regenerating the tree decomposition, the result T ′ = (T, {Xt \ Y }t∈V (T)) is still a valid tree decomposition.

Next, we claim that even though M avoids regenerating tree decompositions, it remains NP-complete.

Theorem 2 (⋆). Treewidth modulator on a given tree decomposition is NP-COMPLETE.

In our experiments, we use the polynomial-time MINDEGREE heuristic to generate the initial tree decomposition and apply mixed integer programming to remove the minimum set of vertices from the initial tree decomposition's existing bags (⋆). The above is a fast heuristic forM.

3 Technical Description of Framework

We start by describing our core routine, which applies TDP to enhance an existing algorithm specified as a subroutine. We describe the (1+1)EA evolutionary algorithm subroutine and the ϵ-greedy subroutine in this section. We defer the graph neural networks (GNN) based heuristics to the experiments. In our presentation, we use P to denote the optimization problem with solution space 2n . Without loss of generality, we assume that P has a maximization objective.

Core Routine. There are no known efficient algorithms for generating the optimal treewidth modulator. Our more scalable variant of treewidth modulator on a given tree decomposition (M) offers an empirically scalable way to generate a treewidth modulator that suffices for our TDP application. While treewidth modulators are defined as vertex sets whose deletion would reduce the treewidth of the remaining graph, when we apply a treewidth modulator, we do not actually delete any vertices, but we rely on the existing algorithm A that we aim to enhance (i.e., the subroutine we plug in) to assign values to v ∈ M from a search space of 2|M| . The assignments are referred to as A's advice, denoted by s. Via TDP, we can efficiently derive the optimal overall solution conditional on advice s. To illustrate this idea, imagine that we are processing a specific bag B from the tree decomposition. Typically, TDP involves enumerating all feasible states/assignments of B. For example, suppose |B| = 4. Our initial understanding of the optimal assignments can be described as the string <?,?,?,?>, representing that the optimal assignments are completely unknown. TDP needs to enumerate 24 states. Suppose an advice is provided, we can settle some of the ?s. Assume A advised that the first coordinate must be 1 and the third coordinate must be 0, i.e., our understanding of the optimal assignments becomes <1,?,0,?>. Consequently, we only have 22 states to enumerate. Thus, given an advice string describing the decisions within the treewidth modulator, TDP is effectively focusing on the decisions outside the treewidth modulator, as if the treewidth modulator vertices have been deleted. Our core routine's pseudo code is provided as follows. We follow the standard description of treewidth dynamic program, 4 only slightly modified to accommodate advice.

2 Our proxy problem is on deleting vertices. A variant on deleting edges from a given tree decomposition has been previously studied in the field of bioinformatics [Marchand et al., 2021].

3 We abuse M for both treewidth modulator and the problem of computing treewidth modulator.

Algorithm 1 Treewidth Dynamic Programming with advice

Input: G = (V, E), Tw = (T, {Xt}t∈V (T)): an arbitrary tree decomposition with width w, Mη: a modulator to Tw with target width η, s ⊆ M: an advice string (subset) given by external subroutine A, P : a maximization problem Output: OPT to P

• 1: Let C, D be two tables.
• 2: for t ∈ V (T ) in a bottom-up manner do 3: Xp ← {k|k ∈ V (T) and k ∈ Parent(t)} 4: Xc ← {j|j ∈ V (T) and j ∈ Children(t)} Apply advice here 5: Ft ← {x| x ⊆Xt \ s and P(x) is satisfied} 6: for x ∈ Ft do Complete state with advice 7: x ← x ∪ s Merge states from children 8: C(t, x ∩ Xj ) = |x| + ∑︁j∈Xc (D(j, t, x ∩ Xj ) - |x ∩ Xj |) Upload states to parent 9: D(t, k, x ∩ Xk) = maxk∈Xp C(t, x ∩ Xk) 10: OPT ←maxx∈Froot C(root, x) 11: return OPT

(1+1)EA Evolutionary Algorithm Subroutine. We use (1+1)EA to search over advice assignments on the modulator M. The algorithm maintain an incumbent x ∈ {0, 1}|M| . Each iteration generates an offspring y by mutating x: for every coordinate i, the bit xi is flipped independently with probability 1/ |M|. The selection rule is elitist: y replaces x if it achieves at least the same fitness value.

4 Please refer to Chapter 7.1-7.3 of [Cygan et al., 2020] for a detailed description of treewidth dynamic programming.

The fitness function f is defined through conditional optimization. For an advice vector x, we fix the decisions of vertices inMaccording to x, and compute an optimal completion over V \M that inherits these fixed decisions. The resulting objective value is f(x). This evaluation is performed by the treewidth DP with advice (Alg. 1), which makes fitness computation scalable after modulator restriction. The complete (1+1)EA procedure is given in Alg. 2.

Algorithm 2 (1+1)EA Subroutine

Input: modulator M ⊆ V with |M| = m; fitness function f : {0, 1}m →R; iteration (or time) budget B Output: the best advice x ∈ {0, 1}m found 1: Sample x ∼ Unif({0, 1}m); fx ← f(x) 2: for ℓ = 1 to B do 3: y ← x 4: for i = 1 to m do 5: if Bernoulli(1/m) = 1 then 6: yi ← 1 - yi 7: fy ← f(y) 8: if fy ≥ fx then 9: x ← y; fx ← fy 10: return x

ϵ-greedy with Voting Subroutine. The second class of algorithms we investigate is greedy. For each problem P , we instantiate a problem-specific greedy heuristic Hp: max-degree for MVC, vertex-flipping for MC, and min-degree as an effective heuristic for MIS.

We augment Hp with an exploration rate ϵ, interpreted as the probability of taking a non-greedy step rather than the greedy one. Algorithm 3 runs Hp(G, ϵ) for R trails to generate solutions x(r) , then converts each trail into an advice bitvector a(r) ∈ {0, 1}m by restricting to the modulator , i.e., a(r) ← x(r) |M; each trail is scores by α(r) ← objP (x(r) ). The final advice is selected by either: 1. WTA: choose r∗ ∈ argmaxr∈[R] α(r) and output a(r) . 2. Maj: for each i ∈ [m], set ai = 1 ⇐⇒ ⃓⃓⃓{︂r ∈ [R] | a(r) i = 1}︂⃓⃓⃓ > R/2. In this way, WTA trusts the single best run under objP , while Maj stabilizes the modulator decisions through aggregation over repeated ϵ-greedy trails.

Correctness. TDPA conditions the dynamic program on an advice assignment over the treewidth modulator M. The key correctness requirement is that this conditioning must neither exclude feasible completions that remain consistent with the advice nor admit infeasible solutions. The required consistency mechanism is problem dependent, and we use MC versus MIS/MVC to illustrate the difference.

For MC, the advice only fixes decisions internal toMand does not impose constraints on choices outside M. Consequently, committing to any assignment onMcannot introduce

Input: modulator Mwith |M| = m; heuristic HP ; exploration rate ϵ; trials R; rule Vote ∈ {WTA,Maj} Output: advice vector a ∈ {0, 1}m 1: for r = 1 to R do 2: x(r) ←HP (G, ϵ) 3: a(r) ← x(r) |M ∈ {0, 1}m 4: α(r) ← objP (x(r) ) 5: if Vote =WTA then 6: r⋆ ← arg maxr∈[R] α(r) 7: return a(r⋆ ) 8: else 9: Initialize a ← 0 ∈ {0, 1}m 10: for i = 1 to m do 11: if |{r ∈ [R] | a(r) i = 1}| > R/2 then 12: ai ← 1 13: return a

cross-boundary conflicts, and the DP over the remainder of the graph remains an exact optimization over all feasible completions.

Fro MIS and MVC, in contrast, decisions onMnecessarily constrain vertices outside M through adjacency. We therefore enforce boundary consistency via ∂M, the set of vertices inM that have neighbors outside M. For MIS, selecting v ∈ ∂M forces all neighbors in N(v) to be non-selectable. For MVC, excluding v ∈ ∂M forces all neighbors v ∈ N(v) to be included. These implications ensure that the DP enumerates exactly the feasible completions consistent with the advice in the next stage.

Finally, for randomized algorithms like (1+1)EA, the advice itself maybe locally infeasible within M (e.g., selecting adjacent vertices for MIS). Such conflicts are resolved by a simple randomized repair step that restores feasibility onM before invoking TDPA.

4 Experiments

We evaluate on Maximum Independent Set (MIS), Minimum Vertex Cover (MVC), and Max Cut (MC). We apply TDP to enhance (1+1)EA, greedy, and graph neural networks. For every combination of optimization models and existing algorithms, our TDP enhanced versions significantly improve over the original algorithms. In many scenarios, TDP-enhanced greedy achieve solutions that are comparable to, and sometimes clearly outperform, those obtained by GUROBI, a state-ofthe-art commercial solver. It is worth emphasizing that while occasionally surpassing GUROBI is an impressive achievement, especially considering that our implementation is pure Python, our primary experimental goal is to demonstrate that TDP can be used as a broadly applicable enhancement tool.

Dataset. We construct two benchmark sets, EASY and HARD, based on treewidth. EASY consists of real-world graphs, e.g., from fluid dynamics, road networking and others that typically have relatively low treewidth. HARD contains synthetic instances generated from the frequently cited models [Ahn et al., 2020; Sun and Yang, 2023] Erd˝os-R'enyi (ER) and Barab'asi-Albert (BA) models, configured to yield moderately large treewidth so that commercial solvers such as GUROBI struggle to obtain high-quality solutions within a limited time budget; we generate 100 instances per model. We exclude near-clique graphs (clique number close to |V |), since they usually have treewidth linear to |V | and are thus uninformative for treewidth dynamic programming. Full instance statistics and sources are deferred (⋆) to the appendix.

Baselines and Configurations. We evaluate baseline algorithms with the TDPA-enhanced counterparts under our framework. As a reference point, we include GUROBI, which typically yields strong feasible solutions for combinatorial optimization even when it does not complete the optimality proof. To ensure a fair comparison, we restrict GUROBI to a single thread, consistent with all other methods in this paper. We report results at checkpoints of {30, 60, 300, 600} seconds under two settings: the default configuration and MIPFocus=1, which prioritizes finding high-quality feasible solutions.

For heuristic baselines, we integrate evolutionary algorithm, greedy heuristics and GNN models into our framework, demonstrating broad composability across various paradigms.

Greedy heuristics. We tune ϵ in the range of {0, 0.01, 0.05} as exploration ratio on both MIS and MVC. For MC, we use vertex-flipping, here ϵ controls the refinement budget (number of iterations), and we set it in {0, 1000, 5000}. Details (⋆) are deferred to appendix.

GNN baselines. We train a simple GNN (⋆) by unsupervised minimization of the QUBO objective (⋆). Given GNN advice, TDPA computes the optimal completion consistent with that advice.

All methods have 10 runs with 10 different seeds per instance; additional details can be found in appendix.

Decompositions andModulators. Prior results [Bannach et al., 2017; Maniu et al., 2019] indicate that min-degree (⋆) heuristic often produces near-optimal treewidth in practice and remains competitive with more sophisticated treewidth algorithms. We therefore apply this heuristic to construct initial tree decompositions. And we defer the details of this heuristic to appendix. For the modulatorM, we formulate the computation as a mixed-integer programming (⋆), since in practice the MIP takes about one second on average to obtain M. Although the optimality gap between M and M∗ can in principle be large, tightening |M| is not our focus; any reduction in |M| will only strengthen our results.

4.1 Results &Analysis

On Randomized Algorithm. Across all instances and objectives (MC/MIS maximization and MVC minimization), Figure 1 highlights two consistent effects: incorporatingM reduces stagnation, and smaller modulators typically yield stronger gains. We denote TMτ as the modulator computed by M at target treewidth τ (larger τ ⇒ smaller |TMτ |). We vary the target treewidth τ ∈ {5, 7, 9}; as the legends indicate, a larger τ produces a smaller modulator, e.g., |TM5| > |TM7| > |TM9|. Under a much smaller budget (3,000 vs. 1 million iterations), the modulator-guided runs reach high-quality solutions much earlier: the annotated firsthitting times occur sooner and the trajectories improve more u1D447 u1D4405

u1D447 u1D4407

u1D447 u1D4409

The Number of Iterations

Figure 1: Colored vertical lines mark the average first hitting time - the first moment the best solution appears for each curve. The indicates the GUROBI solutions. For presentation, once the curves converge to a single value, we omit the rest steps because they are not informative. The instance name and TW are shown above TM in each legend group. More results (⋆) are deferred to the appendix.

steadily, with TM9 most often leading throughout the run. Additionally, the smaller-|M| curves more frequently approach, and in several cases match the GUROBI reference line, while larger-|M| runs exhibit longer plateaus, whereas leveraging |M| substantially increases the chance of attaining the global optimum. The table echoes this effect quantitatively: for many instances (e.g., DD199 and power-685-bus across MC/MIS/MVC), EA+TDPA attains the GUROBI-optimal objective values whereas (1 + 1)EA remains far below/above them, consistent with the baseline being trapped on suboptimal plateaus. While the smaller modulator is preferable in best objective values, the first-hitting times in seconds can exhibit a trade-off (e.g., dwt 307), and there are instances where the baseline is competitive under our settings (e.g., can 161), suggesting room for adaptive choices of τ .

On Greedy Heuristics. Table 2 summarizes the MIS/MVC results (Results on MC(⋆) has been deferred to the appendix), and reveals two patterns. First, ϵ-greedy baselines are insensitive and problem-specific: on both ER and BA, increasing ϵ

from 0 to 0.05 consistently worsens the runtime but does not reliably improve quality, and can even worsen it and yields larger gaps on both ER and BA. Second, TDPA provides a consistent improvement on solution quality and largely removes the tuning brittleness. For MIS, TDPA yields near-solver quality: on ER, (0.01)-TDPA attains a gap of about -0.20% relative to the 600s GUROBI baseline, and on BA it reaches 0.51% - both dramatically better than greedy's 2-4% gaps. For MVC, TDPA reduces the gap roughly by half compared to greedy, e.g., BA:3.78%→ 1.84%. Compared with MIS, MVC seems more sensitive to the remaining hard structure outside the reduced-treewidth region. In terms of time, TDPA typically runs in ∼25-60s, which place it near the 30-60s solver budgets; in this regime it can match or exceed short-budget solver performance in several settings while remaining purely heuristic. These trends suggest that TDPA primarily improves the search landscape and robustness (replace fragile ϵ choices with stable performance). Additionally, restricting TDP to reduced-treewidth components can systematically elevate simple heuristics toward near-optimal solutions while preserving the scalability advantages that make greedy methods attractive on hard instances.

On Graph Neural Network. Neural solvers for combinatorial optimization are commonly built upon GNNs with reinforcement learning [Ahn et al., 2020] or diffusion-style sampling [Sun and Yang, 2023]. In practice, they often suffer from (a) large training budgets, (b) sensitivity to the training distribution, and (c) limited competitiveness against strong heuristics. We study an unsupervised alternative [Angelini and Ricci-Tersenghi, 2022] that frames vertex problems as node classifications and minimize a QUBO-form objective [Glover et al., 2019]. Empirically, as shown in Fig. 2, we find that optimization progress is not reflected by the loss: the loss decreases monotonically, yet solution quality (Performance) plateaus early, consistent with convergence to a poor local optimum; continuing training then yields diminishing returns rather than meaningful improvements.

TDPA provides a principled way to diagnose and exploit this plateau. We monitor the labels on the treewidth modulatorMvia TM-stability, defined at checkpoint t as |Lp∩Lc| |M| , where Lt is the predicted label set onM. In Fig. 2 (10,000 gradient-descent steps, evaluated every 50 steps), TM-stability rises to near 1.0 within the earliest checkpoints, substantially earlier than the loss and performance curves stabilize. This indicates that the model's decisions onM"freeze" quickly. This decoupling explains the stagnation: subsequent updates mainly reshuffle predictions outside M and rarely change the globally relevant commitments captured by M. From this early stabilization, TDPA uses GNN's current labels on M as advice to produce a high-quality feasible solution early; the orange curves track this prediction and consistently dominate the raw GNN solutions during the long plateau for MC and MIS, and yield markedly better solutions for MVC as well (where smaller the better). Consequently, TM-stability serves as an actionable early-stopping signal, and TDPA turns partial training progress into near-best solutions without paying the full training cost. Results on BA reflect the similar improvements, further confirming the effectiveness while coupling with GNNs.

5 Conclusion

We introduced treewidth dynamic programming with advice, a general framework for enhancing graph combinatorial optimization algorithms. TDPA integrates TDP with heterogeneous advice sources, including (1 + 1)EA, greedy heuristics, and GNN-based models. To enable this integration, we show that treewidth modulator on given tree decomposition is hard, and we propose a MIP formula that enables fast computation in practice. We then prove that the resulting advice-integrated DP remains correct. Empirically, TDPA consistently improves solution quality over the underlying methods and stays competitive with GUROBI in first-hitting time. We further showed that TDPA provides a useful early-stage prediction, enabling earlier feedback during training and sharper improvement of downstream performance. These findings suggest that treewidth DP can be practically effective beyond small-treewidth instances when coupled with targeted advice. Future work will focus on practical methods for constructing smaller treewidth modulators to further expand the range of scalable instances.

Acknowledgements

We would like to particularly thank Professor Michael Fellows and Professor Frances Rosamond for their valuable comments and support to this work. I am deeply grateful to Dr. Weitong Chen for his tremendous guidance and unwavering support. We are also profoundly thankful to Dr. Fabien Voisin, who consistently provided timely support with computing resources. This work was supported with resources provided by the Phoenix HPC service at Adelaide University. Without the support of any of these parties, this work would not have reached its current stage.