15
$\begingroup$

When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree decomposition where the tree is binary and its height is $O(\log n)$. This can be achieved while keeping the width of the decomposition at most $3w$. (See e.g. "Parallel algorithms with optimal speedup for bounded treewidth", by Bodlaender and Hagerup). So, logarithmic depth is a property of a tree decomposition which we can get almost for free.

My question is if there exists a similar result for clique-width, or perhaps a counter-example. In other words, given a clique-width expression for $G$ using $k$ labels, does there always exist a clique-width expression of height $O(\log n)$ for $G$, that uses at most $f(k)$ labels? Here, the height is defined naturally as the height of the parse tree of the clique-width expression.

If a statement similar to the above is not known, is there an example of an $n$-vertex graph $G$ with small clique-width $k$, such that the only way to construct $G$ with $f(k)$ labels is to use an expression with large depth?

$\endgroup$
5
$\begingroup$

After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else.

It is in fact possible to re-balance clique-width expressions so that they have logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote Theorem 4.4 from the paper:

"Every graph of clique-width or NLC-width $k$ is the value of a 3-balanced clique-width expression of clique-width or NLC-width at most $k \times 2^{k+1}$"

The catch here is that the number of labels blows up exponentially in the balancing. It seems that for clique-width no better result is currently known. The same paper gives a similar result with only a constant blow-up for rankwidth, but this doesn't help, since the difference between clique-width and rankwidth can be exponential in the worst case.

$\endgroup$
  • 3
    $\begingroup$ The first result dealing with balanced clique-width expressions is by Courcelle and Vanicat (DAM 131(1):129-150, 2003). The WG'07 paper generalizes the techniques in the 2003 paper and give sufficient conditions for a graph algebra to obtain balanced expressions. My conjecture was that we cannot avoid the exponential blow-up, but I never try to prove or disprove it. At least our technique cannot avoid the exponential blow-up. $\endgroup$ – M. kanté Dec 6 '14 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.