# Parameter: pathwidth

Definition:

A path decomposition of a graph $G$ is a pair $(P,X)$ where $P$ is a path with vertex set $\{1, \ldots, q\}$, and $X = \{X_1,X_2, \ldots ,X_q\}$ is a family of vertex subsets of $V(G)$ such that:

• $\bigcup_{p \in \{1,\ldots ,q\}} X_p = V(G)$
• $\forall\{u,v\} \in E(G) \exists p \colon u, v \in X_p$
• $\forall v \in V(G)$ the set of vertices $\{p \mid v \in X_p\}$ is a connected subpath of $P$.
The width of a path decomposition $(P,X)$ is max$\{|X_p| - 1 \mid p \in \{1,\ldots ,q\}\}$. The pathwidth of a graph $G$ is the minimum width among all possible path decompositions of $G$.

## Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

[+]Details

[+]Details

## Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability FPT [+]Details
Clique FPT [+]Details
Clique cover XP [+]Details
Colourability FPT [+]Details
Domination FPT [+]Details
Feedback vertex set FPT [+]Details
Graph isomorphism FPT [+]Details
Hamiltonian cycle FPT [+]Details
Hamiltonian path FPT [+]Details
Independent set FPT [+]Details
Maximum cut FPT [+]Details
Monopolarity Unknown to ISGCI [+]Details
Polarity XP [+]Details
Weighted clique FPT [+]Details
Weighted feedback vertex set FPT [+]Details
Weighted independent dominating set FPT [+]Details
Weighted independent set FPT [+]Details