Tree decomposition, explained

The scaffold that turns a tangled graph into something you can sweep.

What a tree decomposition is

A tree decomposition of a graph G is a tree T whose nodes are bags — subsets of G's vertices — satisfying three conditions: every vertex appears in some bag; every edge of G has both endpoints together in some bag; and for each vertex, the bags containing it form a connected subtree.

The width of the decomposition is the size of its largest bag, minus one. The treewidth of G is the smallest width achievable over all valid decompositions. The −1 is a convention that makes trees come out at width 1.

The connectivity condition is the load-bearing one

The third condition — that the bags containing any fixed vertex form a connected subtree — is what makes dynamic programming sound. It guarantees that once a vertex 'leaves' the active frontier as you sweep the tree, it never comes back. That is exactly the property that lets you forget state and keep the table small.

A worked example

Take a 4-cycle a–b–c–d–a. One valid decomposition is a path of two bags: {a, b, c} and {a, c, d}. Each edge is covered, every vertex's bags are connected, and the largest bag has 3 vertices — width 2. No decomposition does better, so the 4-cycle has treewidth 2.