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

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

2009-08-19

arxiv.org/abs/0908.2765v1

Mathematics

Combinatorics

Scientific paper

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(\log^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^*(2^{O(\log ^4 n)})$ time algorithms for a large class of vertex subset and vertex partitioning problems.

Affiliated with

Also associated with

No associations

Rating

On the boolean-width of a graph: structure and applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the boolean-width of a graph: structure and applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the boolean-width of a graph: structure and applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216506