Dynamic survey on rank-width and related width parameters of graphs
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.
Rank-width was introduced by Oum and Seymour .
Clique-width is defined and investigated first by Courcelle and Olariu  published in 2000, but the operations for clique-width has been introduced by Courcelle, Engelfriet, and Rozenberg  in 1993.
NLC-width was introduced by Wanke  in 1994.
Boolean-width was introduced by Bui-Xuan, Telle, and Vatshelle .
Oum  proved that graphs of bounded rank-width are well-quasi-ordered under taking pivot-minors.
This result has been generalized to
- skew-symmetric or symmetric matrices over a fixed finite field
by Oum ,
- σ-symmetric matrices over a fixed finite field by Kante .
3 Forbidden vertex-minors
Oum  showed that if a graph has rank-width k, then so is its vertex-minor.
This, together with the well-quasi-ordering theorem  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  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 
showed that there are at least 3Ω(3k) forbidden vertex-minors for linear rank-width at most k.
Computing rank-width is NP-hard. It can be easily deduced by combining the following known facts. This reduction is mentioned in .
- Seymour and Thomas  proved that computing branch-width is NP-hard.
Kloks, Kratochvíl, and Müller  even showed that it is NP-hard to compute branch-width of interval graphs.
- Hicks and McMurray Jr.  and independently Mazoit and Thomassé  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.
- Oum  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 .
Gurski and Wanke  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  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 
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 ) for their study on measurement-based quantum computation.
If we do not mind having bigger function in k, then in the same paper , 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  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 , which is applicable to linear rank-width in time O(n2k+4).
Courcelle and Oum  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  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  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  and monadic second-order logic formula to test vertex-minors . But it is not known how to find the list of forbidden vertex-minors.
Wahlström  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  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
if G has branch-width k,
then the incidence graph of G has rank-width k or k−1,
Corneil and Rotics  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  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  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  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|
|Linear rank-width||O*(2n)||forklore (trivial)|
The running time to compute clique-width exactly seems open.
Müller and Urner  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  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 Random graphs
Lee, Lee, and Oum  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  claimed that boolean-width of G(n,p) for fixed 0 < p < 1 is Θ(log2 n) asymptotically almost surely.
Johansson  (also in his Ph.D. thesis
) 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.
10 Explicit graphs
Jelínek  proved that an n×n grid has rank-width n−1.
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
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.
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.
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.
Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle.
Boolean-width of graphs.
Theoret. Comput. Sci., 412(39):5187-5204, 2011.
Derek G. Corneil and Udi Rotics.
On the relationship between clique-width and treewidth.
SIAM J. Comput., 34(4):825-847 (electronic), 2005.
Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.
Handle-rewriting hypergraph grammars.
J. Comput. System Sci., 46(2):218-270, 1993.
Bruno Courcelle and Stephan Olariu.
Upper bounds to the clique width of graphs.
Discrete Appl. Math., 101(1-3):77-114, 2000.
Bruno Courcelle and Sang-il Oum.
Vertex-minors, monadic second-order logic, and a conjecture by
J. Combin. Theory Ser. B, 97(1):91-126, 2007.
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,
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.
Fedor Fomin, Frédéric Mazoit, and Ioan Todinca.
Computing branchwidth via efficient triangulations and blocks.
Discrete Appl. Math., 157(12):2726-2736, 2009.
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.
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.
Frank Gurski and Egon Wanke.
Line graphs of bounded clique-width.
Discrete Math., 307(22):2734-2754, 2007.
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.
Petr Hlinený and Sang-il Oum.
Finding branch-decompositions and rank-decompositions.
SIAM J. Comput., 38(3):1012-1032, 2008.
The rank-width of the square grid.
Discrete Appl. Math., 158(7):841-850, 2010.
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.
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.
Graph decomposition using node labels.
PhD thesis, Royal Institute of Technology, 2001.
Mamadou Moustapha Kanté.
Vertex-minor reductions can simulate edge contractions.
Discrete Appl. Math., 155(17):2328-2340, 2007.
Mamadou Moustapha Kanté.
Well-quasi-ordering of matrices under Schur complement and
applications to directed graphs.
European J. Combin., 33(8):1820-1841, 2012.
Ton Kloks, Jan Kratochvíl, and Haiko Müller.
Computing the branchwidth of interval graphs.
Discrete Appl. Math., 145(2):266-275, 2005.
O-joung Kwon and Sang-il Oum.
Graphs of small rank-width are pivot-minors of graphs of small
Discrete Appl. Math., 2013.
Choongbum Lee, Joonkyung Lee, and Sang-il Oum.
Rank-width of random graphs.
J. Graph Theory, 70(3):339-347, July/August 2012.
Vadim Lozin and Dieter Rautenbach.
The relative clique-width of a graph.
J. Combin. Theory Ser. B, 97(5):846-858, 2007.
Some probabilistic results on width measures of graphs.
Unpublished, 08 2009.
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.
Haiko Müller and Ruth Urner.
On a disparity between relative cliquewidth and relative NLC-width.
Discrete Appl. Math., 158(7):828-840, 2010.
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.
Rank-width and vertex-minors.
J. Combin. Theory Ser. B, 95(1):79-100, 2005.
Approximating rank-width and clique-width quickly.
ACM Trans. Algorithms, 5(1):Art. 10, 20, 2008.
Rank-width and well-quasi-ordering.
SIAM J. Discrete Math., 22(2):666-682, 2008.
Rank-width is less than or equal to branch-width.
J. Graph Theory, 57(3):239-244, 2008.
Computing rank-width exactly.
Inform. Process. Lett., 109(13):745-748, 2009.
Rank-width and well-quasi-ordering of skew-symmetric or symmetric
Linear Algebra Appl., 436(7):2008-2036, 2012.
Sang-il Oum and Paul Seymour.
Approximating clique-width and branch-width.
J. Combin. Theory Ser. B, 96(4):514-528, 2006.
Sang-il Oum and Paul Seymour.
J. Combin. Theory Ser. B, 97(3):385-393, 2007.
Paul Seymour and Robin Thomas.
Call routing and the ratcatcher.
Combinatorica, 14(2):217-241, 1994.
M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel.
Classical simulation versus universality in measurement-based quantum
Phys. Rev. A, 75:012337, Jan 2007.
New plain-exponential time classes for graph homomorphism.
Theory Comput. Syst., 49(2):273-282, 2011.
k-NLC graphs and polynomial algorithms.
Discrete Appl. Math., 54(2-3):251-266, 1994.