Pathwidth¶

Measure how narrowly a graph can be arranged along a path by minimizing the largest bag size minus one over path decompositions with vertex continuity and edge coverage.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2460
Origin domain: graph theory
Subdomain: graph width parameters
Aliases: Path-width

Core Idea¶

The pathwidth of a finite undirected graph \(G\) is the minimum, over all path decompositions \((B_1,\ldots,B_m)\), of \(\max_i |B_i|-1\). A path decomposition is a sequence of vertex bags such that every vertex occurs in at least one bag, every edge has both endpoints together in some bag, and for each vertex the indices of bags containing it form a contiguous interval. The subtraction of one is conventional and makes a path with at least one edge have pathwidth one. Empty-graph and isolated-vertex conventions should be stated when they matter.^[1]

A path decomposition exposes a graph through a moving frontier. When a vertex first enters a bag, it can support edges to vertices already active; contiguity prevents it from disappearing and later returning; when it leaves, every future obligation involving it must already be discharged. The largest simultaneous frontier determines width. Minimizing this bottleneck over all valid sequences yields a graph invariant. Equivalent formulations through vertex separation and node searching translate the same frontier burden into an ordering or search game, subject to their offset and convention choices.^[2]

Pathwidth is not the number of vertices in a longest path, graph diameter, bandwidth, cutwidth, or treewidth. A path decomposition is a tree decomposition whose decomposition tree is restricted to be a path, so \(\operatorname{tw}(G)\leq\operatorname{pw}(G)\), often strictly. Bag width counts vertices minus one, whereas a separator or search-number formulation may shift by one. The parameter applies to disconnected graphs and need not be witnessed by a subgraph that is itself a path. Approximation, fixed-parameter recognition, and forbidden-minor theorems are results about the invariant rather than parts of its definition.^[3]

Structural Signature¶

Input graph. A finite undirected graph supplies vertices and adjacency obligations.
Index path. A linear order of bag positions restricts the decomposition's global shape.
Vertex bags. Subsets of vertices record the currently retained interface.
Vertex coverage. Every graph vertex appears somewhere in the sequence.
Edge coverage. Every edge has a bag containing both endpoints.
Interval condition. For each vertex, bag membership occupies one contiguous block of indices.
Bag width. The largest bag cardinality minus one measures the candidate decomposition.
Global minimum. Optimization over all valid decompositions makes the value graph-invariant.

What It Is Not¶

Not treewidth. Treewidth permits a branching decomposition tree; pathwidth imposes a linear one.
Not bandwidth. Bandwidth minimizes maximum endpoint distance in a vertex labeling, not simultaneous bag size.
Not cutwidth. Cutwidth counts edges crossing an ordering cut rather than active boundary vertices.
Not longest-path length. A graph can contain long paths while retaining small pathwidth.
Not one chosen decomposition. The invariant is the minimum across all valid path decompositions.
Not path cover number. Covering vertices by graph paths is a different combinatorial optimization problem.

Scope of Application¶

The abstraction is literal wherever practitioners can identify the same constitutive roles, apply the same boundary tests, and obtain the same kind of output. The following habitats are uses of Pathwidth itself, not metaphors based only on resemblance.

Structural graph theory. Classifying graphs by closeness to a thickened linear structure.
Dynamic programming. Processing graph problems along bags while storing only boundary states.
Parameterized complexity. Treating pathwidth as a structural parameter for fixed-parameter algorithms.
Graph searching. Relating a minimum search frontier to decomposition width under stated conventions.
Layout problems. Using vertex-separation formulations to reason about linear arrangements.
Minor theory. Studying obstruction sets and forest-minor characterizations for bounded pathwidth.

Clarity¶

A clear account of Pathwidth must preserve the recognition invariant stated in the Core Idea rather than rely on the title alone. State all three decomposition conditions and the bag-size-minus-one width convention. Distinguish the width of one supplied decomposition from the graph's minimum pathwidth. Name graph class assumptions, including finite, undirected, simple, or multigraph conventions. When translating to vertex separation or searching, reconcile offsets and monotonicity rules explicitly. These declarations are not editorial extras: each changes what observations count, which transformations are licensed, and what conclusion can be drawn. A reader should be able to reconstruct the input, the operative rule, the output, and at least one defeater from the account without consulting an implementation or guessing an unstated convention.

Manages Complexity¶

Pathwidth manages complexity by replacing a diffuse field of observations or possible operations with a bounded role structure: input graph supplies a finite undirected graph supplies vertices and adjacency obligations.; index path supplies a linear order of bag positions restricts the decomposition's global shape.; vertex bags supplies subsets of vertices record the currently retained interface.; vertex coverage supplies every graph vertex appears somewhere in the sequence.; edge coverage supplies every edge has a bag containing both endpoints.. The compression is useful because it localizes disagreement. One can ask whether the input was properly formed, whether a constitutive relation held, whether an alternative explanation defeats the inference, or whether the output was overinterpreted. The same compression can mislead when its discarded detail is exactly what the decision requires. A reference-grade use therefore reports both the invariant retained and the information intentionally lost.

Abstract Reasoning¶

Verify that every vertex appears in the proposed bag sequence.
Check that each edge has a common bag rather than merely adjacent endpoint bags.
For every vertex, verify that its bag indices form an interval.
Compute the maximum bag size and subtract one under the declared convention.
Construct lower bounds using separators, minors, brambles, or equivalent layout obligations.
Construct upper bounds by exhibiting a valid decomposition and simplifying unnecessary bags.
Match lower and upper bounds or retain the best justified interval when exact minimization is unavailable.
Test the candidate interpretation against the nearest named confusable rather than accepting a shared surface feature.
State the conclusion at the same scope as the source conditions, and retain uncertainty or nonuniqueness where the construct does not remove it.

Knowledge Transfer¶

The strict upward abstraction is Decomposition. Pathwidth instantiates Decomposition because it represents a graph through overlapping components that preserve vertex and edge information, with a path-shaped overlap discipline and an optimized bottleneck. Within graph width parameters, the full mechanism transfers literally when the same roles and boundary tests recur. Beyond that domain, only the parent-level skeleton should travel. Reusing the label Pathwidth after removing its constitutive vocabulary would hide a change of mechanism behind an analogy. The honest transfer rule is therefore two-stage: recognize the domain-specific pattern first, then lift only the parent relation that remains invariant under a substrate change.

Examples¶

Canonical¶

For the path graph \(v_1v_2\cdots v_n\), take bags \(B_i=\{v_i,v_{i+1}\}\). Every edge is covered and each internal vertex occurs in two consecutive bags, so the width is one. A graph containing an edge cannot have width zero, because width zero bags contain only one vertex and cannot cover that edge. Therefore every nontrivial path has pathwidth one.

Mapped back: input and conventions → constitutive role test → bounded output → explicit interpretation and defeater check.

Applied / In Practice¶

A scheduling or state-space algorithm receives a graph together with bags of size at most six. It processes bags from left to right, introduces and forgets vertices, and stores partial solutions indexed by states of the active bag. The decomposition certifies width at most five. It does not prove pathwidth exactly five unless a separate lower bound rules out width four; runtime stated in terms of the supplied width must preserve that distinction.

Mapped back: field observation or problem → candidate recognition → confusable and limit checks → appropriately scoped conclusion.

Structural Tensions¶

T1: Local bags versus global graph. Each bag is small, but validity depends on coverage and continuity across the full sequence. Diagnostic: Have all edges and every vertex interval been checked globally?
T2: Linear simplicity versus width cost. Forcing a path can make bags much larger than in a branching tree decomposition. Diagnostic: Is the application truly sequential, or would treewidth be the relevant measure?
T3: Constructive upper bound versus exact invariant. One decomposition proves only an upper bound. Diagnostic: What independent obstruction or lower-bound argument closes the gap?
T4: Equivalent formulation versus convention drift. Vertex separation and searching can use different offsets and rule sets. Diagnostic: Do both sources count the same frontier under the same convention?
T5: Parameter tractability versus instance cost. Small pathwidth can enable dynamic programming while large constants or state spaces remain. Diagnostic: Which bag-state complexity actually controls the algorithm?
T6: Autonomous invariant versus generic decomposition. Decomposition is portable; linear bag order and minimized frontier size define pathwidth. Diagnostic: Would branching the index structure change the invariant to treewidth?

Structural–Framed Character¶

Pathwidth is structural: once graph and conventions are fixed, validity and width are mathematical, although practitioners choose representations and algorithms for finding useful decompositions. The five framing criteria point in a consistent direction. Evaluative weight is limited to whether the defining conditions are met, not whether the outcome is desirable. Human practice matters to the extent that experts choose conventions, instruments, or reporting thresholds, but those choices do not make every verdict arbitrary. Institutional history explains the name and standard use; it does not replace the recognition rule. The operative vocabulary travels within the home field and closely adjacent subfields, while transfer farther away requires translation to the parent prime. Thus recognition remains disciplined even where interpretation is defeasible.

Structural Core vs. Domain Accent¶

What is skeletal. Pathwidth instantiates Decomposition because it represents a graph through overlapping components that preserve vertex and edge information, with a path-shaped overlap discipline and an optimized bottleneck. This is the part that can be expressed without the candidate's specialist nouns.

What is domain-bound. The irreducible accent is an undirected graph, a path-indexed bag sequence, edge coverage, contiguous vertex occurrence, maximum bag size minus one, and minimization over valid sequences. Remove those elements and the result is no longer Pathwidth; it is only the parent relation or a loose analogy.

Why this does not clear the prime bar. The name does not recur with unchanged diagnostics across three independent domains. What transfers is already represented by prime:decomposition. The candidate remains autonomous because its in-domain recognition rule, failure modes, and consequences are stable, but its vocabulary and interventions do not float free of the home substrate.

Pathwidth instantiates Decomposition because it represents a graph through overlapping components that preserve vertex and edge information, with a path-shaped overlap discipline and an optimized bottleneck.

The prospective workspace queue contains one strict upward edge to prime:decomposition. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Pathwidth Domain-specific

Parents (1) — more general patterns this builds on

Pathwidth is a kind of Decomposition Prime

Pathwidth instantiates Decomposition because it represents a graph through overlapping components that preserve vertex and edge information, with a path-shaped overlap discipline and an optimized bottleneck.

Hierarchy path (1) — routes to 1 parentless root

Pathwidth → Decomposition

Neighborhood in Abstraction Space¶

Pathwidth sits in a sparse region of the domain-specific corpus (73^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Treewidth. Uses tree-indexed bags and can be lower because branching is allowed.
Bandwidth. Constrains distances between adjacent vertices in a linear labeling.
Cutwidth. Counts crossing edges at ordering cuts.
Vertex separation number. An equivalent ordering invariant under the standard convention, useful as an alternate representation rather than a new definition.
Path decomposition. One certificate whose width may exceed the graph's minimum.
Path cover. A collection of paths covering vertices or edges, unrelated to the bag continuity invariant.

References¶

[1] Robertson, N., and Seymour, P. D. (1983). 'Graph Minors. I. Excluding a Forest.' Journal of Combinatorial Theory, Series B 35(1), 39–61. https://doi.org/10.1016/0095-8956(83)90079-5 registry ↩

[2] Kinnersley, N. G. (1992). 'The Vertex Separation Number of a Graph Equals Its Path-Width.' Information Processing Letters 42(6), 345–350. https://doi.org/10.1016/0020-0190(92)90234-M registry ↩

[3] Bodlaender, H. L. (1998). 'A Partial k-Arboretum of Graphs with Bounded Treewidth.' Theoretical Computer Science 209(1–2), 1–45. https://doi.org/10.1016/S0304-3975(97)00228-4 registry ↩