Parameter: treewidth

Definition:

A tree decomposition of a graph $G$ is a pair $(T, X)$, where $T = (I, F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a family of subsets of $V(G)$ such that

• the union of all $X_i$, $i \in I$ equals $V$,
• for all edges $\{v,w\} \in E$, there exists $i \in I$, such that $v, w \in X_i$, and
• for all $v \in V$ the set of nodes $\{i \in I \mid v \in X_i\}$ forms a subtree of $T$.
The width of the tree decomposition is $\max |X_i| - 1$.
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph.

[+]Details

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-Linear [+]Details
Clique FPT [+]Details
Clique cover XP [+]Details
Colourability FPT [+]Details
Domination FPT-Linear [+]Details
Feedback vertex set FPT [+]Details
Graph isomorphism FPT [+]Details
Hamiltonian cycle FPT-Linear [+]Details
Hamiltonian path FPT [+]Details
Independent set FPT [+]Details
Maximum cut FPT-Linear [+]Details
Monopolarity Unknown to ISGCI [+]Details
Polarity XP [+]Details
Weighted clique FPT-Linear [+]Details
Weighted feedback vertex set FPT [+]Details
Weighted independent dominating set FPT [+]Details
Weighted independent set FPT-Linear [+]Details