Treewidth

Some graph problems are notoriously hard. Finding the largest independent set, the smallest vertex cover, or a proper 3-coloring are all NP-hard in general — no known algorithm avoids, in the worst case, an explosion of work as the graph grows.

But there is one shape where all of these problems are easy: a tree. On a tree you can solve them by walking from the leaves up to the root, carrying a small summary at each step. No branching, no backtracking — just a single sweep.

Treewidth is the number that measures how close a graph is to being a tree. A tree has treewidth 1. A graph with a few extra edges has treewidth 2 or 3. A dense, tangled graph has high treewidth. And the punchline is that for a huge family of hard problems, the difficulty scales not with the size of the graph but with its treewidth — keep that small and the hardness melts away.

Here is a tree whose vertices carry weights. Your goal is the classic NP-hard problem maximum-weight independent set: pick a set of vertices with the largest total weight such that no two picked vertices share an edge.

Click vertices to select them (illegal neighbor pairs flash red). Then press Solve optimally to watch a single bottom-up dynamic-programming sweep compute the true optimum — the same algorithm that runs on any low-treewidth graph via its tree decomposition.

<p class="hint">{{hint}}</p>
<svg id="tree" viewBox="0 0 360 250" role="img" aria-label="{{aria_tree}}"></svg>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
svg { width: 100%; max-width: 360px; height: auto; display: block; margin: 0 auto; }
.edge { stroke: #adb1b8; stroke-width: 2; }
.edge.bad { stroke: #e63946; stroke-width: 3.5; animation: flash .5s ease-in-out 3; }
@keyframes flash { 50% { stroke: #ffb3ba; } }
.node { cursor: pointer; }
.node circle { fill: #e8eef3; stroke: #cdd9e3; stroke-width: 2; transition: all .12s; }
.node.sel circle { fill: #0a7d33; stroke: #075c25; }
.node.opt circle { fill: #1d3557; stroke: #14233b; }
.node text { font: 700 13px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.node.sel text, .node.opt text { fill: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

On a general graph this problem is intractable. But on a tree (treewidth 1) the dynamic program keeps just two numbers per vertex — best with it in the set, best with it out — and combines children in linear time. Raise the treewidth to k and the same idea works, but each "bag" of the decomposition now tracks $2^{k}$ combinations. Small k: fast. Large k: back to exponential.

Treewidth, introduced by Robertson and Seymour in their graph-minors work (1984), is defined through a tree decomposition: arrange the graph's vertices into overlapping "bags" attached to a tree, so that every edge sits inside some bag and each vertex's bags form a connected sub-tree. The width is the size of the largest bag minus one; the treewidth is the smallest width over all decompositions.

What this buys us:

• A polynomial-time algorithm for the fixed parameter. Independent set, vertex cover, dominating set, 3-coloring, Hamiltonian cycle and dozens more can be solved in time roughly 2^$O(k)$ · n on a graph of treewidth k — linear in the graph size once k is fixed. This is the textbook example of fixed-parameter tractability (FPT).
• Courcelle's theorem (Bruno Courcelle, 1990): any graph property expressible in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. One theorem, an infinite buffet of "hard" problems made easy.
• Computing treewidth is itself NP-hard (Arnborg, Corneil, Proskurowski, 1987). But for a fixed target k, Bodlaender's algorithm (1996) decides treewidth ≤ k and builds the decomposition in linear time — so the bottleneck is the value of k, not the size of the graph.

The deep message ties back to P vs NP: a problem being NP-hard is a statement about the worst case over all inputs. Treewidth carves out a vast, structured slice of inputs where the worst case never happens.

"This network is almost a tree" is a surprisingly common situation, and treewidth is how we cash it in:

• Probabilistic inference: exact inference in a Bayesian network runs the junction-tree algorithm — dynamic programming over a tree decomposition. Its cost is exponential in treewidth, so the whole field hunts for low-width orderings.
• Compilers: register allocation and other dataflow problems are tractable because control-flow graphs of structured programs have small treewidth.
• Databases: a conjunctive query whose hypergraph has low (hyper)treewidth can be evaluated efficiently; query optimizers exploit exactly this.
• Networks and roads: many real-world networks are "tree-like" enough that bounded-treewidth algorithms beat the general-case worst bounds.

The same dynamic-programming-on-a-decomposition engine reappears across these fields — it is the practical face of the minimum spanning tree-style "structure makes it easy" idea.

Treewidth reframes one of the most important questions in computing. "Is this problem hard?" becomes "how tree-like is this input?" For an enormous family of NP-hard problems, a small treewidth is a guarantee of a fast, exact, dynamic-programming solution.

So hardness is not always destiny. The worst case that makes P vs NP so daunting often hides in dense, tangled instances — and when your graph is almost a tree, you can walk right past it, one bag at a time.