On the boolean-width of a graph: structure and applications

MaRDI QIDQ6215089zbMATH OpenFDO

Authors Yuri Rabinovich, Jan Arne Telle

Publication date 19 August 2009

Abstract: We study the recently introduced boolean-width of graphs. Our structural results are as follows. Firstly, we show that almost surely the boolean-width of a random graph on $n$ vertices is $O(lo{g}^{2}n)$, and it is easy to find the corresponding decomposition tree. Secondly, for any constant $d$ a graph of maximum degree $d$ has boolean-width linear in treewidth. This implies that almost surely the boolean-width of a (sparse) random $d$-regular graph on $n$ vertices is linear in $n$. Thirdly, we show that the boolean-cut value is well approximated by VC dimension of corresponding set system. Since VC dimension is widely studied, we hope that this structural result will prove helpful in better understanding of boolean-width. Combining our first structural result with algorithms from Bui-Xuan et al cite{BTV09,BTV09II} we get for random graphs quasi-polynomial $O^{\ast }(2^{O(lo{g}^{4}n)})$ time algorithms for a large class of vertex subset and vertex partitioning problems.

This page was built for publication: On the boolean-width of a graph: structure and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6215089)