pathwidth

Pathwidth is a graph parameter that measures how closely a graph resembles a path. It is defined through path decompositions. A path decomposition of a graph G = (V,E) is a sequence of subsets, called bags, X1, X2, ..., Xm, of V such that: the union of all bags is V; every edge uv ∈ E is contained in some bag (i.e., {u,v} ⊆ Xi for some i); and for every vertex v ∈ V, the set of indices i with v ∈ Xi forms a contiguous interval. The width of a path decomposition is the maximum bag size minus one, and the pathwidth pw(G) is the minimum width over all path decompositions of G.

Examples illustrate the concept: a path on n vertices has pw = 1; a cycle Cn has pw = 2 for n ≥ 4; a complete graph Kn has pw = n − 1.

Pathwidth is related but distinct from the more general treewidth. For any graph G, pw(G) is at least its treewidth tw(G). In general the two parameters can differ substantially; complete graphs attain pw = tw = n − 1, while paths have both equal to 1. The study of pathwidth focuses on understanding how the structure of a graph can be organized along a linear sequence of bags, in contrast to the more flexible tree decompositions used for treewidth.

Computational aspects include that computing the exact pathwidth is computationally challenging (NP-hard in general). The associated decision problem pw(G) ≤ k is NP-complete when k is part of the input, but it is fixed-parameter tractable with respect to k, allowing specialized algorithms for small pathwidth. Applications often involve dynamic programming along a path decomposition, yielding efficient algorithms for problems that remain hard in general graphs when the pathwidth is small.