Lesson 9

The main reason treewidth is important is algorithmic. Many problems that are hard on general graphs become efficient when a small-width tree decomposition is given. Here is the typical statement.

Theorem. Given a tree decomposition of width \(k\) with \(O(n)\) bags, a maximum independent set in an \(n\)-vertex graph can be found in time \(2^{O(k)}n\).

Proof. Root the decomposition tree. For a vertex \(x\) of \(T\), let \(B_{x}\) be the corresponding bag. Let \(T_{x}\) be the subtree below \(x\), and let \(V_{x}\) be the set of graph vertices appearing in bags of \(T_{x}\). For every set \(U\subseteq B_{x}\), store the best size of an independent set \(I\subseteq V_{x}\) such that \(I\cap B_{x}=U\). If \(U\) is not independent, the value is impossible.

The important point is that this state contains all information the parent needs. Let \(y\) be a child of \(x\), and put \(S=B_{x}\cap B_{y}\). The picture to keep in mind is this: after cutting the edge \(xy\) in the decomposition tree, the whole child subproblem is separated from the rest, and the only interface between the two sides is \(S\).

Any edge from the part \(V_{y}\) to the rest of the graph must have its endpoint in \(S\). Otherwise, some edge would be covered by a bag on one side of the tree edge \(xy\), while one of its endpoints would have to appear on the other side as well, violating the connectedness condition for bags containing this endpoint. Thus the solution inside the child subtree only has to agree with the parent on \(S\).

We now process bags from leaves to the root. For every bag there are at most \(2^{k+1}\) possible sets \(U\). To combine a bag with one child, we try all pairs of states that agree on the intersection of the two bags, and keep the best compatible value. This costs at most \(4^{k+1}\) checks per edge of the decomposition tree. Since there are \(O(n)\) bags, the total running time is \(2^{O(k)}n\). The answer is the largest value stored at the root.◼