Dynamic survey on rank-width

2013-04-26 · 2013

math

Note added on Jan. 2019: An improved version of this article has been published as a journal paper in Discrete Applied Mathematics.

Dynamic survey on rank-width and related width parameters of graphs

Sang-il Oum

Aug 19, 2013

 

This is an incomplete on-going survey on rank-width and its related parameters. I intend to expand it slowly.
By no means, this will be complete.
Please feel free to leave comments or give me suggestions.

 

1  Definitions

Rank-width was introduced by Oum and Seymour [35].
Clique-width is defined and investigated first by Courcelle and Olariu [5] published in 2000, but the operations for clique-width has been introduced by Courcelle, Engelfriet, and Rozenberg [4] in 1993.
NLC-width was introduced by Wanke [40] in 1994.
Boolean-width was introduced by Bui-Xuan, Telle, and Vatshelle [2].

 

2  Well-quasi-ordering

Oum [31] proved that graphs of bounded rank-width are well-quasi-ordered under taking pivot-minors.
This result has been generalized to

1. skew-symmetric or symmetric matrices over a fixed finite field
   by Oum [34],
    
2. σ-symmetric matrices over a fixed finite field by Kante [20].
    

 

3  Forbidden vertex-minors

Oum [29] showed that if a graph has rank-width k, then so is its vertex-minor.
This, together with the well-quasi-ordering theorem [31] implies that
for each k, there exists a list of finitely many graphs such that a graph has rank-width at most k if and only if none of its vertex-minors is isomorphic to a graph in the list.

 

Oum [29] showed that for each k, the forbidden vertex-minor for rank-width at most k has at most (6^k+1−1)/5 vertices.
So in theory, we can enumerate all of them by an algorithm for fixed k.

 

However, it is not clear how to find the list of forbidden vertex-minors
for graphs of linear rank-width at most k,
as there are no analogous upper bound on the size of forbidden vertex-minors. Jeong, Kwon, and Oum [16]
showed that there are at least 3^Ω(3k) forbidden vertex-minors for linear rank-width at most k.

 

4  Hardness

Computing rank-width is NP-hard. It can be easily deduced by combining the following known facts. This reduction is mentioned in [30].

1. Seymour and Thomas [37] proved that computing branch-width is NP-hard.
   Kloks, Kratochvíl, and Müller [21] even showed that it is NP-hard to compute branch-width of interval graphs.
    
2. Hicks and McMurray Jr. [13] and independently Mazoit and Thomassé [26] showed that if a graph G is not a forest, then the branch-width of the cycle matroid M(G) is equal to the branch-width of G.
    
3. Oum [29] showed that the branch-width of a binary matroid is equal to the rank-width of its fundamental graph. Every graphic matroid is binary.
    

It is not known to me whether computing linear rank-width is NP-hard.

 

Computing clique-width is NP-hard, shown by Fellows, Rosamond, Rotics, and Szeider [8].

 

Computing the relative clique-width is also NP-complete, shown by Müller and Urner [27]. The relative clique-width [24] is a clique-width restricted to a fixed decomposition tree.

 

Gurski and Wanke [12] proved that computing NLC-width is
also NP-hard via a reduction from the tree-width.

 

5  Finding an approximate rank-decomposition for a fixed k

 

Oum and Seymour [35] provided an algorithm to
find a rank-decomposition of width at most 3k+1 or confirm that the input graph has rank-width bigger than k
in time O(8^k n⁹ logn).
(Here, n is the number of vertices of the input graph.)
The running time was later improved by Oum [30]
to O(8^k n⁴).

 

This allows us to find a rank-decomposition of width at most c′ times rank-width
if the rank-width is at most clogn in polynomial time.
This is used in the quantum information theory (see Van den Nest, Dür, Vidal, and Briegel [38]) for their study on measurement-based quantum computation.

 

If we do not mind having bigger function in k, then in the same paper [30], it is possible to find a rank-decomposition of width 3k−1 or
confirm that the rank-width is bigger than k in time O(f(k)n³).

 

We do not know whether there is an algorithm to find an approximate rank-decomposition of width O(k) in time O(c₁^k n^c) for c ≤ 3
when an input graph has rank-width at most k.

 

These algorithms can be used as a tool to construct an expression for clique-width decomposition, which are essential in many algorithmic applications.

 

6  Deciding rank-width at most k for fixed k

There is a general algorithm of Oum and Seymour [36] which can construct a branch-decomposition of any symmetric submodular function in time O(n^8k+c), and if we apply it to rank-width, we get an algorithm of running time O(n^8k+12logn).
Note that a simple general algorithm for path-width of any symmetric submodular function
was developed by Nagamochi [28], which is applicable to linear rank-width in time O(n^2k+4).

 

Courcelle and Oum [6] first constructed an algorithm to decide, for fixed k, whether rank-width is at most k in time O(f(k)n³). But their algorithm uses the monadic second-order logic formula and does not provide an explicit rank-decomposition even if it exists.

 

This problem was solved later.
Hlinený and Oum [14] constructed an algorithm to decide whether rank-width is at most k
and find a rank-decomposition of width at most k, if it exists, in time O(f(k)n³).
Here, f(k) is growing very fast with k, because the algorithm uses the monadic second-order logic as well as the list of forbidden minors for branch-width at most k for matroids representable over a fixed finite field.
Geelen, Gerards, Robertson, and Whittle [11] proved that the forbidden minors for matroids of branch-width at most k have at most (6^k−1)/5 elements. This implies that we can construct an explicit algorithm for testing rank-width at most k and constructing a rank-decomposition of width at most k if it exists. (If there was no upper bound, then it may be impossible to enumerate all forbidden minors.)

 

One can also decide whether the linear rank-width is at most k in time O(n³) by using the well-quasi-ordering theorem [31] and monadic second-order logic formula to test vertex-minors [6]. But it is not known how to find the list of forbidden vertex-minors.

 

 

Wahlström [39] showed that deciding whether clique-width is at most k and finding a k-expression can be done in time O^*((2k+1)ⁿ).

 

Espelage, Gurski, and Wanke [7] constructed an algorithm to decide whether a graph has clique-width at most k for graphs of bounded tree-width.

 

7  Relation to Tree-width

 

Kante [19] showed that rank-width is at most 4k+2 if the tree-width is k.
Later,
Oum [32] showed that rank-width is at most k+1 if tree-width is k.
In fact, it is shown that

if *G* has branch-width *k*, then the incidence graph of *G* has rank-width *k* or *k*−1, unless *k*=0.

 

Corneil and Rotics [3] showed that the clique-width is at most 3·2^k−1 if the tree-width is k.
Moreover, they proved that for each k, there is a graph G having tree-width k and clique-width at least 2^{k/2−1}.
This also implies that there are graphs having rank-width at most k+1 and clique-width at least 2^{k/2−1} for each k.

 

Kwon and Oum [22] proved that every graph of rank-width k
is a pivot-minor of a graph of tree-width at most 2k.
They also proved that every graph of linear rank-width k is a pivot-minor of a graph of path-width k+1.
In other words,
a set I of graphs has bounded rank-width
if and only if it is a set of pivot-minors of graphs of bounded tree-width.

 

Fomin, Oum, and Thilikos [10] showed that when graphs are planar, or H-minor-free, then
having bounded tree-width is equivalent to having bounded rank-width.
For instance, if a graph G is planar and has rank-width k,
then tree-width is at most 72k−2.
If G of rank-width k
has no K_r minor with r > 2, then tree-width is at most 2^O(rloglogr)k.
This is already proven in Courcelle and Olariu [5] without explicit bounds because they use logical tools.

 

8  Exact Algorithms

There are small number of papers dealing with computing exact value of rank-width or related width parameters.

 

| | | | | :---------------: | :-------------------------------: | :--------------------: | | Width Parameter | Running time | Paper | | Rank-width | *O*^\*(2^*n*) | Oum \[[33](#Oum2009)\] | | Linear rank-width | *O*^\*(2^*n*) | forklore (trivial) |

The running time to compute clique-width exactly seems open.

 

Müller and Urner [27] proved that NLC-width can be computed in time O(3ⁿ n) for an n-vertex graph.
When they gave a talk at GROW2007 about this result, they further claimed that clique-width can be computed in time O^*(3ⁿ) by finding a polynomial-time algorithm to compute relative clique-width [24] but later Ruth Urner emailed me that there was a mistake.

 

Branch-width of graphs can be computed in time O^*((2√3)ⁿ), shown by Fomin, Mazoit, and Todinca [9].

 

9  Random graphs

Lee, Lee, and Oum [23] showed that asymptotically almost surely the Erdös-Rényi random graph G(n,p) has rank-width n/3−O(1) if p is a constant between 0 and 1.
Furthermore, [1/(n)] << p ≤ [1/2], then the rank-width is [(n)/3]−o(n),
and if p = c/n and c > 1, then rank-width is at least r n for some r = r(c).

 

Since the clique-width is at least rank-width, this also gives a lower bound for clique-width.

 

Adler, Bui-Xuan, Rabinovich, Renault, Telle, and Vatshelle [1] claimed that boolean-width of G(n,p) for fixed 0 < p < 1 is Θ(log² n) asymptotically almost surely.

 

**Remark.** Johansson \[[17](#Johansson1998)\] (also in his Ph.D. thesis \[[18](#Johansson2001b)\]) claimed in a conference paper that NLC-width and clique-width of a random graph *G*(*n*,*p*) for a fixed 0 \< *p* \< 1 is Ω(*n*) almost surely. But we believe that the proof is incorrect.

 

In 2009, Marecek \[[25](#Marecek2009)\] studied the rank-width of *G*(*n*,1/2), though I believe that the first version of his paper on arxiv[¹](#tthFtNtAAB) is incorrect; Later versions have different proofs.

 

10  Explicit graphs

Jelínek [15] proved that an n×n grid has rank-width n−1.

 

11  Software

Philipp Klau Krause implemented a simple dynamic programming algorithm
to compute the rank-width of a graph².
This software is now included in the open source mathematics software
package called SAGE; see the
manual³.

 

Apparently Friedmanský wrote Master’s thesis on “implementation of
optimization of a graph algorithm for computing rank-width”⁴ under the
supervision of Robert Ganian.

 

Acknowledgment

I would like to thank careful readers who kindly emailed me
suggestions for this survey.

• August 2013: Jisu Jeong found a typo.
   
• August 2013: Chiheon Kim pointed out a mistake on the statement
  on the consequence of a theorem by Corneil and Rotics.
   
• July 2013: J. Marecek explained his paper on arxiv.
   
• July 2013: F. Gurski provided a journal version of his paper
  with E. Wanke cited
  in the survey.
   

 

 

References

• [1]
  Isolde Adler, Binh-Minh Bui-Xuan, Yuri Rabinovich, Gabriel Renault, Jan Arne
  Telle, and Martin Vatshelle.
  On the Boolean-width of a graph: structure and applications.
  In Graph-theoretic concepts in computer science, volume 6410 of
  Lecture Notes in Comput. Sci., pages 159-170. Springer, Berlin, 2010.
  doi:10.1007/978-3-642-16926-7_16.
   
• [2]
  Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle.
  Boolean-width of graphs.
  Theoret. Comput. Sci., 412(39):5187-5204, 2011.
  doi:10.1016/j.tcs.2011.05.022.
   
• [3]
  Derek G. Corneil and Udi Rotics.
  On the relationship between clique-width and treewidth.
  SIAM J. Comput., 34(4):825-847 (electronic), 2005.
  doi:10.1137/S0097539701385351.
   
• [4]
  Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.
  Handle-rewriting hypergraph grammars.
  J. Comput. System Sci., 46(2):218-270, 1993.
  doi:10.1016/0022-0000(93)90004-G.
   
• [5]
  Bruno Courcelle and Stephan Olariu.
  Upper bounds to the clique width of graphs.
  Discrete Appl. Math., 101(1-3):77-114, 2000.
  doi:10.1016/S0166-218X(99)00184-5.
   
• [6]
  Bruno Courcelle and Sang-il Oum.
  Vertex-minors, monadic second-order logic, and a conjecture by
  Seese.
  J. Combin. Theory Ser. B, 97(1):91-126, 2007.
  doi:10.1016/j.jctb.2006.04.003.
   
• [7]
  Wolfgang Espelage, Frank Gurski, and Egon Wanke.
  Deciding clique-width for graphs of bounded tree-width.
  Journal of Graph Algorithms and Applications, 7(2):141-180,
  2003.
   
• [8]
  Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider.
  Clique-width is NP-complete.
  SIAM J. Discrete Math., 23(2):909-939, 2009.
  doi:10.1137/070687256.
   
• [9]
  Fedor Fomin, Frédéric Mazoit, and Ioan Todinca.
  Computing branchwidth via efficient triangulations and blocks.
  Discrete Appl. Math., 157(12):2726-2736, 2009.
  doi:10.1016/j.dam.2008.08.009.
   
• [10]
  Fedor V. Fomin, Sang-il Oum, and Dimitrios M. Thilikos.
  Rank-width and tree-width of H-minor-free graphs.
  European J. Combin., 31(7):1617-1628, 2010.
  doi:10.1016/j.ejc.2010.05.003.
   
• [11]
  James F. Geelen, A. M. H. Gerards, Neil Robertson, and Geoff Whittle.
  On the excluded minors for the matroids of branch-width k.
  J. Combin. Theory Ser. B, 88(2):261-265, 2003.
   
• [12]
  Frank Gurski and Egon Wanke.
  Line graphs of bounded clique-width.
  Discrete Math., 307(22):2734-2754, 2007.
  doi:10.1016/j.disc.2007.01.020.
   
• [13]
  Illya V. Hicks and Nolan B. McMurray Jr.
  The branchwidth of graphs and their cycle matroids.
  J. Combin. Theory Ser. B, 97(5):681-692, 2007.
  doi:10.1016/j.jctb.2006.12.007.
   
• [14]
  Petr Hlinený and Sang-il Oum.
  Finding branch-decompositions and rank-decompositions.
  SIAM J. Comput., 38(3):1012-1032, 2008.
  doi:10.1137/070685920.
   
• [15]
  Vít Jelínek.
  The rank-width of the square grid.
  Discrete Appl. Math., 158(7):841-850, 2010.
  doi:10.1016/j.dam.2009.02.007.
   
• [16]
  Jisu Jeong, O-joung Kwon, and Sang-il Oum.
  Excluded vertex-minors for graphs of linear rank-width at most k.
  In Natacha Portier and Thomas Wilke, editors, 30th International
  Symposium on Theoretical Aspects of Computer Science (STACS 2013), volume 20
  of Leibniz International Proceedings in Informatics (LIPIcs), pages
  221-232, Kiel, Germany, 2013. Schloss Dagstuhl. Leibniz-Zent. Inform.
  URL: http://drops.dagstuhl.de/opus/volltexte/2013/3936, doi:10.4230/LIPIcs.STACS.2013.221.
   
• [17]
  Öjvind Johansson.
  Clique-decomposition, NLC-decomposition, and modular
  decomposition-relationships and results for random graphs.
  In Proceedings of the Twenty-ninth Southeastern International
  Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL,
  1998), volume 132, pages 39-60, 1998.
   
• [18]
  Öjvind Johansson.
  Graph decomposition using node labels.
  PhD thesis, Royal Institute of Technology, 2001.
   
• [19]
  Mamadou Moustapha Kanté.
  Vertex-minor reductions can simulate edge contractions.
  Discrete Appl. Math., 155(17):2328-2340, 2007.
  doi:10.1016/j.dam.2007.06.011.
   
• [20]
  Mamadou Moustapha Kanté.
  Well-quasi-ordering of matrices under Schur complement and
  applications to directed graphs.
  European J. Combin., 33(8):1820-1841, 2012.
  doi:10.1016/j.ejc.2012.03.034.
   
• [21]
  Ton Kloks, Jan Kratochvíl, and Haiko Müller.
  Computing the branchwidth of interval graphs.
  Discrete Appl. Math., 145(2):266-275, 2005.
  doi:10.1016/j.dam.2004.01.015.
   
• [22]
  O-joung Kwon and Sang-il Oum.
  Graphs of small rank-width are pivot-minors of graphs of small
  tree-width.
  Discrete Appl. Math., 2013.
  doi:10.1016/j.dam.2013.01.007.
   
• [23]
  Choongbum Lee, Joonkyung Lee, and Sang-il Oum.
  Rank-width of random graphs.
  J. Graph Theory, 70(3):339-347, July/August 2012.
  doi:10.1002/jgt.20620.
   
• [24]
  Vadim Lozin and Dieter Rautenbach.
  The relative clique-width of a graph.
  J. Combin. Theory Ser. B, 97(5):846-858, 2007.
  doi:10.1016/j.jctb.2007.04.001.
   
• [25]
  Jakub Marecek.
  Some probabilistic results on width measures of graphs.
  Unpublished, 08 2009.
  arXiv:0908.1772v1.
   
• [26]
  Frédéric Mazoit and Stéphan Thomassé.
  Branchwidth of graphic matroids.
  In Anthony Hilton and John Talbot, editors, Surveys in
  Combinatorics 2007, volume 346 of London Math. Soc. Lecture Note Ser.,
  pages 275-286. Cambridge Univ. Press, Cambridge, 2007.
   
• [27]
  Haiko Müller and Ruth Urner.
  On a disparity between relative cliquewidth and relative NLC-width.
  Discrete Appl. Math., 158(7):828-840, 2010.
  doi:10.1016/j.dam.2009.06.024.
   
• [28]
  Hiroshi Nagamochi.
  Linear layouts in submodular systems.
  In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, *
  ISAAC ’12, volume 7676 of *Lecture Notes in Comput. Sci., pages
  475-484. Springer Berlin Heidelberg, 2012.
  doi:10.1007/978-3-642-35261-4_50.
   
• [29]
  Sang-il Oum.
  Rank-width and vertex-minors.
  J. Combin. Theory Ser. B, 95(1):79-100, 2005.
  doi:10.1016/j.jctb.2005.03.003.
   
• [30]
  Sang-il Oum.
  Approximating rank-width and clique-width quickly.
  ACM Trans. Algorithms, 5(1):Art. 10, 20, 2008.
  doi:10.1145/1435375.1435385.
   
• [31]
  Sang-il Oum.
  Rank-width and well-quasi-ordering.
  SIAM J. Discrete Math., 22(2):666-682, 2008.
  doi:10.1137/050629616.
   
• [32]
  Sang-il Oum.
  Rank-width is less than or equal to branch-width.
  J. Graph Theory, 57(3):239-244, 2008.
  doi:10.1002/jgt.20280.
   
• [33]
  Sang-il Oum.
  Computing rank-width exactly.
  Inform. Process. Lett., 109(13):745-748, 2009.
  doi:10.1016/j.ipl.2009.03.018.
   
• [34]
  Sang-il Oum.
  Rank-width and well-quasi-ordering of skew-symmetric or symmetric
  matrices.
  Linear Algebra Appl., 436(7):2008-2036, 2012.
  doi:10.1016/j.laa.2011.09.027.
   
• [35]
  Sang-il Oum and Paul Seymour.
  Approximating clique-width and branch-width.
  J. Combin. Theory Ser. B, 96(4):514-528, 2006.
  doi:10.1016/j.jctb.2005.10.006.
   
• [36]
  Sang-il Oum and Paul Seymour.
  Testing branch-width.
  J. Combin. Theory Ser. B, 97(3):385-393, 2007.
  doi:10.1016/j.jctb.2006.06.006.
   
• [37]
  Paul Seymour and Robin Thomas.
  Call routing and the ratcatcher.
  Combinatorica, 14(2):217-241, 1994.
  doi:10.1007/BF01215352.
   
• [38]
  M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel.
  Classical simulation versus universality in measurement-based quantum
  computation.
  Phys. Rev. A, 75:012337, Jan 2007.
  doi:10.1103/PhysRevA.75.012337.
   
• [39]
  Magnus Wahlström.
  New plain-exponential time classes for graph homomorphism.
  Theory Comput. Syst., 49(2):273-282, 2011.
  doi:10.1007/s00224-010-9261-z.
   
• [40]
  Egon Wanke.
  k-NLC graphs and polynomial algorithms.
  Discrete Appl. Math., 54(2-3):251-266, 1994.
  doi:10.1016/0166-218X(94)90026-4.

 

---

Footnotes:

 

¹https://arxiv.org/pdf/0908.1772v1.pdf

 

²http://pholia.tdi.informatik.uni-frankfurt.de/~philipp/software/rw.shtml

 

³http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/rankwidth.html

 

⁴http://is.muni.cz/th/172614/fi_m/thesis.pdf