Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$ is a binary tree with $|V(G)|$ leaves and $\chi$ is a bijection mapping the leaves of $T$ to the vertices of $G$. Every edge $e \in E(T)$ of the tree $T$ partitions the vertices of the graph $G$ into two parts $V_e$ and $V \backslash V_e$ according to the leaves of the two connected components in $T - e$. The width of an edge $e$ of the tree is the number of edges of a graph $G$ that have exactly one endpoint in $V_e$ and another endpoint in $V \backslash V_e$. The width of the decomposition $(T,\chi)$ is the largest width over all edges of the tree $T$. The carvingwidth of a graph is the minimum width over all decompositions as above.
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.
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
[?]
(decision variant)
|
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 |