By replacing the word "even" with "odd," we obtain similar questions (1o), (2o), and (3o). We will also explore localized versions of each, obtained by specifying a vertex v of G and asking (for example):
The difficulty of detecting even cycles in digraphs apparently was observed first by D.H. Younger. [Younger, 1973] It is still not known whether an efficient algorithm exists for this problem, or whether it is NP-complete. The same is true for the corresponding problem for even closed trails (2e), and in fact, these two problems are equivalent. First let us prove:
Theorem (Klee, Ladner, and Manber, 1984): (1o), (2o), and (3o) all admit polynomial-time solutions.
Proof: Klee, et al. describe an efficient algorithm which solves these and (1e) by solving (1e-loc) and (1o-loc). First we demonstrate the equivalence of (1o), (2o) and (3o) by observing that a digraph has an odd cycle if and only if it has an odd closed walk.
One direction is clear: Every cycle is a closed walk. On the other hand, if W is an odd closed walk x0 x1 ... xk (xk = x0 and k is odd), and if W is not already an odd cycle, then there are two vertices repeated in this sequence. Choose i as large as possible subject to the condition that xi = xj for some i < j <= k. There is a unique such i and j, and now xi xi+1 ... xj-1 xj is a cycle. If it is an odd cycle, we are done. If not, then j-i is even and the sequence x0 x1 ... xi-1 xi xj xj+1 ... xk formed by removing the cycle is a shorter odd closed walk. Repeated application of this procedure eventually produces an odd cycle because the digraph is finite. Notice that this proof hinges on the fact that no odd integer can be represented as a sum of two even integers. In contrast, an even integer may be written as a sum of two odd integers, and so a digraph may contain an even closed walk but have no even cycles - for example, the digraph formed by the one-point union of two odd cycles.
Consequently, to solve any of (1o), (2o), and (3o) in polynomial time it suffices to construct an efficient algorithm to determine whether a graph has an odd closed walk. In fact, we will show the stronger result that (1e-loc) and (1o-loc) admit polynomial-time solutions. However, the remaining localized versions are all NP-complete.
In this algorithm, each edge enters the computation at most twice (once for each label that can be "active" on the head vertex of the edge). Thus the computational complexity for solving the localized problems (1o-loc) and (1e-loc) is linear in the number of edges of the digraph (quadratic in the number of vertices). Therefore, determining whether a digraph has an odd cycle (3o) can be solved by an algorithm with time complexity cubic in the number of vertices.
The algorithm is as follows: We are given a digraph G and a vertex v, and ask whether there is an odd (or even) cycle passing through v. Starting at v, breadth-first search through the digraph, keeping track of the parities of lengths of walks discovered. Begin by applying the label 0 to vertex v. Apply the label 1 to the vertex w to indicate the discovery of an odd walk from v to w; similarly, label w with 0 when there is an even walk from v to w. Labels are never removed, and a vertex may have both labels. When attaching a new label to a vertex, the label remains active until the vertex has been "scanned." Scanning a vertex x consists of inspecting each neighbor y of x to determine whether the recent addition of a new label to x justifies the attachment of a new label to y. The list of all vertices with active labels is kept in a queue Q, which is empty at the beginning of our computation and at the end. When the algorithm terminates, each vertex w carries a label if and only if there is a walk of that parity starting at v and ending at w.
Figure 1 gives the algorithm in pseudo-code. It consists of two functions, the main program and a subsidiary function for applying labels to vertices. Denote the set of all [active] labels of the vertex x by L(x) [A(x)]. The queue Q contains all vertices with active labels, and there are functions add_to_Q(x) and remove_from_Q() which add x to the rear of Q or remove and return the front element of Q, respectively. The functions add_element(element, set) and is_element(element, set) add the element to the set, or return 1 [0] if the element is [not] a member of the set, respectively. Each label is treated as a boolean value (0 or 1), and !s denotes the logical complement of s (read "not s").
We assume that we are given the source vertex v and the digraph in a manner such that the neighbors of a vertex can be computed efficiently. Table I lists the contents of the queue as the algorithm is run on the sample digraph in figure 2. Each vertex is followed by its currently active labels.
# subsidiary function to add labels to vertices
label(x, y, s) {
if(is_element(!s, A(x)) and !is_element(s, L(x))) {
add_element(s, A(y));
add_element(s, L(y));
if(!is_element(y, Q)) {
add_to_Q(y);
}
}
}
# main algorithm
main() {
for each neighbor y of v {
add_element(1, A(y));
add_element(1, L(y));
add_to_Q(y);
}
while Q is nonempty {
x = remove_from_Q();
for each neighbor y of x {
label(x, y, 0);
label(x, y, 1);
A(x) = empty set;
}
}
if(is_element(0, L(v))) {
print "Vertex v lies on an even closed walk";
}
if(is_element(1, L(v))) {
print "Vertex v lies on an odd closed walk";
}
}
| Step | Vertices in queue (with active labels) |
|---|---|
| 0 | empty |
| 1 | 1 (1) 2 (1) 3 (1) |
| 2 | 2 (1) 3 (1) 4 (0) 5 (0) |
| 3 | 3 (1) 4 (0) 5 (0) 1 (0) |
| 4 | 4 (0) 5 (0) 1 (0) |
| 5 | 5 (0) 1 (0) v (1) |
| 6 | 1 (0) v (1) |
| 7 | v (1) 4 (1) 5 (1) |
| 8 | 4 (1) 5 (1) 2 (0) 3 (0) |
| 9 | 5 (1) 2 (0) 3 (0) v (0) |
| 10 | 2 (0) 3 (0) v (0) |
| 11 | 3 (0) v (0) |
| 12 | v (0) |
| 13 | empty |
As already mentioned, the remaining localized problems are all NP-complete. This situation is in stark contrast to the analogous questions for undirected graphs, all of which (local and global) admit polynomial-time solutions! [La Paugh and Papadimitriou, 1984] For digraphs, the computational complexity of (2e) and (3e) remains unknown, but these two problems are equivalent:
Theorem (Klee, Ladner, and Manber, 1984): Even cycles can be detected efficiently if and only if even closed trails can.
Proof: We describe a polynomial-time algorithm A which takes a digraph G and constructs another digraph H which has an even closed trail if and only if G has an even cycle. Similarly, we describe an algorithm B which constructs a digraph with an even closed trail if and only if the original graph contains an even cycle. These algorithms are illustrated in figure 3. Because each algorithm runs in polynomial time, detecting even cycles in directed graphs is equivalent to detecting even closed trails in directed graphs.
In algorithm A, each vertex of G is replaced by three vertices x0, x1 and x2, and two edges (x0, x1) and (x1, x2). Each edge (x, y) of G is replaced by the edge (x2, y0) in H. Clearly, each cycle of length k in G is transformed into a cycle of length 3k in H. When k is even, this cycle is an even closed trail in H corresponding to the even cycle in G.
On the other hand, suppose T is a closed trail in H. The successive edges of T form a sequence of pairwise edge-disjoint paths of length three. The first two edges of each such path arise from a vertex of G, and the third edge from an edge of G. We claim that no vertex of T is ever repeated, and hence T is actually an even cycle. Consider three successive edges (x0, x1), (x1, x2), (x2, y0) in T, corresponding to an edge (x, y) of G. Now, x 2 is not repeated in T because (x1, x2) is the only edge of H into x2, and no edge of T is repeated (T is a trail, by assumption). Similarly, x1 is not repeated. But then the vertex x0 cannot be repeated either, because (x0, x1) is the only edge issuing from x0. Thus, each closed trail T in H is, in fact, a cycle of length 3k, and arises from a cycle of length k in G. Because k and 3k have the same parity, we have constructed the desired algorithm A.
Algorithm B produces the edge graph of G: For each edge (x, y) of G, there is a vertex xy in its edge graph, and (uv, xy) is an edge in the edge graph of G only when v = x. Each closed trail of length k in G involves k distinct, successively adjacent edges, thus leading to a cycle of length k in its edge graph. Conversely, each cycle of length k in the edge graph of G is a sequence of k distinct, adjacent vertices, and hence must come from a sequence of k distinct, successively adjacent edges in G (that is, a closed trail of length k in G).
Theorem: Every strongly connected directed graph with n vertices and at least floor[(n+1)2/4] edges has an even cycle, and this bound is best possible in the sense that there exist strong digraphs with fewer edges and no even cycles.
Of course, this theorem allows for the possibility that many edges are clumped together. In order to obtain better bounds, we need to exlude these cases by better distributing the edges among the vertices. One way to accomplish this task is to place lower or upper bounds on the vertex degrees. For example,
Theorem (Koh, 1976): If each vertex of a digraph G has outdegree at least two, then G contains two edge-disjoint cycles with at least one common vertex. Hence G contains an even closed trail.
Proof: If each vertex of a digraph has outdegree at least one, then the digraph has a cycle. To produce one, start from any edge (x0, x1) and continue to add edges (xk, xk+1) until some vertex is repeated in the sequence x0, ..., xk+1. Such edges exist because each vertex has outdegree at least one; until we repeat a vertex, there is always at least one outgoing edge. The graph is finite, so eventually some vertex must be repeated, and then we have found a cycle of the digraph.
Now if every vertex of G has outdegree at least two, start with some cycle C1, and let G1 denote the sugraph of G formed by removing all the edges of C1. Each vertex of G1 has outdegree at least 1, so G1 also has some cycle, C2. Now let G2 be the sugraph of G1 formed by removing the edges of C2. If C2 is vertex-disjoint from C1, then every vertex of G2 also has outdegree at least 1, and we can continue this process. Eventually we obtain two cycles with at least one vertex in common, but with no edges in common.
Given any two such cycles, if either is even then it is an even cycle, and thus an even closed trail. Otherwise, produce an even closed trail by starting at a vertex they have in common and then following first one cycle and then the other.
However, the analogous result for even cycles is not true. In fact, there exist digraphs with arbitrarily large in- and outdegrees, yet no even cycles:
Theorem (Thomassen, 1985): For each positive integer n there are digraphs Dn and Gn having no even cycles, even though
Proof: Let D1 be an odd cycle, and create Dn from Dn-1 by induction as follows: For each vertex v in Dn-1 add a set Yv of n vertices and one more additional vertex v'. Add the edge (v, v') and for each y in Yv add the edges (v', y) and (y, v). Also, for each neighbor z of v in Dn-1 and for each member y of Yv, add the edge (y, z). Then Dn is strongly connected by construction, and each vertex of Dn has outdegree exactly n. Every cycle in Dn corresponds to a cycle of the same parity in Dn-1, so Dn has no even cycles (because Dn-1 doesn't by the induction hypothesis).
Now form the digraph En by reversing all edges of Dn, so each vertex of En has indegree exactly n. Form Gn by taking vertex-disjoint copies of En and Dn and adding all the edges (e, d) for each vertex e in En and d in Dn. Thus, each vertex of Gn has outdegree and indegree at least n. Gn has no even cycles because any cycle must lie entirely in one of its strong components, En and Dn, but neither of these has any even cycles.
Any cycle of a digraph lies in one of its strongly connected components, and efficient algorithms exist for finding these components. [Tarjan, 1972] Therefore, we lose nothing if we restrict our attention to strongly connected digraphs. In fact, Thomassen asked whether the properties of Dn and En in this theorem can be combined into a single graph: Does there exist a positive integer n such that every strongly connected digraph with indegree and outdegree at least n has an even cycle? Partial answers to this question exist. For example, every d-regular digraph, d>=7, has an even cycle. [Friedland, 1989] Except when d=7, this theorem is subsumed by a result proved in an entirely different manner:
Theorem (Alon/Linial, 1989): If G is a digraph with minimum outdegree at least d and maximum outdegree at most D, and if the inequality e(Dd + 1) (1 - 1/k)d < 1 holds, then G has a cycle whose length is divisible by k. In particular, if e(dD + 1) < 2d, then G has an even cycle.
Recently, Thomassen improved this bound still further:
Theorem (Thomassen, 1992): Every d-regular digraph, d>=3, has an even cycle. As a (nontrivial) consequence, every 3-connected digraph has an even cycle.
However, this is the best possible in the sense that there exists a 2-regular, 2-connected digraph with no even cycles. [Koh, 1976; also Boyd, cited in Thomassen, 1986] This digraph, pictured in figure 4, is neatly described as the union of two 7-cycles 0123456 and 0362514. A computer search has shown that every other 2-connected, 2-regular digraph with rotational symmetry and fifteen or fewer vertices has an even cycle. [McKay, 1989, cited in Thomassen, 1993]
Theorem (Thomassen, 1992): A digraph G is even if and only if G has a weak odd double-cycle. (A weak odd double-cycle is any digraph obtainable from an odd dicycle by splitting vertices or subdividing edges.)
The recognition problem for even digraphs is equivalent to the Even Cycle Problem. [Seymour and Thomassen, 1987] As with even cycles, there are many theorems asserting that digraphs with certain connectivity or vertex degrees are even. One such theorem is that every strongly connected digraph with minimum in- and outdegrees at least three is even. In contrast to the situation for even cycles, it is known that there are infinitely many 2-connected digraphs which are not even. [Thomassen, 1992]
First, they described a polynomial-time algorithm for detecting even cycles in digraphs which are K3,3 or K5 free. [Galluccio and Loebl, 1995] (An undirected graph is H-free when it does not contain a subgraph contractible to H. A digraph is H-free when its underlying undirected graph is H-free.) Their algorithm actually extends to detecting cycles of any modularity in a directed graph, similar in spirit to the theorem due to Alon and Linial previously mentioned.
They followed up with a proof that, given a fixed but arbitrary surface, one can determine in polynomial time whether a digraph embeddable on that surface has an even cycle. [Galluccio and Loebl, 1996] Thus this result includes the previous one for planar digraphs, and constitutes a significant step toward detecting even cycles in arbitrary digraphs.