The Rank-Width of Directed Graphs
Mamadou Moustapha Kanté, Rao, Michael · arXiv (Cornell University) · 2007
Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs which has good algorithmic and structural properties. We compare two possible definitions of the rank-width of directed graphsn named bi-rank-width and GF(4)-rank-width. They turn out to be equivalent. We propose algebraic graph operations that handle both efficiently, similar to the one that we have given for the rank-width of undirected graphs. We give approximation recognition algorithms for the two parameters, and then, a polynomial time approximation algorithm for the clique-width of directed graphs. We also define a notion of vertex-minor for GF(4)-rank-width and prove that for fixed k there is a finite list C_k of directed graphs such that a directed graph has GF(4)-rank-width at most k if and only if it has no vertex-minor isomorphic to a directed graph in C_k.