Cycle rank

In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. When applied to undirected graphs, the concept of cycle rank bears many different names in the research literature, including vertex ranking number, ordered chromatic number, minimum elimination tree height and tree-depth (Bodlaender et al. 1998, Rossman 2008)

Besides its original application in the studying the star height of formal languages, the measure has found use in sparse matrix computations (see Bodlaender et al. 1995) and logic (Rossman 2008).

Definition

The cycle rank r(G) of a digraph G = (V, E) is inductively defined as follows:

• If G is acyclic, then r(G) = 0.
• If G is strongly connected and E is nonempty, then

$r(G) = 1 + \min_{v\in V} r(G-v).\,$

• If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G.

History

In the special case of undirected graphs, the cycle rank was rediscovered about twenty years later in the context of sparse matrix computations (Schreiber 1982). Apparently being unaware of the original definition from the 1960s, later authors generalized the concept once again to digraphs (Eisenstat & Liu 2005).

Bounds

Any n-vertex forest has cycle rank O(log n). For, in a forest, one can always find a constant number of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most 2n/3 vertices each. By recursively partitioning each of these two subforests, we can easily derive a logarithmic upper bound on the cycle rank. The same technique, applied to a tree decomposition of a graph, shows that, if the treewidth of an n-vertex graph G is t, then the pathwidth of G is O(t log n), see (Bodlaender et al. 1995). Since outerplanar graphs, series-parallel graphs, and Halin graphs all have bounded treewidth, they all also have at most logarithmic cycle rank.

Cycle rank formulas for some digraphs

As mentioned in the introduction, the cycle rank of a directed acyclic graph is 0, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. Apart from these, the cycle rank of a few other digraphs is known: the undirected path P_n of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank $\lfloor \log n\rfloor$ (McNaughton 1969). For the directed $(m\times n)$-torus T_m,n, i.e., the cartesian product of two directed circuits of lengths m and n, we have r(T_n,n) = n and r(T_m,n) = min{m,n} + 1 for m ≠ n (Eggan 1963, Gruber & Holzer 2008).

Computing the cycle rank

Computing the cycle rank is computationally hard: already in the case of undirected graphs, the corresponding decision problem is NP-complete (Pothen 1988). The same holds true in the case of digraphs (Gruber 2008). For undirected graphs, problem remains NP-complete for cobipartite graphs (Pothen 1988), that is, complements of bipartite graphs, for bipartite graphs (Bodlaender et al. 1998), as well as for chordal graphs (Dereniowski & Nadolski 2006). On the positive side, the problem is solvable in polynomial time on interval graphs (Aspvall & Heggernes 1994), as well as on permutation, trapezoid, circular-arc, circular permutation graphs, and cocomparability graphs of bounded dimension (Deogun et al. 1999). For undirected trees, the problem is even solvable in linear time (Iyer, Ratliff & Vijayan 1988, Schäffer 1989). Concerning the approximation complexity of the problem, Bodlaender et al. (1995) give an O((log n)²)-approximation algorithm for the undirected case.

Applications

Star height of regular languages

The very first application of cycle rank was in formal language theory, for studying the star height of regular languages. Eggan (1963) established a relation between the theories of regular expressions, finite automata, and of directed graphs. In subsequent years, this relation became known as Eggan's theorem, cf. Sakarovitch (2009). In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a set of labeled edges δ, referred to as transition relation: Q × (Σ ∪{ε}) × Q. Here ε denotes the empty word.
• an initial state q₀ ∈ Q
• a set of states F distinguished as accepting states F ⊆ Q.

A word w ∈ Σ^* is accepted by the ε-NFA if there exists a directed path from the initial state q₀ to some final state in F using edges from δ, such that the concatenation of all labels visited along the path yields the word w. The set of all words over Σ^* accepted by the automaton is the language accepted by the automaton A.

When speaking of digraph properties of a nondeterministic finite automaton A with state set Q, we naturally address the digraph with vertex set Q induced by its transition relation. Now the theorem is stated as follows.

Eggan's Theorem: The star height of a regular language L equals the minimum cycle rank among all nondeterministic finite automata with ε-moves accepting L.

Proofs of this theorem are given by Eggan (1963), and more recently by Sakarovitch (2009).

Cholesky factorization in sparse matrix computations

Another application of this concept lies in sparse matrix computations, namely for computing the Cholesky factorization of a (symmetric) matrix in parallel. A given sparse $(n\times n)$-matrix M may be interpreted as the adjacency matrix of some symmetric digraph G on n vertices, in a way such that the non-zero entries of the matrix are in one-to-one correspondence with the edges of G. If the cycle rank of the digraph G is at most k, then the Cholesky factorization of M can be computed in at most k steps on a parallel computer with n processors (Dereniowski & Kubale 2003).

See also

• Graph coloring
• Star height
• Nested dissection

References

• Aspvall, Bengt; Heggernes, Pinar (1994), "Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time", BIT 34 (4): 484–509, doi:10.1007/BF01934264 .
• Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt (1998), "Rankings of graphs", SIAM Journal on Discrete Mathematics 11 (1): 168–181, doi:10.1137/S0895480195282550, http://www.cs.uu.nl/pub/RUU/CS/techreps/CS-1995/1995-03.pdf .
• Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms 18 (2): 238–255, doi:10.1006/jagm.1995.1009, ftp://ftp.parc.xerox.com/pub/gilbert/csl9010.ps.Z .
• Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko (1999). "On the vertex ranking problem for trapezoid, circular-arc and other graphs". Discrete Applied Mathematics 98: 39–34. doi:10.1016/S0166-218X(99)00179-1.  edit.
• Dereniowski, Dariusz; Kubale, Marek (2004), "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs", 5th International Conference on Parallel Processing and Applied Mathematics, Lecture Notes on Computer Science, 3019, Springer-Verlag, pp. 985–992, doi:10.1007/978-3-540-24669-5_127, http://www.eti.pg.gda.pl/katedry/kams/wwwkams/pdf/Cholesky_fmprg.pdf .
• Eggan, Lawrence C. (1963), "Transition graphs and the star-height of regular events", Michigan Mathematical Journal 10 (4): 385–397, doi:10.1307/mmj/1028998975 .
• Dereniowski, D.; Nadolski, A. (2006). "Vertex rankings of chordal graphs and weighted trees". Information Processing Letters 98: 96. doi:10.1016/j.ipl.2005.12.006.  edit
• Eisenstat, Stanley C.; Liu, Joseph W. H. (2005), "The theory of elimination trees for sparse unsymmetric matrices", SIAM Journal on Matrix Analysis and Applications 26 (3): 686–705, doi:10.1137/S089547980240563X .
• Gruber, Hermann (2008), "Digraph Complexity Measures and Applications in Formal Language Theory", 4th Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS), pp. 60–67 .
• Gruber, Hermann; Holzer, Markus (2008), "Finite automata, digraph connectivity, and regular expression size", Proc. 35th International Colloquium on Automata, Languages and Programming, Lecture Notes on Computer Science, 5126, Springer-Verlag, pp. 39–50, doi:10.1007/978-3-540-70583-3_4, http://www.hermann-gruber.com/data/icalp08.pdf .
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988). "Optimal node ranking of trees". Information Processing Letters 28: 225–201. doi:10.1016/0020-0190(88)90194-9.  edit
• Kubale, Marek, Graph Colorings, Contemporary Mathematics, 352, Oxford University Press, ISBN 978-0821834589 .
• McNaughton, Robert (1969), "The loop complexity of regular events", Information Sciences 1 (3): 305–328, doi:10.1016/S0020-0255(69)80016-2 .
• Pothen, Alex (1988). The complexity of optimal elimination trees (Technical report). Pennsylvania State University, USA. CS-88-13. 
• Rossman, Benjamin (2008), "Homomorphism preservation theorems", Journal of the ACM 55 (3): Article 15, doi:10.1145/1379759.1379763 .
• Sakarovitch, Jacques (2009), Elements of Automata Theory, Cambridge University Press, ISBN 0521844258 
• Schäffer, Alejandro A. (1989). "Optimal node ranking of trees in linear time". Information Processing Letters 33: 91–19. doi:10.1016/0020-0190(89)90161-0.  edit
• Schreiber, Robert (1982), "A new implementation of sparse Gaussian elimination", ACM Transactions on Mathematical Software 8 (3): 256–276, doi:10.1145/356004.356006, http://www.hpl.hp.com/personal/Robert_Schreiber/papers/1982%20Sparse%20Gaussian%20Elimination/p256-schreiber%5B1%5D.pdf .