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

<p>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:</p>

<p>"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}$"</p>

<p>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.</p>

CC BY-SA 3.0
2014-12-06T21:40:11.087Z
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.
M. kanté
CC BY-SA 3.0
2014-12-05T13:38:11.000Z
2014-12-05T13:38:11.000Z
Michael Lampis
<p>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.</p>

<p>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. </p>

<p>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?</p>

CC BY-SA 3.0
2014-02-10T16:11:02.140Z
[treewidth](http://en.wikipedia.org/wiki/Tree_width) / [cliquewidth](http://en.wikipedia.org/wiki/Clique-width) wikipedia
vzn
<treewidth><parameterized-complexity><fixed-parameter-tractable><cliquewidth>
Clique-width expressions with logarithmic depth
Michael Lampis
# Clique-width expressions with logarithmic depth

(Asked by: username_0 on 2014-02-10)

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?

**Tags:** treewidth, parameterized-complexity, fixed-parameter-tractable, cliquewidth

> **Comments:**
> **username_1**: [treewidth](http://en.wikipedia.org/wiki/Tree_width) / [cliquewidth](http://en.wikipedia.org/wiki/Clique-width) wikipedia  

---

## 1 answers

### Answer by username_0 on 2014-12-05. Score: 6

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.

> **Comments:**
> **username_2**: 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.  

---

