Consider the following decomposition of a graph $G$ which is defined as a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. The function $\text{cut-bool} \colon 2^{V(G)} \rightarrow R$ is defined as $\text{cut-bool}(A)$ := $\log_2|\{S \subseteq V(G) \backslash A \mid \exists X \subseteq A \colon S = (V(G) \backslash A) \cap \bigcup_{x \in X} N(x)\}|$. Every edge $e$ in $T$ partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according to the leaves of the two connected components of $T - e$. The booleanwidth of the above decomposition $(T,L)$ is $\max_{e \in E(T)\;} \{ \text{cut-bool}(A_e)\}$. The booleanwidth of a graph $G$ is the minimum booleanwidth of a decomposition of $G$ 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
[?]
|
XP | [+]Details | |||||
Hamiltonian cycle
[?]
|
XP | [+]Details | |||||
Hamiltonian path
[?]
|
XP | [+]Details | |||||
Independent set
[?]
|
FPT | [+]Details | |||||
Maximum cut
[?]
(decision variant)
|
XP,W-hard | [+]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 |