Introduction

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.

Solve It on a Tree

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">Pick a set of vertices with the largest total <b>weight</b> so that <b>no two picked vertices share an edge</b> (maximum-weight independent set). On a general graph this is NP-hard — but this is a <b>tree</b>, so one bottom-up dynamic-programming sweep finds the true optimum.</p>
<svg id="tree" viewBox="0 0 360 250" role="img" aria-label="weighted tree"></svg>
<div class="status" id="status">Your selection: weight 0</div>
<div class="btns">
  <button id="solve" type="button">Solve optimally</button>
  <button id="reset" type="button" class="ghost">Clear</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Maximum-weight independent set on a TREE.
// General graphs: NP-hard. Trees (treewidth 1): solvable by a single
// bottom-up dynamic program. For each vertex v we keep two values:
//   IN[v]  = best weight in v's subtree WITH v chosen   = w(v) + sum over children c of OUT[c]
//   OUT[v] = best weight in v's subtree WITHOUT v chosen = sum over children c of max(IN[c],OUT[c])
// Answer = max(IN[root], OUT[root]). Linear time, exact optimum.
const W = { 0:4, 1:8, 2:3, 3:7, 4:2, 5:9, 6:5 }; // vertex weights
const POS = { 0:[180,30], 1:[90,100], 2:[270,100], 3:[40,180], 4:[140,180], 5:[230,180], 6:[310,180] };
const CHILDREN = { 0:[1,2], 1:[3,4], 2:[5,6], 3:[], 4:[], 5:[], 6:[] };
const PARENT = {}; for (const p in CHILDREN) CHILDREN[p].forEach(c => PARENT[c] = +p);
const EDGES = []; for (const p in CHILDREN) CHILDREN[p].forEach(c => EDGES.push([+p, c]));
const ROOT = 0;

const sel = new Set();

function buildSvg() {
  const svg = document.getElementById('tree'); svg.innerHTML = '';
  const ns = 'http://www.w3.org/2000/svg';
  EDGES.forEach(([a,b],i) => {
    const l = document.createElementNS(ns,'line');
    l.setAttribute('x1',POS[a][0]); l.setAttribute('y1',POS[a][1]);
    l.setAttribute('x2',POS[b][0]); l.setAttribute('y2',POS[b][1]);
    l.setAttribute('class','edge'); l.dataset.edge = i; svg.appendChild(l);
  });
  for (const v in POS) {
    const g = document.createElementNS(ns,'g');
    g.setAttribute('class','node'); g.dataset.v = v;
    const c = document.createElementNS(ns,'circle');
    c.setAttribute('cx',POS[v][0]); c.setAttribute('cy',POS[v][1]); c.setAttribute('r',18);
    const t = document.createElementNS(ns,'text');
    t.setAttribute('x',POS[v][0]); t.setAttribute('y',POS[v][1]); t.textContent = W[v];
    g.appendChild(c); g.appendChild(t);
    g.addEventListener('click',()=>toggle(+v));
    svg.appendChild(g);
  }
  render();
}

function toggle(v){ sel.has(v) ? sel.delete(v) : sel.add(v); render(); }

function violations(){ return EDGES.filter(([a,b]) => sel.has(a) && sel.has(b)); }
function weight(set){ let s=0; set.forEach(v => s += W[v]); return s; }

function render(opt){
  document.querySelectorAll('.node').forEach(g => {
    const v = +g.dataset.v;
    g.classList.toggle('sel', sel.has(v) && !opt);
    g.classList.toggle('opt', !!opt && opt.has(v));
  });
  const bad = violations();
  document.querySelectorAll('.edge').forEach(l => l.classList.remove('bad'));
  bad.forEach(([a,b]) => { const i = EDGES.findIndex(e=>e[0]===a&&e[1]===b);
    const l = document.querySelector('.edge[data-edge="'+i+'"]'); if(l) l.classList.add('bad'); });
  const s = document.getElementById('status');
  if (opt) { s.textContent = fmt('Optimal set highlighted: weight %weight%.', { weight: weight(opt) }); s.className='status ok'; }
  else if (bad.length) { s.textContent = fmt('✗ %length% edge(s) connect two picked vertices — not independent.', { length: bad.length }); s.className='status bad'; }
  else { s.textContent = fmt('Your selection: weight %weight% %v%', { weight: weight(sel), v: sel.size?'(valid independent set)':'' }); s.className='status'+(sel.size?' ok':''); }
}

// Bottom-up DP. Returns {IN, OUT, takeIn} per vertex; reconstruct the chosen set.
function solve(){
  const IN = {}, OUT = {};
  // post-order via recursion (tree is small and acyclic)
  function dfs(v){
    let inSum = W[v], outSum = 0;
    CHILDREN[v].forEach(c => { dfs(c); inSum += OUT[c]; outSum += Math.max(IN[c], OUT[c]); });
    IN[v] = inSum; OUT[v] = outSum;
  }
  dfs(ROOT);
  const chosen = new Set();
  // reconstruct: top-down, choose v iff it helps and parent not chosen
  function pick(v, parentChosen){
    const takeV = !parentChosen && IN[v] >= OUT[v];
    if (takeV) chosen.add(v);
    CHILDREN[v].forEach(c => pick(c, takeV));
  }
  pick(ROOT, false);
  return { chosen, best: Math.max(IN[ROOT], OUT[ROOT]) };
}

document.getElementById('solve').addEventListener('click',()=>{
  const { chosen, best } = solve();
  sel.clear(); chosen.forEach(v => sel.add(v));
  render(chosen);
  console.log('Optimal independent set:', [...chosen].sort((a,b)=>a-b), '| weight', best);
});
document.getElementById('reset').addEventListener('click',()=>{ sel.clear(); render(); });
buildSvg();
Result
Console

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 2k2^{k} combinations. Small k: fast. Large k: back to exponential.

The Real Complexity

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

Where It Matters

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

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/treewidth/Content licensed under CC BY-NC 4.0.