Lesson 1

We have seen that some problems become much easier on trees. This is not only because trees have few edges. The important point is that a tree can be cut into independent parts by removing one vertex. Dynamic programming uses exactly this: solve the parts separately, and remember only what happens at the small boundary.

Treewidth is a way to measure how far a graph is from this situation. Instead of asking whether one vertex separates the graph into parts, we allow small groups of vertices to play the role of separators. A graph of small treewidth is not necessarily a tree, but it can be assembled from small overlapping pieces in a tree-like way.