 Pathwidth

A path decomposition of a finite graph is a sequence of vertex sets, or bags, $B_1,\dots ,B_t$, 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 ${\max }_i|B_i|-1$; pathwidth is the minimum width.

A path with at least one edge has pathwidth one using bags $\{v_i,v_{i+1}\}$. A complete graph on $n$ vertices has pathwidth $n-1$. 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.

Pathwidth is a graph-theoretical concept that measures how "tree-like" a graph is. Specifically, the pathwidth of a graph is defined in terms of how it can be decomposed into a sequence of related structures called "paths.