Dynamic Programming on Tree Decompositions

The Core Intuition: Remember the Boundary

Many hard graph problems feel global because a choice made here can constrain vertices far away. Treewidth asks whether those long-range interactions can be routed through a small interface. If they can, we process most of the graph, forget its internal details, and retain only what the unprocessed part still needs to know.

This is the same idea behind ordinary dynamic programming on a rooted tree. A child subtree communicates with its parent through one vertex. A tree decomposition generalizes that interface from one vertex to a small set of vertices.

What a Tree Decomposition Must Guarantee

A tree decomposition of $G=(V,E)$ is a tree $T$ whose nodes carry vertex sets called bags, written $B_t\subseteq V$. It is not a spanning tree of the graph: its nodes are bags, bags may overlap, and one graph vertex may occur in several bags.

The third rule is the subtle one. A vertex may persist across several adjacent bags, but it may not disappear and later reappear. Without that connectedness, a DP could forget a constraint involving the vertex and then encounter the vertex again with no reliable memory of the earlier decision.

Width and treewidth

The width of one decomposition is its largest bag size minus one. Treewidth is the smallest width achievable over every valid decomposition:

The “minus one” convention makes a nontrivial tree have treewidth $1$: each tree edge can be a bag of size two. A single isolated vertex has treewidth $0$.

The separator fact that makes DP possible

Cut any decomposition-tree edge $tt'$. The intersection $B_t\cap B_{t'}$ separates graph vertices that occur only on one side from vertices that occur only on the other. Therefore, once a rooted DP finishes the subtree below $t$, the rest of the graph can interact with that processed region only through the current bag.

That observation tells us what a state should mean:

Nice Decompositions: Four Reusable Transitions

Arbitrary decompositions can be normalized into a rooted nice tree decomposition. Each node then performs one small structural operation. This usually increases the number of bags only polynomially and makes both proofs and implementations much cleaner.

We use bottom-up processing and the convention above. Some books reverse the names “introduce” and “forget” by orienting the tree differently. The formulas are not contradictory; the direction and state invariant must simply be stated.

flowchart TD
L[Leaf: base state] --> I[Introduce: extend]
I --> F[Forget: optimize]
L2[Other processed branch] --> J[Join: merge]
F --> J
J --> R[Root: final answer]

Worked Example: Maximum Independent Set

An independent set contains no adjacent pair. For a node $t$ and subset $S\subseteq B_t$, define

The invariant carries two kinds of information: $S$ must itself be independent, and the table value remembers the best compatible solution already hidden below the bag.

The transitions

At an empty root bag, the sole table entry is the optimum. For the chain-of-triangles graph above, the maximum independent-set size is $2$; examples include $\{A,D\}$ and $\{A,E\}$.

A manual trace

Implementation: Stable Bag Indices and Valid Masks

For subset-based problems, assign each vertex in a bag a fixed local bit position. Bit $i$ is $1$ exactly when the $i$th bag vertex is selected. A bag of size $b$ then has $2^b$ raw masks. Precompute which masks satisfy local constraints so transitions never reconsider obviously invalid states.

def valid_independent_masks(bag, edges):
    position = {vertex: i for i, vertex in enumerate(bag)}
    conflicts = [0] * len(bag)

    for u, v in edges:
        if u in position and v in position:
            i, j = position[u], position[v]
            conflicts[i] |= 1 << j
            conflicts[j] |= 1 << i

    valid = []
    for mask in range(1 << len(bag)):
        if all(not (mask & (1 << i) and mask & conflicts[i])
               for i in range(len(bag))):
            valid.append(mask)
    return valid

bag = ["B", "C", "D"]
edges = [("B", "C"), ("B", "D"), ("C", "D")]
print(valid_independent_masks(bag, edges))  # [0, 1, 2, 4]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Local order is B, C, D. Each pair is an edge.
    vector<int> conflict = {0b110, 0b101, 0b011};
    vector<int> valid;

    for (int mask = 0; mask < (1 << 3); ++mask) {
        bool ok = true;
        for (int i = 0; i < 3; ++i)
            if ((mask & (1 << i)) && (mask & conflict[i]))
                ok = false;
        if (ok) valid.push_back(mask);
    }
    for (int mask : valid) cout << mask << ' '; // 0 1 2 4
}

import java.util.*;

public class BagMasks {
    public static void main(String[] args) {
        // Local order is B, C, D. Each pair is an edge.
        int[] conflict = {0b110, 0b101, 0b011};
        List<Integer> valid = new ArrayList<>();

        for (int mask = 0; mask < (1 << 3); mask++) {
            boolean ok = true;
            for (int i = 0; i < 3; i++)
                if ((mask & (1 << i)) != 0 &&
                    (mask & conflict[i]) != 0) ok = false;
            if (ok) valid.add(mask);
        }
        System.out.println(valid); // [0, 1, 2, 4]
    }
}

Complexity: What the Parameter Really Buys

Let $n=|V|$ and let $k$ be the decomposition width. A subset state has at most $2^{k+1}$ masks per bag, so independent-set and vertex-cover DPs can often run in $O(2^k\,\mathrm{poly}(k)\,n)$ time on a suitable nice decomposition. The exact factor depends on transitions and representation.

The phrase “linear time on bounded-treewidth graphs” means that $k$ and the problem description are treated as fixed. It does not mean the hidden dependence on $k$ is small. Courcelle's theorem is a powerful classification result, but its general construction can carry enormous constants; hand-designed DPs are usually preferable in practice.

Where Treewidth DP Fits

Treewidth DP is most attractive when an exact answer matters, the width stays modest, and the state can express all boundary interactions compactly. A large, low-degree road or grid network may still have high treewidth; in that case approximation, branch-and-bound, integer programming, or problem-specific separators may be a better choice.

Common Failure Modes

A practical design checklist

Structural Theory to an Algorithmic Toolkit

Treewidth grew from structural graph theory and became central to the graph-minors program. Its algorithmic importance comes from a clean bridge: small treewidth means the graph can be assembled through small separators, and small separators mean a finite boundary state can summarize each processed region.

Courcelle's theorem pushes this principle remarkably far: many properties expressible in monadic second-order logic are decidable in linear time on graph classes of bounded treewidth. The theorem explains the breadth of the method; the worked independent-set DP shows the engineering pattern that makes it tangible.