Treewidth, in depth: tree decompositions, min-fill elimination orderings, lower bounds, a tested DP over bags, nice decompositions and exact solvers

Tree decompositions

A tree decomposition of a graph G is a tree T whose nodes carry sets of vertices of G, called bags, satisfying three rules:

1. Every vertex of G is in at least one bag.
2. For every edge u-v of G, some bag contains both u and v.
3. For every vertex v, the bags containing v form a connected subtree of T. This is the running intersection property.

The width of a decomposition is the size of its largest bag minus one. The treewidth of G is the smallest width over all its decompositions. The minus one is there so that trees come out with treewidth 1: each edge becomes a bag of two vertices.

Some anchors help. A forest with at least one edge has treewidth 1. A cycle has treewidth 2. A complete graph on n vertices has treewidth n - 1, because some bag must contain every vertex. An n by n grid has treewidth n. The connectivity rule is what makes dynamic programming work: a bag separates the vertices that appear only below it in the tree from the vertices that appear only elsewhere, so a solution can be built from the bottom up while remembering only what happens inside the current bag.

Elimination orderings are decompositions

The most practical way to construct a decomposition is through an elimination ordering. Take the vertices in some order. To eliminate a vertex v, record the bag consisting of v and its current neighbours, add edges so that those neighbours form a clique (the new edges are fill edges), then delete v. The width of the ordering is the largest bag minus one.

Every ordering gives a valid decomposition: each bag hangs under the bag of the earliest eliminated vertex among its other members. Conversely, every decomposition of width k yields an ordering of width at most k, so treewidth equals the minimum width over all orderings. The search for a good decomposition becomes a search for a good permutation. The graph plus its fill edges is chordal, which is why this topic and chordal graphs are the same subject seen from two sides.

Min-fill and min-degree

Finding the best ordering is NP-hard, so practice relies on greedy heuristics. Min-degree eliminates the vertex with the fewest current neighbours. Min-fill eliminates the vertex whose elimination adds the fewest fill edges, breaking ties by degree. Min-fill is slower per step but usually gives smaller width, and it is the standard first choice.

def min_fill_order(adj):
    """Greedy elimination ordering. adj: dict vertex -> set of neighbours."""
    g = {v: set(ns) for v, ns in adj.items()}
    order, bags = [], {}
    while g:
        def fill(v):
            ns = list(g[v])
            return sum(1 for i in range(len(ns)) for j in range(i + 1, len(ns))
                       if ns[j] not in g[ns[i]])
        v = min(g, key=lambda u: (fill(u), len(g[u]), str(u)))
        ns = g[v]
        bags[v] = frozenset(ns | {v})
        for a in ns:                      # make the neighbourhood a clique
            g[a] |= ns - {a}
            g[a].discard(v)
        del g[v]
        order.append(v)
    return order, bags

def decomposition(order, bags):
    """bag(v) hangs under the bag of the first-eliminated vertex among its later neighbours."""
    pos = {v: i for i, v in enumerate(order)}
    parent = {}
    for v in order:
        later = [u for u in bags[v] if u != v]
        parent[v] = min(later, key=pos.get) if later else None
    width = max(len(b) for b in bags.values()) - 1
    return parent, width

This version recomputes fill for every vertex at each step, which is fine for thousands of vertices but not millions. Production code keeps fill counts in a priority queue and updates only the vertices near the one just eliminated. On a 5 by 5 grid this code returns width 5, which is optimal.

Worked example

Take the six-cycle a-b-c-d-e-f-a with one chord b-e. Min-fill starts with four vertices that each need one fill edge (a, c, d and f) and picks a by name. Eliminating a adds the fill edge b-f. Now f has neighbours b and e, already joined by the chord, so f costs no fill and goes next. Then b adds c-e, and the rest need nothing. The result:

order  : a f b c d e
bags   : a:{a,b,f}  f:{b,e,f}  b:{b,c,e}  c:{c,d,e}  d:{d,e}  e:{e}
parent : a->f  f->b  b->c  c->d  d->e  e->root
width  : 2

Check the rules by hand. Edge b-e appears in bags bef and bce. Vertex b appears in abf, bef and bce, which are consecutive in the chain. The graph contains a cycle, so its treewidth is at least 2, and this decomposition proves it is exactly 2.

Lower bounds

A heuristic width is only an upper bound. To know whether it is close to optimal, compute a lower bound. The simplest is the degeneracy: repeatedly delete a minimum-degree vertex and record the largest minimum degree seen. Treewidth is at least the degeneracy: if some subgraph H has minimum degree d, then in any elimination ordering the first vertex of H to be eliminated still has all its H-neighbours, so its bag holds at least d + 1 vertices.

def degeneracy(adj):
    g = {v: set(ns) for v, ns in adj.items()}
    lb = 0
    while g:
        v = min(g, key=lambda u: len(g[u]))
        lb = max(lb, len(g[v]))
        for u in g[v]:
            g[u].discard(v)
        del g[v]
    return lb

Degeneracy is weak on sparse graphs: on the 5 by 5 grid it gives 2 against a true value of 5. Minor-min-width is much better. Instead of deleting the minimum-degree vertex, contract it into a neighbour, choosing the neighbour that shares the fewest neighbours with it. Treewidth never increases under contraction, so the largest minimum degree seen is still a lower bound, and it usually climbs much higher. When the bounds meet, you are done; when the gap is large and the width is decisive for running time, invest in an exact solver.

Dynamic programming over bags

Here is the dynamic program that makes treewidth useful, for maximum-weight independent set. For each bag B, the table maps every independent subset S of B to the best weight of an independent set in the vertices at or below that bag whose intersection with B is exactly S. A child bag agrees with its parent on their shared vertices; their weight is subtracted once so it is not counted twice.

def mwis(adj, w, order, bags, parent):
    children = {v: [] for v in order}
    for v, p in parent.items():
        if p is not None:
            children[p].append(v)

    def independent(s):
        return all(b not in adj[a] for a in s for b in s if a != b)

    def subsets(bag):
        items = sorted(bag, key=str)
        for mask in range(1 << len(items)):
            yield frozenset(x for i, x in enumerate(items) if mask >> i & 1)

    table = {}
    for v in order:                       # children are eliminated before parents
        bag, t, best_from = bags[v], {}, []
        for c in children[v]:
            shared, best = bags[c] & bag, {}
            for s, val in table.pop(c).items():
                key = s & shared
                val -= sum(w[x] for x in key)   # counted again at this bag
                if val > best.get(key, float("-inf")):
                    best[key] = val
            best_from.append((shared, best))
        for s in subsets(bag):
            if not independent(s):
                continue
            total = sum(w[x] for x in s)
            for shared, best in best_from:
                total += best.get(s & shared, float("-inf"))
            t[s] = total
        table[v] = t
    return sum(max(t.values()) for t in table.values())   # one table per root

Each bag enumerates at most 2^k+1 subsets, and each child's table is reduced to the shared vertices first, so the work is O(2^k · k² · n). With the example weights a=3, b=4, c=2, d=5, e=4, f=3 it returns 12, the set {b, d, f}. A test harness compared it with brute force on 400 random graphs of up to ten vertices, and checked the edge-coverage and connectivity rules on every decomposition. Keep such a harness next to any treewidth DP you write; the subtract-the-overlap step is the usual bug.

Nice tree decompositions

Textbook algorithms use nice tree decompositions, where every node is one of four kinds: a leaf with an empty bag, an introduce node that adds one vertex to its child's bag, a forget node that removes one vertex, and a join node with two children carrying identical bags. Any decomposition converts into a nice one of the same width with O(k · n) nodes.

Nice decompositions make proofs and hand-written DPs simpler, because each node type has a short, separate update rule. The generic join in the code above does the same work in one place. Use nice decompositions when the per-node logic is intricate, as in counting problems or Hamiltonian-path variants, and the direct form when the state is simple.

Exact treewidth and solvers

Deciding whether treewidth is at most k is NP-complete, as Arnborg, Corneil and Proskurowski showed in 1987, and they also gave an algorithm polynomial for each fixed k. Bodlaender's 1996 algorithm runs in linear time for fixed k, but its dependence on k is so large that it is not used in practice.

Practical exact solvers came out of the PACE challenges in 2016 and 2017, which included exact and heuristic treewidth tracks; their open-source solvers handle many graphs with hundreds or thousands of vertices. The PACE file formats are worth adopting even for your own tools: a graph file begins with p tw <vertices> <edges> followed by one edge per line, and a decomposition file begins with s td <bags> <max bag size> <vertices>, followed by b <id> <vertices...> lines and tree edges. A common checker then validates any solver's output.

Where it pays off

Courcelle's theorem generalizes all of this: any property expressible in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. The constants are astronomical, so treat it as a sign that a fast algorithm exists, then write the specific DP.

Failure modes

• Width blow-up: the DP is exponential in width, so a decomposition one or two wider than necessary can multiply run time and memory by four or more. Always print the width before starting the DP.
• Disconnected graphs: elimination produces a forest. Combine the root tables, as the code does, or the answer covers only one component.
• Double counting: forgetting to subtract the shared-vertex weight inflates results; test against brute force.
• Large dense graphs: random or dense graphs have treewidth close to n, and no decomposition will save you. Check the lower bound first.
• Memory: each table holds up to 2^k+1 entries. Free child tables as soon as they are consumed, as the code does with table.pop.

Trade-offs

Heuristic orderings are fast and usually close to optimal; exact solvers cost minutes to hours but can halve DP time when width dominates. Min-degree is faster than min-fill and worse on most inputs. A direct DP over arbitrary bags is shorter than a nice-decomposition DP; the nice form is easier to prove correct. For some problems, the classic tree DP techniques carry over directly, and the general principles in dynamic programming still apply to state design.

What to do next

1. Compute degeneracy and a min-fill width for your graph; if the width is above about 25, consider other methods.
2. Write your graph in the PACE .gr format and try an exact PACE solver if the bounds disagree.
3. Copy the MWIS DP, run it with a brute-force test harness, then adapt the table state to your problem.
4. Implement minor-min-width and compare it with degeneracy on your data.
5. For SAT-like problems, read SAT solving and compare treewidth-based counting with CDCL.