A path decomposition of a finite graph is a sequence of vertex sets, called bags, , 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 . Minimizing this width gives the pathwidth.
For the three-vertex path , bags 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 , 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 vertices. Hence its pathwidth is , showing that small width imposes a real structural restriction.
Pathwidth Created 2026-10-20 Updated 2026-11-05
A path decomposition of a finite graph is a sequence of vertex sets, or bags, , such that every vertex occurs, every edge has both endpoints in a common bag, and the bags containing any fixed vertex form a consecutive interval. Its width is ; pathwidth is the minimum width.
A path with at least one edge has pathwidth one using bags . A complete graph on vertices has pathwidth . The consecutive-occurrence condition means a vertex can be forgotten permanently after its last bag, which supports dynamic programming that stores information only about the current bag. Pathwidth is at least treewidth because a path is a special tree.