Clique-width expressions with logarithmic depth

Question

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 3ドルw$. (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?

• vzn: treewidth / cliquewidth wikipedia

Answer 1

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.

• M. kanté: 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.