---
tag: YDEKMEQF90
kind: concept
name: Pathwidth
aliases: [path-decomposition, path-width]
sources:
  - wikipedia: en:5133142@r1369812266
    locator: Pathwidth
    note: adopted
    mention: wikipedia://en/5133142
    sections: [Summary]
same_as:
  wikidata: Q7144893
  wikipedia: Pathwidth
inventory: [35FFR7E7XJ]
---

## Summary

In graph theory, a **path decomposition** of a [[graph|00C0BR7D7H]] $G$ is, informally, a representation of $G$ as a "thickened" [[path graph|075WR6W3Y3]], and the **pathwidth** of $G$ is a number that measures how much the path was thickened to form $G$. More formally, a path-decomposition is a sequence of [[subsets|0BJR9QR08E]] of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous [[subsequence|0F1PR74BRX]] of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as **interval thickness** (one less than the maximum clique size in an interval supergraph of $G$), **vertex separation number**, or **node searching number**.