View source for Cycle rank

{{Graph connectivity sidebar}}
In [[graph theory]], the '''cycle rank''' of a [[directed graph]] is a [[directed graph|digraph]] [[Connectivity (graph theory)|connectivity]] measure proposed first by Eggan and [[Julius Richard Büchi|Büchi]] {{harv|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 graph|complete digraph]] of [[Graph (discrete mathematics)#Definitions|order]] ''n'' with a [[self-loop]] at
each vertex has cycle rank ''n''. The cycle rank of a directed graph is closely related to the [[tree-depth]] of an [[undirected graph]] and to the [[star height]] of a [[regular language]]. It has also found use
in [[sparse matrix]] computations (see {{harvnb|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}}) and [[logic]]
{{harv|Rossman|2008}}.

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

* If ''G'' is acyclic, then {{math|1=''r''(''G'')&nbsp;=&nbsp;0}}.   
* If ''G'' is [[strongly connected]] and ''E'' is nonempty, then
::<math>r(G) = 1 + \min_{v\in V} r(G-v),\,</math> 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.

==History==
Cycle rank was introduced by {{harvtxt|Eggan|1963}} in the context of [[star height]] of [[regular language]]s. 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}}.

==Examples==
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 <math>P_n</math> of order ''n'', which possesses a symmetric edge relation and no self-loops, has cycle rank <math>\lfloor \log n\rfloor</math> {{harv|McNaughton|1969}}.  For the directed <math>(m\times n)</math>-torus <math>T_{m,n}</math>, i.e., the [[cartesian product of graphs|cartesian product]] of two directed circuits of lengths ''m'' and ''n'', we have
<math>r(T_{n,n}) = n</math> and <math>r(T_{m,n}) = \min\{m,n\} + 1</math> for ''m &ne; n'' ({{harvnb|Eggan|1963}}, {{harvnb|Gruber|Holzer|2008}}).

==Computing the cycle rank==

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 <math>O(1.9129^n)</math> on digraphs of maximum [[outdegree]] at most 2, and in time <math>O^*(2^n)</math> on general digraphs. There is an [[approximation algorithm]] with approximation ratio <math>O((\log n)^\frac32)</math>.

==Applications==

===Star height of regular languages===
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 graph]]s.  In subsequent years, this relation became known as ''Eggan's theorem'', cf. {{harvtxt|Sakarovitch|2009}}.  
In automata theory, a [[nondeterministic finite automaton|nondeterministic finite automaton with ε-moves]] (ε-NFA) is defined as a [[n-tuple|5-tuple]], (''Q'', Σ, ''δ'', ''q<sub>0</sub>'', ''F''), consisting of
* a finite [[Set (mathematics)|set]] of states ''Q''
* a finite set of [[input symbol]]s Σ 
* a set of labeled edges ''δ'', referred to as ''transition relation'': ''Q'' &times; (Σ ∪{ε}) &times; ''Q''.  Here ε denotes the [[empty word]].
* an ''initial'' state ''q''<sub>0</sub> ∈ ''Q''
* a set of states ''F'' distinguished as ''accepting states'' ''F'' ⊆ ''Q''.
A word ''w'' ∈ Σ<sup>*</sup> is accepted by the ε-NFA if there exists a [[directed path]] from the initial state ''q''<sub>0</sub> 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 Σ<sup>*</sup> 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_automaton#NFA_with_.CE.B5-moves|nondeterministic finite automata with ε-moves]] accepting ''L''.

Proofs of this theorem are given by {{harvtxt|Eggan|1963}}, and more recently by {{harvtxt|Sakarovitch|2009}}.

===Cholesky factorization in sparse matrix computations===
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 <math>(n\times n)</math>-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 <math>n</math> processors {{harv|Dereniowski|Kubale|2004}}.

==See also==
* [[Circuit rank]]

==References==
{{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
 | url = ftp://ftp.parc.xerox.com/pub/gilbert/csl9010.ps.Z
 | volume = 18
 | year = 1995
 }}{{dead link|date=August 2017 |bot=InternetArchiveBot |fix-attempted=yes }}.
*{{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
 | 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}}.
*{{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 = [[International Colloquium on Automata, Languages and Programming|Proc. 35th International Colloquium on Automata, Languages and Programming]]
 | contribution-url = http://www.hermann-gruber.com/data/icalp08.pdf
 | volume = 5126
 | year = 2008}}.
*{{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=0-521-84425-8}}
*{{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]]