= Path decomposition
{disambiguate=graph theory}
A path decomposition of a finite <graph> is a sequence of vertex sets, called bags, $B_1,\ldots,B_t$, satisfying three conditions: every vertex appears, every edge has both endpoints together in a bag, and the bag indices containing each fixed vertex form an interval. Its width is $\max_i|B_i|-1$. Minimizing this width gives the <pathwidth>.
For the three-vertex path $1-2-3$, bags $\{1,2\},\{2,3\}$ have width one. Vertex two remains present while the decomposition passes from one edge to the next. The interval requirement forbids forgetting a vertex and later introducing it again, which is what permits <dynamic programming> to retain only the current bag's unresolved information.
For $K_n$, the intervals belonging to any pair of vertices intersect because their edge must be covered. Pairwise intersecting intervals have a common intersection, so some bag contains all $n$ vertices. Hence its <pathwidth> is $n-1$, showing that small width imposes a real structural restriction.
Back to article page
