Lesson 5

The third condition in the definition is the one that makes the decomposition useful. Suppose we remove a bag from the decomposition tree. The remaining tree breaks into components. In the original graph, vertices living in different components can communicate only through the removed bag.

For example, after fixing what happens with vertices \(b,c,f\), the vertices on the left and on the right can be treated independently. This is the same idea as dynamic programming on trees, only now the boundary may contain several vertices.