cycle rank

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

• If G is acyclic, then {{math|1=r(G) = 0}}.
• If G is strongly connected and E is nonempty, then

::$r(G)\; =\; 1\; +\; \backslash min\_\{v\backslash in\; V\}\; r(G-v),\backslash ,$ where {{tmath|G - v}} is the digraph resulting from deletion of vertex {{mvar|v}} and all edges beginning or ending at {{mvar|v}}.

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

The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components.

Cycle rank was introduced by {{harvtxt|Eggan|1963}} in the context of star height of regular languages. It was rediscovered by {{harv|Eisenstat|Liu|2005}} as a generalization of undirected tree-depth, which had been developed beginning in the 1980s

and applied to sparse matrix computations {{harv|Schreiber|1982}}.

The cycle rank of a DAG 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 $\backslash lfloor\; \backslash log\; n\backslash rfloor$ {{harv|McNaughton|1969}}. For the directed $(m\backslash 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\})\; =\; \backslash min\backslash \{m,n\backslash \}\; +\; 1$ for m ≠ n ({{harvnb|Eggan|1963}}, {{harvnb|Gruber|Holzer|2008}}).

Computing the cycle rank is computationally hard: {{harvtxt|Gruber|2012}} proves that the corresponding decision problem is NP-complete, even for sparse digraphs of maximum outdegree at most 2. On the positive side, the problem is solvable in time $O(1.9129^n)$ on digraphs of maximum outdegree at most 2, and in time $O^*(2^n)$ on general digraphs. There is an approximation algorithm with approximation ratio $O((\backslash log\; n)^\backslash frac32)$.

The first application of cycle rank was in formal language theory, for studying the star height of regular languages. {{harvtxt|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. {{harvtxt|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 {{harvtxt|Eggan|1963}}, and more recently by {{harvtxt|Sakarovitch|2009}}.

Another application of this concept lies in sparse matrix computations, namely for using nested dissection to compute the Cholesky factorization of a (symmetric) matrix in parallel. A given sparse $(n\backslash 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 {{harv|Dereniowski|Kubale|2004}}.

• Circuit rank

{{refbegin}}

• {{citation

| last1 = Bodlaender

| first1 = Hans L.

| author1-link = Hans L. Bodlaender

| last2 = Gilbert

| first2 = John R.

| last3 = Hafsteinsson

| first3 = Hjálmtýr

| last4 = Kloks

| first4 = Ton

| doi = 10.1006/jagm.1995.1009

| zbl = 0818.68118

| issue = 2

| journal = Journal of Algorithms

| pages = 238–255

| title = Approximating treewidth, pathwidth, frontsize, and shortest elimination tree

| volume = 18

| year = 1995

}}.

• {{citation

| last1 = Dereniowski

| first1 = Dariusz

| last2 = Kubale

| first2 = Marek

| contribution = Cholesky Factorization of Matrices in Parallel and Ranking of Graphs

| doi = 10.1007/978-3-540-24669-5_127

| zbl = 1128.68544

| pages = 985–992

| publisher = Springer-Verlag

| series = Lecture Notes on Computer Science

| title = 5th International Conference on Parallel Processing and Applied Mathematics

| url = http://www.eti.pg.gda.pl/katedry/kams/wwwkams/pdf/Cholesky_fmprg.pdf

| volume = 3019

| year = 2004

| isbn = 978-3-540-21946-0

| url-status = dead

| archiveurl = https://web.archive.org/web/20110716060800/http://www.eti.pg.gda.pl/katedry/kams/wwwkams/pdf/Cholesky_fmprg.pdf

| archivedate = 2011-07-16

}}.

• {{citation

| last = Eggan | first = Lawrence C.

| doi = 10.1307/mmj/1028998975 | zbl=0173.01504

| issue = 4

| journal = Michigan Mathematical Journal

| pages = 385–397

| title = Transition graphs and the star-height of regular events

| volume = 10

| year = 1963| doi-access = free

}}.

• {{citation

| last1 = Eisenstat | first1 = Stanley C.

| last2 = Liu | first2 = Joseph W. H.

| doi = 10.1137/S089547980240563X

| issue = 3

| journal = SIAM Journal on Matrix Analysis and Applications

| pages = 686–705

| title = The theory of elimination trees for sparse unsymmetric matrices

| volume = 26

| year = 2005}}.

• {{citation

| last1 = Gruber | first1 = Hermann

| title = Digraph Complexity Measures and Applications in Formal Language Theory

| pages = 189–204

| journal = Discrete Mathematics & Theoretical Computer Science

| volume = 14

| number = 2

| year = 2012

| url = http://www.hermann-gruber.com/data/dmtcs12-revised.pdf

}}.

• {{citation

| last1 = Gruber | first1 = Hermann

| last2 = Holzer | first2 = Markus

| contribution = Finite automata, digraph connectivity, and regular expression size

| doi = 10.1007/978-3-540-70583-3_4

| pages = 39–50

| publisher = Springer-Verlag

| series = Lecture Notes on Computer Science

| title = Proc. 35th International Colloquium on Automata, Languages and Programming

| contribution-url = http://www.hermann-gruber.com/data/icalp08.pdf

| volume = 5126

| year = 2008| isbn = 978-3-540-70582-6

}}.

• {{citation

| doi = 10.1016/S0020-0255(69)80016-2

| last = McNaughton | first = Robert

| issue = 3

| journal = Information Sciences

| pages = 305–328

| title = The loop complexity of regular events

| volume = 1

| year = 1969}}.

• {{citation

| last = Rossman | first = Benjamin

| doi = 10.1145/1379759.1379763

| issue = 3

| journal = Journal of the ACM

| page = Article 15

| title = Homomorphism preservation theorems

| volume = 55

| year = 2008}}.

• {{Citation |title=Elements of Automata Theory |last= Sakarovitch |first=Jacques |year=2009 |publisher=Cambridge University Press |isbn=978-0-521-84425-3}}
• {{citation

| last = Schreiber

| first = Robert

| doi = 10.1145/356004.356006

| issue = 3

| journal = ACM Transactions on Mathematical Software

| pages = 256–276

| title = A new implementation of sparse Gaussian elimination

| url = http://www.hpl.hp.com/personal/Robert_Schreiber/papers/1982%20Sparse%20Gaussian%20Elimination/p256-schreiber%5B1%5D.pdf

| volume = 8

| year = 1982

| access-date = 2010-01-04

| archive-url = https://web.archive.org/web/20110607103148/http://www.hpl.hp.com/personal/Robert_Schreiber/papers/1982%20Sparse%20Gaussian%20Elimination/p256-schreiber%5B1%5D.pdf

| archive-date = 2011-06-07

| url-status = dead

}}.

{{refend}}

Category:Graph connectivity

Category:Graph invariants

Category:NP-complete problems