Dynamic survey on rank-width


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

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 (6k+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(8k n9 logn).
(Here, n is the number of vertices of the input graph.)
The running time was later improved by Oum [30]
to O(8k n4).

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)n3).

We do not know whether there is an algorithm to find an approximate rank-decomposition of width O(k) in time O(c1k nc) 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(n8k+c), and if we apply it to rank-width, we get an algorithm of running time O(n8k+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(n2k+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)n3). 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)n3).
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 (6k−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(n3) 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)n).

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·2k−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 2k/2−1.
This also implies that there are graphs having rank-width at most k+1 and clique-width at least 2k/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 Kr minor with r > 2, then tree-width is at most 2O(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*(2n) Oum [33]
Linear rank-width O*(2n) 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(3n 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*(3n) 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)n), 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 Θ(log2 n) asymptotically almost surely.

Remark.
Johansson [17] (also in his Ph.D. thesis
[18]) 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] studied the rank-width
of G(n,1/2), though I believe that the first version of his paper on
arxiv1 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 graph2.
This software is now included in the open source mathematics software
package called SAGE; see the
manual3.

Apparently Friedmanský wrote Master's thesis on "implementation of
optimization of a graph algorithm for computing rank-width"4 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:

1http://arxiv.org/pdf/0908.1772v1.pdf

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.