Dynamic survey on rankwidth and related width parameters of graphs
Sangil Oum
Aug 19, 2013
This is an incomplete ongoing survey on rankwidth 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
Rankwidth was introduced by Oum and Seymour [35].
Cliquewidth is defined and investigated first by Courcelle and Olariu [5] published in 2000, but the operations for cliquewidth has been introduced by Courcelle, Engelfriet, and Rozenberg [4] in 1993.
NLCwidth was introduced by Wanke [40] in 1994.
Booleanwidth was introduced by BuiXuan, Telle, and Vatshelle [2].
2 Wellquasiordering
Oum [31] proved that graphs of bounded rankwidth are wellquasiordered under taking pivotminors.
This result has been generalized to
 skewsymmetric or symmetric matrices over a fixed finite field
by Oum [34],  σsymmetric matrices over a fixed finite field by Kante [20].
3 Forbidden vertexminors
Oum [29] showed that if a graph has rankwidth k, then so is its vertexminor.
This, together with the wellquasiordering theorem [31] implies that
for each k, there exists a list of finitely many graphs such that a graph has rankwidth at most k if and only if none of its vertexminors is isomorphic to a graph in the list.
Oum [29] showed that for each k, the forbidden vertexminor for rankwidth 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 vertexminors
for graphs of linear rankwidth at most k,
as there are no analogous upper bound on the size of forbidden vertexminors. Jeong, Kwon, and Oum [16]
showed that there are at least 3^{Ω(3k)} forbidden vertexminors for linear rankwidth at most k.
4 Hardness
Computing rankwidth is NPhard. It can be easily deduced by combining the following known facts. This reduction is mentioned in [30].
 Seymour and Thomas [37] proved that computing branchwidth is NPhard.
Kloks, Kratochvíl, and Müller [21] even showed that it is NPhard to compute branchwidth of interval graphs.  Hicks and McMurray Jr. [13] and independently Mazoit and Thomassé [26] showed that if a graph G is not a forest, then the branchwidth of the cycle matroid M(G) is equal to the branchwidth of G.
 Oum [29] showed that the branchwidth of a binary matroid is equal to the rankwidth of its fundamental graph. Every graphic matroid is binary.
It is not known to me whether computing linear rankwidth is NPhard.
Computing cliquewidth is NPhard, shown by Fellows, Rosamond, Rotics, and Szeider [8].
Computing the relative cliquewidth is also NPcomplete, shown by Müller and Urner [27]. The relative cliquewidth [24] is a cliquewidth restricted to a fixed decomposition tree.
Gurski and Wanke [12] proved that computing NLCwidth is
also NPhard via a reduction from the treewidth.
5 Finding an approximate rankdecomposition for a fixed k
Oum and Seymour [35] provided an algorithm to
find a rankdecomposition of width at most 3k+1 or confirm that the input graph has rankwidth bigger than k
in time O(8^{k} n^{9} 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^{4}).
This allows us to find a rankdecomposition of width at most c′ times rankwidth
if the rankwidth 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 measurementbased quantum computation.
If we do not mind having bigger function in k, then in the same paper [30], it is possible to find a rankdecomposition of width 3k−1 or
confirm that the rankwidth is bigger than k in time O(f(k)n^{3}).
We do not know whether there is an algorithm to find an approximate rankdecomposition of width O(k) in time O(c_{1}^{k} n^{c}) for c ≤ 3
when an input graph has rankwidth at most k.
These algorithms can be used as a tool to construct an expression for cliquewidth decomposition, which are essential in many algorithmic applications.
6 Deciding rankwidth at most k for fixed k
There is a general algorithm of Oum and Seymour [36] which can construct a branchdecomposition of any symmetric submodular function in time O(n^{8k+c}), and if we apply it to rankwidth, we get an algorithm of running time O(n^{8k+12}logn).
Note that a simple general algorithm for pathwidth of any symmetric submodular function
was developed by Nagamochi [28], which is applicable to linear rankwidth in time O(n^{2k+4}).
Courcelle and Oum [6] first constructed an algorithm to decide, for fixed k, whether rankwidth is at most k in time O(f(k)n^{3}). But their algorithm uses the monadic secondorder logic formula and does not provide an explicit rankdecomposition even if it exists.
This problem was solved later.
Hlinený and Oum [14] constructed an algorithm to decide whether rankwidth is at most k
and find a rankdecomposition of width at most k, if it exists, in time O(f(k)n^{3}).
Here, f(k) is growing very fast with k, because the algorithm uses the monadic secondorder logic as well as the list of forbidden minors for branchwidth 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 branchwidth at most k have at most (6^{k}−1)/5 elements. This implies that we can construct an explicit algorithm for testing rankwidth at most k and constructing a rankdecomposition 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 rankwidth is at most k in time O(n^{3}) by using the wellquasiordering theorem [31] and monadic secondorder logic formula to test vertexminors [6]. But it is not known how to find the list of forbidden vertexminors.
Wahlström [39] showed that deciding whether cliquewidth is at most k and finding a kexpression can be done in time O^{*}((2k+1)^{n}).
Espelage, Gurski, and Wanke [7] constructed an algorithm to decide whether a graph has cliquewidth at most k for graphs of bounded treewidth.
7 Relation to Treewidth
Kante [19] showed that rankwidth is at most 4k+2 if the treewidth is k.
Later,
Oum [32] showed that rankwidth is at most k+1 if treewidth is k.
In fact, it is shown that
if G has branchwidth k,
then the incidence graph of G has rankwidth k or k−1,
unless k=0.
Corneil and Rotics [3] showed that the cliquewidth is at most 3·2^{k−1} if the treewidth is k.
Moreover, they proved that for each k, there is a graph G having treewidth k and cliquewidth at least 2^{k/2−1}.
This also implies that there are graphs having rankwidth at most k+1 and cliquewidth at least 2^{k/2−1} for each k.
Kwon and Oum [22] proved that every graph of rankwidth k
is a pivotminor of a graph of treewidth at most 2k.
They also proved that every graph of linear rankwidth k is a pivotminor of a graph of pathwidth k+1.
In other words,
a set I of graphs has bounded rankwidth
if and only if it is a set of pivotminors of graphs of bounded treewidth.
Fomin, Oum, and Thilikos [10] showed that when graphs are planar, or Hminorfree, then
having bounded treewidth is equivalent to having bounded rankwidth.
For instance, if a graph G is planar and has rankwidth k,
then treewidth is at most 72k−2.
If G of rankwidth k
has no K_{r} minor with r > 2, then treewidth 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 rankwidth or related width parameters.
Width Parameter  Running time  Paper 
Rankwidth  O^{*}(2^{n})  Oum [33] 
Linear rankwidth  O^{*}(2^{n})  forklore (trivial) 
The running time to compute cliquewidth exactly seems open.
Müller and Urner [27] proved that NLCwidth can be computed in time O(3^{n} n) for an nvertex graph.
When they gave a talk at GROW2007 about this result, they further claimed that cliquewidth can be computed in time O^{*}(3^{n}) by finding a polynomialtime algorithm to compute relative cliquewidth [24] but later Ruth Urner emailed me that there was a mistake.
Branchwidth 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ösRényi random graph G(n,p) has rankwidth n/3−O(1) if p is a constant between 0 and 1.
Furthermore, [1/(n)] << p ≤ [1/2], then the rankwidth is [(n)/3]−o(n),
and if p = c/n and c > 1, then rankwidth is at least r n for some r = r(c).
Since the cliquewidth is at least rankwidth, this also gives a lower bound for cliquewidth.
Adler, BuiXuan, Rabinovich, Renault, Telle, and Vatshelle [1] claimed that booleanwidth of G(n,p) for fixed 0 < p < 1 is Θ(log^{2} n) asymptotically almost surely.
Johansson [17] (also in his Ph.D. thesis
[18]) claimed in a conference paper that NLCwidth
and cliquewidth 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 rankwidth
of G(n,1/2), though I believe that the first version of his paper on
arxiv^{1} is
incorrect; Later versions have different proofs.
10 Explicit graphs
Jelínek [15] proved that an n×n grid has rankwidth n−1.
11 Software
Philipp Klau Krause implemented a simple dynamic programming algorithm
to compute the rankwidth of a graph^{2}.
This software is now included in the open source mathematics software
package called SAGE; see the
manual^{3}.
Apparently Friedmanský wrote Master's thesis on "implementation of
optimization of a graph algorithm for computing rankwidth"^{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, BinhMinh BuiXuan, Yuri Rabinovich, Gabriel Renault, Jan Arne
Telle, and Martin Vatshelle.
On the Booleanwidth of a graph: structure and applications.
In Graphtheoretic concepts in computer science, volume 6410 of
Lecture Notes in Comput. Sci., pages 159170. Springer, Berlin, 2010.
doi:10.1007/9783642169267_16.  [2]

BinhMinh BuiXuan, Jan Arne Telle, and Martin Vatshelle.
Booleanwidth of graphs.
Theoret. Comput. Sci., 412(39):51875204, 2011.
doi:10.1016/j.tcs.2011.05.022.  [3]

Derek G. Corneil and Udi Rotics.
On the relationship between cliquewidth and treewidth.
SIAM J. Comput., 34(4):825847 (electronic), 2005.
doi:10.1137/S0097539701385351.  [4]

Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.
Handlerewriting hypergraph grammars.
J. Comput. System Sci., 46(2):218270, 1993.
doi:10.1016/00220000(93)90004G.  [5]

Bruno Courcelle and Stephan Olariu.
Upper bounds to the clique width of graphs.
Discrete Appl. Math., 101(13):77114, 2000.
doi:10.1016/S0166218X(99)001845.  [6]

Bruno Courcelle and Sangil Oum.
Vertexminors, monadic secondorder logic, and a conjecture by
Seese.
J. Combin. Theory Ser. B, 97(1):91126, 2007.
doi:10.1016/j.jctb.2006.04.003.  [7]

Wolfgang Espelage, Frank Gurski, and Egon Wanke.
Deciding cliquewidth for graphs of bounded treewidth.
Journal of Graph Algorithms and Applications, 7(2):141180,
2003.  [8]

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider.
Cliquewidth is NPcomplete.
SIAM J. Discrete Math., 23(2):909939, 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):27262736, 2009.
doi:10.1016/j.dam.2008.08.009.  [10]

Fedor V. Fomin, Sangil Oum, and Dimitrios M. Thilikos.
Rankwidth and treewidth of Hminorfree graphs.
European J. Combin., 31(7):16171628, 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 branchwidth k.
J. Combin. Theory Ser. B, 88(2):261265, 2003.  [12]

Frank Gurski and Egon Wanke.
Line graphs of bounded cliquewidth.
Discrete Math., 307(22):27342754, 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):681692, 2007.
doi:10.1016/j.jctb.2006.12.007.  [14]

Petr Hlinený and Sangil Oum.
Finding branchdecompositions and rankdecompositions.
SIAM J. Comput., 38(3):10121032, 2008.
doi:10.1137/070685920.  [15]

Vít Jelínek.
The rankwidth of the square grid.
Discrete Appl. Math., 158(7):841850, 2010.
doi:10.1016/j.dam.2009.02.007.  [16]

Jisu Jeong, Ojoung Kwon, and Sangil Oum.
Excluded vertexminors for graphs of linear rankwidth 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
221232, Kiel, Germany, 2013. Schloss Dagstuhl. LeibnizZent. Inform.
URL: http://drops.dagstuhl.de/opus/volltexte/2013/3936, doi:10.4230/LIPIcs.STACS.2013.221.  [17]

Öjvind Johansson.
Cliquedecomposition, NLCdecomposition, and modular
decompositionrelationships and results for random graphs.
In Proceedings of the Twentyninth Southeastern International
Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL,
1998), volume 132, pages 3960, 1998.  [18]

Öjvind Johansson.
Graph decomposition using node labels.
PhD thesis, Royal Institute of Technology, 2001.  [19]

Mamadou Moustapha Kanté.
Vertexminor reductions can simulate edge contractions.
Discrete Appl. Math., 155(17):23282340, 2007.
doi:10.1016/j.dam.2007.06.011.  [20]

Mamadou Moustapha Kanté.
Wellquasiordering of matrices under Schur complement and
applications to directed graphs.
European J. Combin., 33(8):18201841, 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):266275, 2005.
doi:10.1016/j.dam.2004.01.015.  [22]

Ojoung Kwon and Sangil Oum.
Graphs of small rankwidth are pivotminors of graphs of small
treewidth.
Discrete Appl. Math., 2013.
doi:10.1016/j.dam.2013.01.007.  [23]

Choongbum Lee, Joonkyung Lee, and Sangil Oum.
Rankwidth of random graphs.
J. Graph Theory, 70(3):339347, July/August 2012.
doi:10.1002/jgt.20620.  [24]

Vadim Lozin and Dieter Rautenbach.
The relative cliquewidth of a graph.
J. Combin. Theory Ser. B, 97(5):846858, 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 275286. Cambridge Univ. Press, Cambridge, 2007.  [27]

Haiko Müller and Ruth Urner.
On a disparity between relative cliquewidth and relative NLCwidth.
Discrete Appl. Math., 158(7):828840, 2010.
doi:10.1016/j.dam.2009.06.024.  [28]

Hiroshi Nagamochi.
Linear layouts in submodular systems.
In KunMao Chao, Tsansheng Hsu, and DerTsai Lee, editors,
ISAAC '12, volume 7676 of Lecture Notes in Comput. Sci., pages
475484. Springer Berlin Heidelberg, 2012.
doi:10.1007/9783642352614_50.  [29]

Sangil Oum.
Rankwidth and vertexminors.
J. Combin. Theory Ser. B, 95(1):79100, 2005.
doi:10.1016/j.jctb.2005.03.003.  [30]

Sangil Oum.
Approximating rankwidth and cliquewidth quickly.
ACM Trans. Algorithms, 5(1):Art. 10, 20, 2008.
doi:10.1145/ 1435375.1435385.  [31]

Sangil Oum.
Rankwidth and wellquasiordering.
SIAM J. Discrete Math., 22(2):666682, 2008.
doi:10.1137/050629616.  [32]

Sangil Oum.
Rankwidth is less than or equal to branchwidth.
J. Graph Theory, 57(3):239244, 2008.
doi:10.1002/jgt.20280.  [33]

Sangil Oum.
Computing rankwidth exactly.
Inform. Process. Lett., 109(13):745748, 2009.
doi:10.1016/j.ipl.2009.03.018.  [34]

Sangil Oum.
Rankwidth and wellquasiordering of skewsymmetric or symmetric
matrices.
Linear Algebra Appl., 436(7):20082036, 2012.
doi:10.1016/j.laa.2011.09.027.  [35]

Sangil Oum and Paul Seymour.
Approximating cliquewidth and branchwidth.
J. Combin. Theory Ser. B, 96(4):514528, 2006.
doi:10.1016/j.jctb.2005.10.006.  [36]

Sangil Oum and Paul Seymour.
Testing branchwidth.
J. Combin. Theory Ser. B, 97(3):385393, 2007.
doi:10.1016/j.jctb.2006.06.006.  [37]

Paul Seymour and Robin Thomas.
Call routing and the ratcatcher.
Combinatorica, 14(2):217241, 1994.
doi:10.1007/BF01215352.  [38]

M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel.
Classical simulation versus universality in measurementbased quantum
computation.
Phys. Rev. A, 75:012337, Jan 2007.
doi:10.1103/PhysRevA.75.012337.  [39]

Magnus Wahlström.
New plainexponential time classes for graph homomorphism.
Theory Comput. Syst., 49(2):273282, 2011.
doi:10.1007/s002240109261z.  [40]

Egon Wanke.
kNLC graphs and polynomial algorithms.
Discrete Appl. Math., 54(23):251266, 1994.
doi:10.1016/0166218X(94)900264.
Footnotes:
^{1}http://arxiv.org/pdf/0908.1772v1.pdf
^{2}http://pholia.tdi.informatik.unifrankfurt.de/~philipp/software/rw.shtml
^{3}http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_decompositions/rankwidth.html