Cycle rank
Encyclopedia
In graph theory
, the cycle rank of a directed graph
is a digraph connectivity
measure proposed first by Eggan and Büchi
. 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
Besides its original application in the
studying the star height
of formal language
s, the measure has found use
in sparse matrix
computations (see ) and logic
.
in the context of sparse matrix
computations . Apparently being unaware of the original definition from the 1960s,
later authors generalized the concept once again to digraphs .
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 . Since outerplanar graph
s, series-parallel graph
s, and Halin graph
s all have bounded treewidth, they all also have at most logarithmic cycle rank.
each vertex has cycle rank n. Apart from these, the cycle rank of a few other digraphs is known: the undirected path
of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank 
. For the directed 
-torus 
, i.e., the cartesian product
of two directed circuits of lengths m and n, we have
and 
for m ≠ n .
. The same holds true in the case of digraphs . For undirected graphs, problem remains NP-complete for cobipartite graphs , that is, complements of bipartite graphs, for bipartite graph
s , as well as for chordal graph
s . On the positive side, the problem is solvable in polynomial time on interval graphs , as well as on permutation, trapezoid, circular-arc, circular permutation graphs, and cocomparability graphs of bounded dimension . For undirected trees, the problem is even solvable in linear time .
Concerning the approximation complexity
of the problem, give an
-approximation algorithm for the undirected case.
of regular languages. 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. .
In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q0, F), consisting of
A word w ∈ Σ* is accepted by the ε-NFA if there exists a directed path from the initial state q0 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.
Proofs of this theorem are given by , and more recently by .
computations, namely for computing the Cholesky factorization of a (symmetric) matrix in parallel. A given sparse
-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 
processors .
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the cycle rank of a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
is a digraph connectivity
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
measure proposed first by Eggan and Büchi
Julius Richard Büchi
Julius Richard Büchi was a Swiss logician and mathematician.He received his Dr. sc. nat. in 1950 at the ETH Zürich under supervision of Paul Bernays and Ferdinand Gonseth. Shortly afterwards he went to Purdue University, Lafayette, Indiana...
. Intuitively, this concept measures how close a
digraph is to a directed acyclic graph
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
(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
Besides its original application in the
studying the star height
Star height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
of formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, the measure has found use
in sparse matrix
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
computations (see ) and logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
.
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
-
- 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 laterin the context of sparse matrix
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
computations . Apparently being unaware of the original definition from the 1960s,
later authors generalized the concept once again to digraphs .
Bounds
Any n-vertex forestTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
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
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
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 . Since outerplanar graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
s, series-parallel graph
Series-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...
s, and Halin graph
Halin graph
In graph theory, a mathematical discipline, a Halin graph is a planar graph constructed from a plane embedding of a tree with at least four vertices and with no vertices of degree 2, by connecting all the leaves of the tree with a cycle that passes around the tree in the natural cyclic order...
s 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 ateach vertex has cycle rank n. Apart from these, the cycle rank of a few other digraphs is known: the undirected path
of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank . For the directed -torus , i.e., the cartesian productCartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
of two directed circuits of lengths m and n, we have
and for m ≠ n .Computing the cycle rank
Computing the cycle rank is computationally hard: already in the case of undirected graphs, the corresponding decision problem is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. The same holds true in the case of digraphs . For undirected graphs, problem remains NP-complete for cobipartite graphs , that is, complements of bipartite graphs, for bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
s , as well as for chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
s . On the positive side, the problem is solvable in polynomial time on interval graphs , as well as on permutation, trapezoid, circular-arc, circular permutation graphs, and cocomparability graphs of bounded dimension . For undirected trees, the problem is even solvable in linear time .
Concerning the approximation complexity
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
of the problem, give an
-approximation algorithm for the undirected case.Star height of regular languages
The very first application of cycle rank was in formal language theory, for studying the star heightStar height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
of regular languages. established a relation between the theories of regular expressions, finite automata, and of directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s. In subsequent years, this relation became known as Eggan's theorem, cf. .
In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q0, 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 q0 ∈ 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 q0 to some final state in F using edges from δ, such that the concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
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 , and more recently by .
Cholesky factorization in sparse matrix computations
Another application of this concept lies in sparse matrixSparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
computations, namely for computing the Cholesky factorization of a (symmetric) matrix in parallel. A given sparse
-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 processors .