Parameter: rankwidth

Definition:

Let $M$ be the $|V| \times |V|$ adjacency matrix of a graph $G$. The cut rank of a set $A \subseteq V(G)$ is the rank of the submatrix of $M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$. A rank decomposition of a graph $G$ is a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. Any edge $e$ in the tree $T$ splits $V(G)$ into two parts $A_e, B_e$ corresponding to the leaves of the two connected components of $T - e$. The width of an edge $e \in E(T)$ is the cutrank of $A_e$. The width of the rank-decomposition $(T,L)$ is the maximum width of an edge in $T$. The rankwidth of the graph $G$ is the minimum width of a rank-decomposition of $G$.

References

[1723]
Sang-il Oum, P. Seymour
Approximating clique-width and branch-width
Journal of Combinatorial Theory, Series B 96 No.4, 514-528 (2006)

Equivalent parameters

Only references for direct inclusions are given. Where no reference is given for an equivalent parameter, check other equivalent parameters.

Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

Minimal upper bounds for this parameter

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability
[?]
Input: A graph G in this class.
Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.
FPT
FPT from FPT-Linear on cliquewidth
Clique
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.
FPT
FPT on cliquewidth
Clique cover
[?]
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.
XP
XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)

Colourability
[?]
Input: A graph G in this class and an integer k.
Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.
FPT
FPT on cliquewidth
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT
FPT from FPT-Linear on cliquewidth
FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
FPT
FPT on cliquewidth
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
XP
XP
[1763]
M. Grohe, P. Schweitzer
Isomorphism Testing for Graphs of Bounded Rank Width
Proc. of 55th Annual IEEE Symposium on Foundations of Computer Science FOCS (2015)

Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
XP
XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
XP
XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

XP
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Independent set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.
FPT
FPT on cliquewidth
[1716]
F. Gurski
A comparison of two approaches for polynomial time algorithms computing basic graph parameters
Manuscript 2008

Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
XP,W-hard
XP on cliquewidth
[1735]
E. Wanke
k-NLC graphs and polynomial algorithsm
Discrete Appl. Math. 54 No.2 251-266 (1994)

W-hard on cliquewidth
[1736]
F.V. Fomin, P.A. Golovach, D. Lokshtanov, S. Saurabh
Almost optimal lower bounds for problems parametrized by clique-width
SIAM J. Comput. 43 No.5 1541-1563 (2014)

Monopolarity
[?]
Input: A graph G in this class.
Output: True iff G is monopolar.
Unknown to ISGCI
Polarity
[?]
Input: A graph G in this class.
Output: True iff G is polar.
XP
XP on cliquewidth
[1764]
V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

Weighted clique
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT
FPT on cliquewidth
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
FPT
FPT from FPT-Linear on cliquewidth
FPT
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Weighted independent dominating set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT
FPT from FPT-Linear on cliquewidth
Weighted independent set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT
FPT from FPT-Linear on cliquewidth
FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Graph classes

Bounded

back to top

Unbounded

back to top

Open

back to top

Unknown to ISGCI

back to top

AltStyle によって変換されたページ (->オリジナル) /