boolean width

equivalent to: clique-width, boolean width, inf-flip-width, module-width, rank-width, NLC-width

providers: ISGCI

Relations

Results

• 2012 New Width Parameters of Graphs by Vatshelle
  • page 42 : boolean width upper bounds mim-width by a linear function – Theorem 4.2.10. Let $G$ be a graph, then $mimw(G) \le boolw(G) \le mimw(G) \log_2(n)$
• 2011 Boolean-width of graphs by Bui-Xuan, Telle, Vatshelle
  • boolean width – \textbf{Definition 1.} A decomposition tree of a graph $G$ is a pair $(T,\delta)$ where $T$ is a tree having internal nodes of degree three and $\delta$ a bijection between the leaf set of $T$ and the vertex set of $G$. Removing an edge from $T$ results in two subtrees, and in a cut ${A,\overline{A}}$ of $G$ given by the two subsets of $V(G)$ in bijection $\delta$ with the leaves of the two subtrees. Let $f\colon w^V \to \mathbb{R}$ be a symmetric function that is also called a cut function: $f(A)=f(\overline{A})$ for all $A\subseteq V(G)$. The $f$-width of $(T,\delta)$ is the maximum value of $f(A)$ over all cuts ${A,\overline{A}}$ of $G$ given by the removal of an edge of $T$. … \textbf{Definition 2.} Let $G$ be a graph and $A \subseteq V(G)$. Define the set of unions of neighborhoods of $A$ across the cut ${A,\overline{A}}$ as $U(A) = {Y \subseteq \overline{A} \mid \exists X \subseteq A \land Y=N(X)\cap \overline{A}}$. The \emph{bool-dim}$\colon 2^{V(G)} \to \mathbb{R}$ function of a graph $G$ is defined as $\mathrm{bool-dim}(A)=\log_2 |U(A)|$. Using Definition 1 with $f=\mathrm{bool-dim}$ we define the boolean-width of a decomposition tree, denoted by $boolw(T,\delta)$, and the boolean-width of a graph, denoted by $boolw(G)$.
  • boolean width upper bounds rank-width by an exponential function – \textbf{Corollary 1.} For any graph $G$ and decomposition tree $(T,\gamma)$ of $G$ it holds that … $\log_2 rw(G) \le boolw(G)$ …
  • rank-width upper bounds boolean width by a polynomial function – \textbf{Corollary 1.} For any graph $G$ and decomposition tree $(T,\gamma)$ of $G$ it holds that … $boolw(G) \le \frac 14 rw^2(G)+O(rw(G))$.
• https://dl.acm.org/doi/10.1145/3486655
  • boolean width upper bounds twin-width by an exponential function – Theorem 3: Every graph with boolean-width $k$ has twin-width at most $2^{k+1}-1$.
• unknown source
  • clique-width upper bounds boolean width by a linear function
  • boolean width upper bounds clique-width by an exponential function
  • branch width upper bounds boolean width by a linear function
  • treewidth upper bounds boolean width by a computable function