Tag: rank-width

  • Dynamic survey on rank-width

    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 (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:

     

    1https://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