Finding Even Cycles Even Faster.
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every $k \geq 2$, there is an $O(V^2)$ time algorithm that decides whether an undirected graph $G=(V,E)$ contains a simple cycle of length $2k$, and finds one if it does. (ii) There is an $O(V^2)$ time algorithm that finds a shortest even cycle in an undirected graph $G=(V,E)$.
Introduction
Throughout this work, the term cycle refers to a simple closed walk and the term path refers to a
simple non-closed walk. An even (odd) cycle is a cycle whose length is even (odd). An even (odd)
path is a path whose length is even (odd).
The problem of finding cycles of a given length, and of finding a shortest, a shortest even, and
a shortest odd cycle in undirected and directed graphs are among the most basic and natural
algorithmic graph problems. These problems were considered by many researchers, see [10] for a
survey.
In this work we consider (almost exclusively) the undirected versions of these problems. The directed
versions of some of them are believed to be much harder. The problem, "does a given directed
graph E) contain a directed cycle of an even length?", for example, is not known to be in P,
nor is it known to be NP-complete (see [9]). Though we do not shed any new light on the directed
versions of the problems, we obtain surprisingly fast algorithms for some of the undirected versions.
Monien [7] presented an O(VE) algorithm for finding all pairs of vertices that are connected by paths
of length is a fixed integer. (Note that if k is part of the input, the problem
is NP-Hard). A simple consequence of his algorithm is an O(VE) algorithm for finding a cycle of
length k, if one exists. In [1], an O(M(V ) log V ) algorithm is obtained for the same problem, where
is the complexity of Boolean matrix multiplication. This algorithm is more efficient
when G is dense. Both algorithms work on directed as well as undirected graphs. In this work we
Work supported in part by THE BASIC RESEARCH FOUNDATION administrated by THE ISRAEL ACADEMY
OF SCIENCES AND HUMANITIES. A preliminary version of this paper had appeared in the Proceedings of the 21st
International Colloquium on Automata, Languages and Programming, Jerusalem, Israel, 1994, pages 532-543.
y Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, ISRAEL.
E-mail addresses of authors: fraphy,zwickg@math.tau.ac.il
show that if k is even and if the graph is undirected, then both these bounds can be improved. We
obtain an O(V 2 ) algorithm for finding cycles of a given even length in undirected graphs. An O(V 2 )
algorithm for finding quadrilaterals (cycles of length four) is part of the folklore (cf. [8]) but all other
cases are new. To obtain this O(V 2 ) algorithm we utilize a combinatorial theorem of Bondy and
Simonovits [4] that states, roughly, that dense enough undirected graphs contain many even cycles.
We also prove a constructive version of their theorem.
The O(V 2 ) algorithm for finding cycles with a given even length leads to the following strange
state of affairs: Deciding whether a given undirected graph contains a cycle of length, say, 100,
is asymptotically faster than deciding, using any known algorithm, whether this graph contains
a triangle (a cycle of length 3)! The term 'asymptotically' above should be stressed, as our O(V 2 )
bound, as well as Monien's O(VE) bound, hides huge multiplicative factors that depend exponentially
on k. This exponential dependence on k is probably unavoidable as the problem is NP-hard if k is
part of the input.
A shortest cycle in a directed or undirected graph E) can be easily found in O(VE) time by
conducting a BFS (breadth first search) from each vertex. Itai and Rodeh [5] show that a shortest
cycle can also be found in O(M(V time in the undirected case, and in O(M(V ) log V ) time in the
directed case. They also notice that by halting the BFS conducted from each vertex in the O(VE)
algorithm when the first non-tree edge is found (this implies an O(V ) running time for each BFS),
an almost shortest cycle (a cycle whose length exceeds the length of a shortest cycle by at most one)
in an undirected graph can be found in O(V 2 ) time.
Monien [6] described a sophisticated O(V 2 ff(V )) algorithm for finding shortest even cycles (SELCs
for short) in undirected graphs, where n) is the functional inverse of Ackermann's
function. His algorithm uses the fast Union-Find data structure. We describe an O(V 2 ) algorithm
for finding SELCs. Our algorithm is somewhat simpler and it does not use any sophisticated data
structure. At the heart of our algorithm lies a combinatorial lemma which is of interest in its own
right. The lemma states that if C is a shortest even cycle in a graph, then there exists a vertex v on
C from which the paths, on the cycle, to all the other vertices on the cycle are almost the shortest
possible. In fact, each of these paths is of length at most one greater than the distance between the
endpoints of the path.
each path on the cycle from v to a vertex u is either a shortest path or exceeds the length of the
shortest path from almost the shortest possible.
We also describe a simple O(M(V finding a shortest odd cycle (SOLC for short)
in an undirected graph E) and a simple O(VE) algorithm for finding a SOLC in a directed
or undirected graph E). Monien [7] described an O(VE) algorithm for the undirected case.
This paper is organized as follows. In Section 2 we present the algorithm for finding fixed length
even cycles in undirected graphs. In Section 3 we investigate the combinatorial structure of SELCs.
In Section 4 we describe the algorithm for finding a SELC and prove its correctness. In Section 5
we describe the simple algorithms for finding SOLCs in directed and undirected graphs. We end, in
Section 6 with some concluding remarks.
Finding Even Cycles of a Given Length
Throughout this section we use C l to denote a cycle of length l. The main result of this section is
the following theorem:
Theorem 2.1 For every k - 2, there is an O((2k)! decides whether an
undirected graph E) contains a C 2k and finds one if it does.
We also obtain the following result which is an algorithmic version of a result by Bondy and
Simonovits [4].
Theorem 2.2 Let l - 2 be an integer and let E) be an undirected graph with jEj -
100l \Delta jV j 1+1=l . Then G contains a C 2k for every k 2 [l; l \Delta jV j 1=l ]. Furthermore, such a C 2k can be
found in O(k In particular, a cycle of length exactly bl \Delta jV j 1=l c can be found in O(V 2+1=l )
time.
It is interesting to comment on the relation between these two theorems. In any undirected graph
E) and any k - 2, we can find a C 2k , if one exists, in O((2k)! This running time
is O(V 2 ) for every fixed k - 2. The running time is exponential, however, if k is part of the input.
If the graph E) is dense enough, i.e., if it
does contain a
C 2k , and such a C 2k can be found in O(k \DeltaV 2 ). Note that this is now polynomial in both V and k. In
dense enough graphs, we can therefore find extremely long cycles efficiently. In a graph containing
example, we can find, in O(V 2:5 ) time, a cycle of length \Theta(V 1=2 ). This should
be compared with the fact that the problem of deciding whether an undirected graph E)
contains a cycle (or an even cycle) of
The first ingredient used in the proofs of Theorems 2.1 and 2.2 is a combinatorial lemma of Bondy
and Simonovits [4] (see also [3]). Their proof of the Lemma is non-constructive. By slightly altering
their arguments we obtain a constructive version of their Lemma which is required in the proof of
Theorem 2.2. Before stating the Lemma we need the following definition.
Definition 2.3 A coloring of the vertices of an undirected graph E) is said to be t-periodic
if the endpoints of every path of length t are colored by the same color.
Note the coloring in the definition above is not required to be proper, i.e., adjacent vertices may be
colored by the same color. We can now state the Lemma of Bondy and Simonovits [4] and present
an algorithmic proof of it.
Lemma 2.4 Let t be a positive integer, and let E) be a connected undirected graph with
coloring of the vertices of G that uses at least three distinct colors is not
t-periodic. Furthermore, if G is non-bipartite, then any coloring of the vertices of G that uses at
least two distinct colors is not t-periodic. In both the bipartite and non-bipartite cases, two vertices
of distinct colors and a path of length t connecting them can be found in O(E) time.
Proof: We begin by showing that G contains two adjacent vertices joined by two vertex-disjoint
paths, each of length at least t, and that such a subgraph, called a \Theta-graph, can be found in O(E)
time. It is easy to see that G contains a subgraph G 0 whose minimal degree is at least 2t. Such a
subgraph can be easily found in O(E) time by sequentially removing from G vertices whose degrees
are less than 2t. Let be a maximal path in G 0 , i.e., a path that cannot be further
extended. Such a path can be greedily constructed in O(E) time. The vertex v 1 is then adjacent
to at least 2t vertices 2t on this path, where . The path
along with the edges (v 1
the desired \Theta-graph.
The \Theta-graph found contains three distinct cycles respectively, such that
2. Every vertex v of the \Theta-graph has at most four distinct paths of
length t in the \Theta-graph that start at v. We can easily check in O(V ) time whether, for each v, the
endpoints of these paths are colored by the same color of v. If this is not the case then we are done,
since we have found two vertices colored by distinct colors and a path of length t connecting them.
Assume therefore that the \Theta-graph is t-periodic. It is easy to see that if one of the cycles
L 3 is t   -periodic then the other cycles, and therefore the \Theta-graph, must also be t   -periodic. Let t
be the smallest integer for which the \Theta-graph is t   -periodic. It follows that t   is also the smallest
period of the cycles and as a consequence t   jl As l 1 we get that
and the number of colors used to color the \Theta-graph is at most 2.
Every vertex of G is connected by a simple path whose length is a multiple of t to a vertex of, say,
colored by color not appearing on L 1 , then a simple path t whose endpoints
are colored by distinct colors can be easily found in O(V ) time.
Finally, note that a 2-periodic coloring of a graph E) that uses two colors is necessarily a
proper coloring. Any graph E) that has a 2-periodic coloring that uses only two colors must
therefore be bipartite. 2
The second ingredient used in the proof of Theorem 2.1 is the following result of Monien [7].
Lemma 2.5 There is an O(k! \Delta E) time algorithm that given a (directed or undirected) graph
E), an integer k - 2 and a vertex s 2 V , finds all vertices connected to s by
paths of length k, and exhibits one such path for each such v.
The following are immediate consequences of Lemma 2.5.
Corollary 2.6 Let E) be a (directed or undirected) graph and let k - 3 be an integer. There
is an O((k \Gamma 1)!\DeltaE) time algorithm that given a vertex s 2 V decides whether there is a C k that passes
through s and finds such a C k if one exists.
Proof: Find all the vertices connected to s by paths of length check whether one of them
is also connected to s by an edge. 2
Corollary 2.7 Let E) be a (directed or undirected) graph and let k - 1 be an integer. There
is an O((k E) time algorithm that given two disjoint subsets A and B of vertices, determines
whether there is a path of length k connecting a vertex from A and a vertex from B, and finds such
a path, if one exists.
Proof: Assume that the graph is directed (if not, replace each undirected edge by two anti-parallel
directed edges). Add a new vertex s and connect it to all the vertices of A. Now find all the vertices
to which there are directed paths of length
Alon, Yuster and Zwick [1] have recently described a 2 O(k) performing
the task of Lemma 2.5 and 2 O(k) \DeltaE expected time algorithms for the tasks of Corollaries 2.6 and 2.7.
The dependency on k in the above complexity bounds can be improved, therefore, from k! to 2 O(k)
if randomization, or an extra log V factor are allowed.
We are now ready to prove Theorem 2.1. We prove, in fact, the following slightly stronger result:
Theorem 2.8 Let k ? 1 be a fixed integer. There is an O((2k)! that given an
undirected graph E) and a vertex s 2 V either verifies that s is not contained in any C 2k ,
or finds a C 2k in G (not necessarily passing through s).
Proof: The algorithm starts a BFS from the vertex s. For be the distance between s
and v in G. Let L ig be the set of vertices at level i of the BFS tree. At stage i
the algorithm scans the adjacency lists of the vertices of L i . During this scan, the algorithm keeps
a count of the number of edges found so far inside L i (an edge is inside L i if both its endpoints are
in L i ). Similarly, it keeps a count of the number of edges found so far between L i and L i+1 . We use
i+1 to denote the set of vertices of L i+1 that were already discovered by the search. The search is
halted when one of the following conditions hold:
1. Stage k \Gamma 1 has completed, or the BFS has ended.
2. At least 4k \Delta jL i j edges were found inside L i .
3. At least 4k \Delta (jL
Since the L i 's are disjoint, the total number of edges scanned before the search is halted is at most
12k \Delta jV j. Hence, the search takes only O(k
As in any BFS, when a vertex v 2 L i is discovered, we let -(v) be the vertex in L i\Gamma1 that discovered it.
In such a way a shortest path tree rooted at s and consisting of all discovered vertices is maintained.
The algorithm continues in one of three possible ways, according to the condition that caused the
BFS to halt.
Case 1: The BFS is halted because stage
In this case, the first k+1 levels L have all been discovered and the subgraph G 0 induced
by them (but not containing the edges inside L k ) contains at most 12k \Delta jV j edges. If s is on a C 2k
then this C 2k is completely contained in G 0 . By corollary 2.6, we can check whether such a cycle
exists in O((2k)!
Case 2: The BFS is halted because 4k \Delta jL i j edges were found inside L i , for some i ! k.
Stage i of the search is then left incomplete but all the first i are already
completely discovered. Consider the subgraph of G induced by L i . This subgraph contains at least
one connected component whose vertex set is U ' L i and whose number of edges is at least 4k \Delta jU j.
Denote the subgraph composed of this connected component by H . Such a subgraph is easily found
in O(k \Delta time. Note that jU j ? 1.
Assume at first that H is non-bipartite (this is easily verified in O(k\DeltaV ) time, since H contains O(k\DeltaV
edges). Let c be the lowest common ancestor in the BFS tree of all the vertices in U . The vertex c is
easily found in O(k\DeltaU in the following
fcg. As jU j ? 1, c must
have at least two children in U h+1 . Let d be one of them. Let X 1 ae U be the descendents of d in
U and let Color the vertices of X 1 red and the vertices of X 2 blue. By Lemma 2.4,
the subgraph H cannot be (as it is non-bipartite, connected and colored by two
distinct colors). There must therefore be a path of length between a red vertex and
a blue vertex. As explained in the proof of Lemma 2.4, we can find such a path p in O(k\DeltaU
time (such a path can also be found using corollary 2.7 but the running time would be O((2k)!\DeltaV )).
The path p can now be extended to a cycle of length 2k by adding the disjoint paths of the BFS tree
from c to the two endpoints of p, each having length Note that this cycle contains s only if
Very similar actions are taken if H is bipartite. Let A and B be the vertex classes of H (i.e., A and
are disjoint, A [ U and all the edges in H are between A and B). Assume, without loss of
generality, that jAj ? 1. Let c be the lowest common ancestor in the BFS tree of all the vertices
of A. The vertex c is found using the way described above. Assume again that c is in level h. As
must have at least two children in level h + 1. Let d be one of them. Let X 1 ae A be
the descendents of d in A and let Color the vertices of X 1 red, the vertices of X 2
blue, and the vertices of B green. By Lemma 2.4, the subgraph H cannot be
as it is connected and colored by three distinct colors. There must therefore be a path p of length
between two differently colored vertices. This path must be between a red vertex
and a blue vertex as any path of an even length that starts at a green vertex also ends at a green
vertex. This path can again be found in O(k can again be extended to a cycle of
length 2k.
Case 3: The BFS was halted because 4k \Delta (jL
Find a connected subgraph H of the subgraph of G induced by L i and L 0
with a vertex set U and
with at least 4k\DeltajU j edges. Such a subgraph is easily found in O(k \DeltaV ) time. Note that H is bipartite
with vertex classes
. The algorithm can now proceed as in the previous
case.
In any one of these three cases, the running time is O((2k)! \Delta V ). In fact, the running time of the
algorithm in the second and third cases is only O(k \Delta V ). The only case in which a C 2k is not found
by the algorithm is when no C 2k passes through s. This completes the proof of the Theorem. 2
Theorem 2.1 follows immediately from the above Theorem. All we have to do is to apply the
algorithm described above from each vertex. We now turn to the proof of Theorem 2.2. The proof
of Bondy and Simonovits actually shows that if jEj - 100l \Delta jV j 1+1=l and k 2 [l; l \Delta jV j 1=l ] then there
exists a vertex s 2 V for which the algorithm of Theorem 2.8 stops before completing stage k \Gamma 1.
This immediately leads to the desired O(k \DeltaV 2 Theorem 2.8 has another interesting
consequence:
Theorem 2.9 A C 2k in an undirected graph E) with jEj - 101k \Delta jV j 1+1=k can be found in
expected time.
Proof: Any graph on jV j vertices and at least 100k \Delta jV j 1+1=k edges contains a C 2k . It follows
immediately, that the number of edges in a graph E) which are not contained in any C 2k
is at most 100k \Delta jV j 1+1=k . If E) contains at least 101k \Delta jV j 1+1=k edges then a randomly
chosen edge has a probability of at least 1=101 of belonging to a C 2k . The randomized algorithm
simply chooses a random edge and applies the algorithm of Theorem 2.8 to one of its endpoints. The
expected number of applications before a desired C 2k is found is O(1) and the expected running time
is O((2k)!
3 The Structure of Shortest Even Length Cycles
Let G be an undirected graph and let C be a SELC (shortest even length cycle) of it. Suppose the
vertices on the cycle are consecutively labeled We denote by d(x; y) the distance
between two vertices x and y in G. Clearly d(v
then C, or some other SELC, can be easily
found using a BFS from v 0 . However, the paths on C between v 0 and v i and between v 0 and v 2k\Gammai
are not necessarily shortest paths in G. As an example, consider K 4 , the complete graph on four
vertices. All the even cycles in K 4 are of length 4 but the distance between any two vertices is 1. It
may be, therefore, that d(v k. It is not immediately
clear how to find C, or any other SELC, in such a case.
The main result of this section is the following lemma that states that on every SELC C there is a
vertex v 0 from which the paths, on C, to all the other vertices on C are almost shortest paths. An
almost shortest path is a path whose length exceeds the length of a corresponding shortest path by
at most one. Specifically,
Lemma 3.1 Let C be a SELC of G. Then, the vertices on C can be consecutively labeled
This lemma is the cornerstone of the O(V 2 ) algorithm for finding SELCs presented in the next
section. We think, also, that this lemma is of interest in its own right. Before presenting a proof of
Lemma 3.1, we present the following simple but useful lemma.
Lemma 3.2 If p 1 and p 2 are two distinct (but not necessarily disjoint) shortest paths in G between
x and y, then C contains an even cycle whose length is at most 2d(x; y).
be two distinct shortest paths
between be the minimal index such that a
a be the minimal index j ? i such that a
are two shortest paths connecting a i and a j whose inner vertices are disjoint. We thus obtain a cycle
of length
Proof of Lemma 3.1 Let H be a minimal subgraph of G (with respect to containment) containing
C such that dH (x; denotes the distance between x and y
in H). Let e(H) be the edge set of H . If are done. Otherwise, let
A path p whose two endpoints a and b are on C, but none of its inner vertices are on C, that satisfies
is the length of p, is called an a - b shortcut . Our first claim is
that P is a collection of vertex disjoint shortcuts.
a
a i
c
a b
x

Figure

1: One of the cycles C
a
c
d
e
f
a i
a j

Figure

2: The shortcuts of P .
To see this, let P 0 be a connected component of P . The minimality of H implies that any edge of P 0
is contained in some shortcut. The component P 0 must therefore contain an a - b shortcut p 1 for
some a; b 2 C. If P 0 is composed solely of this shortcut, we are done. Otherwise, let x be a vertex
on incident to an edge e of P 0 which is not on p 1 (x may be a or b). The edge e is contained in
some shortcut p 2 . The shortcuts p 1 and p 2 meet only at x. If they had met in some other vertex
y, a shorter even cycle would have existed, by Lemma 3.2, in the graph. Let p 3 be a portion of p 2
that connects x with some vertex c on C. Consider now the cycles C shown on the
left of Fig. 1. Each of these cycles is of size less than 2k. For C 1 , this follows from the fact that
We show that jC 2 j ! 2k as follows: Let C 4 be the cycle comprised of p 1 with the
part of C between a and b containing c. Since jp we have that jC 4 As p 3 is a
shortest path between c and x, we get that jC 2k. The fact that jC 3 2k follows from
similar arguments. The sum of the lengths of these cycles is 2k which is even, and
thus one of them must be even, contradicting the minimality of C. This contradiction shows that P 0
must simply be a shortcut.
We have shown that is a set of disjoint shortcuts were s (as each shortcut
contains two vertices of C). We now claim that every two distinct shortcuts p i and p j must cross
one another, i.e., each of the two paths on C between the endpoints of p i contains an endpoint of p j .
See the left of Fig. 2.
Assume, for contradiction, that the shortcuts p i and p j do not cross one another, as shown on the
right of Fig. 1. The length of each of the cycles C there is less than 2k. The sum of
their lengths is 2k so one of them must be even, contradicting the minimality of C.
We have shown that the mutual position of p i and p j must be as shown in the middle of Fig. 2.
Let a; b; c; d denote the four segments of C determined by the endpoints of these shortcuts. The
minimality of C implies that jp are all odd,
since these are lengths of cycles smaller than 2k. This, in turn, implies that jp
are even. These two expressions are the lengths of the 'twisted' cycles a;
and b; As a consequence, these lengths are at least 2k. In particular,
Our third claim is that for any two vertices x; y on the cycle C there exists a shortest path between
them that uses at most one shortcut. Consider a shortest path between x and y that contains at
least two shortcuts. Let p i and p j be two consecutive shortcuts appearing on the path. Let c be the
portion of the path that connects them, as shown again in the middle of Fig. 2. From (1), we get
that jp jdj. We can therefore replace the portion of the path by the
path b; c; d without increasing the length. Continuing in this way, we can obtain a shortest path that
uses at most one shortcut. In view of Lemma 3.2, a shortest path that uses more than one shortcut
must connect two antipodal vertices, i.e., two vertices whose distance is k, on the cycle.
It is convenient at this point to fix a consecutive numbering 0; of the vertices of the
cycle C and identify the vertices of C with their numbers. We let a i and b i , where a , be the
two endpoints of the shortcut p i . To every shortcut p i we attach the following interval
Both endpoints of this interval are integral as b i \Gamma a i and jp i j have different parities, otherwise C
would not have been a SELC. As jp
to a subset of the vertices of C.
We claim that if v 2 C i , then for every vertex u on C, if a shortest path between v and u uses
the shortcut p i as its only shortcut, then the path between v and u along the cycle C is an almost
shortest path between v and u. Recall that an almost shortest path between v and u is a path whose
length is at most d(v; u) + 1. To see this, suppose that v 2 C i and that some shortest path from v
to u uses p i as its only shortcut. This shortest path must either go along portion e of the cycle C
from v to a i , then use p i and then go again along C, or go along portion f of the cycle C from v
to b i , then use p i and then go again along C. Both cases are shown on the right of Figure 2. The
definition of C i implies, however, that
The path e; p i can therefore be replaced by the path f , and the path f; p i can be replaced by the
path e while increasing the length by at most one, as required.
Our final task is to show that the intersection " s
of all these intervals is not empty. If v
then the paths along C from v 0 to all other vertices on the cycle are almost shortest paths, as required.
As all the C i 's are intervals, it is enough to show that any two of them intersect. Let C i and C j be two
such intervals where a i ! a j . The fact that p i and p j cross one another implies that a i ! a
To show that C i and C j intersect, we show that
and
The first inequality is equivalent to jp
is the length of the twisted cycle a; shown in the
middle of Fig. 2. The length of this cycle is at least 2k by (1) proving the first inequality. The second
inequality follows immediately from the fact that a i ! a We have shown therefore that
the intervals C i and C j , and therefore all the intervals, do intersect.
Any vertex
can play the role of v 0 in the statement of the Lemma. This completes the
proof of the Lemma. 2
If a SELC C is edge disjoint from all other SELCs, then a sharp inequality holds in (1). This can be
used to show that all the intervals C 0
Every vertex v 0 in this
intersection has the property that the shortest paths along the cycle C from v 0 to all other vertices
are in fact shortest paths. The intersection " s
may however be empty if C is not edge disjoint
from all other SELCs.
be an ordering of C that satisfies the conditions of Lemma 3.1. In view of Lemma 3.2,
it is impossible that d(v yields two shortest paths of lengths
We may assume therefore, without loss of generality, that d(v
We call v 0 a root of C. If d(v a cycle of type one w.r.t. v 0 , and if d(v
we call C a cycle of type two w.r.t. v 0 . Every cycle of type two w.r.t. v 0 has a unique
such that d(v the index of C w.r.t. the root v 0 .
Finally, we note that if v 0 ; . ; v 2k\Gamma1 is an ordering of C that satisfies the conditions of Lemma 3.1,
then is also such an ordering, i.e., v k can play the role of v 0 .
4 An O(V 2 ) Algorithm for Finding a Shortest Even Cycle
Relying on Lemma 3.1, we obtain an O(V 2 ) algorithm for finding a SELC in an undirected
graph E). The algorithm starts a BFS from every vertex but stops it as soon as an even
cycle is detected. This ensures that the time spent in each such BFS is at most O(V ). We show that
the shortest even cycle found in this way by the algorithm is indeed a SELC of the graph.
The BFS performed is an augmented version of the standard BFS capable of detecting even cycles.
Let a be a vertex from which such an augmented BFS is performed (a is called the root of the BFS).
We record for every vertex v, a set of four variables. The first two variables are standard, the other
two are used to detect even cycles. These four variables are:
- the distance of v from a, i.e., the level of v in the BFS tree; has not yet been
discovered.
-(v) - the parent of v in the BFS tree; a or if v has not yet been discovered. If
'(v) - the match of v; if '(v) 6= 0 then '(v) is a vertex in the same level of v such that (v; '(v)) 2 E.
A vertex v is said to be matched if '(v) 6= 0. If v is matched then '(v) will also be matched
and v. The set of edges f(v; '(v)) j '(v) 6= 0g is therefore a matching.
ae(v) - the highest proper ancestor of v in the BFS tree that is matched. If v has no matched proper
ancestors then
We now describe how we process a vertex v that has been popped out of the BFS queue. Before we
start scanning v's neighbors, we assume that ae(v); d(v) and -(v) are correctly set (v may or may not
be matched at this point depending on whether it is adjacent to a vertex in its level that has been
processed before it). The action taken for an edge (v; u) depends on the value of d(u); '(v) and '(u)
in the following way:
1. If do nothing (this edge has been processed before, in its opposite direction).
2. If enqueue u to the BFS queue.
3. If the BFS as an even cycle was found. Let c be the lowest common
ancestor, in the BFS tree, of v and u. Then the c - v and c - u tree paths and the edge (v; u)
form an even cycle of length 2(d(v) This cycle is shown in Fig. 3.
4. If (which also means that do nothing (this edge has been
processed before, in its opposite direction).
5. If and '(u) are not both zero, halt the BFS as an even cycle
was found. Assume, for example, that c be the lowest common ancestor, in
the BFS tree, of x and u. The c - x and c - u tree paths and the edges (x; v); (v; u) form an
even cycle of length 2(d(v) This cycle is shown in Fig. 3.
6. If test whether ae(u). If they are equal, let '(v) / u,
'(u) / v. If they are not equal, halt the BFS as an even cycle is found as follows. Assume,
for example, that c be the lowest common ancestor, in the
BFS tree, of y and u. Then the c - y tree path followed by the edge (y; x) followed by the
path followed by the edge (v; u) followed by the u - c tree path closes an even cycle
of length 2(d(v) This cycle is shown in Fig. 3. Note that this is a cycle (i.e., it is
simple) since x is not an ancestor of u.
After we finish scanning all the neighbors of v, we rescan them to set ae(u) for every u that has become
a child of v. We put ae(u) / ae(v) unless which case we put ae(u) / v. This
completes the description of the algorithm.
Theorem 4.1 The augmented BFS scans no more than 3jV j=2 edges and therefore runs in O(V )
time. Furthermore, If C is a SELC of length 2k and v 0 is a root of it, then an augmented BFS that
starts from v 0 finds an even cycle of length 2k.
Proof: When the BFS halts (either because it has completed, or because an even cycle has been
found), the only edges scanned are the BFS tree edges, the edges between matched vertices (these
c
c
s
c
x y

Figure

3: The even cycles detected by rules 3,5 and 6
wm

Figure

4: If ae(v k
edges form a matching) and possibly an edge that closes an even cycle. There are at most jV
tree edges and at most (jV edges in the matching (the root of the BFS is never matched).
The total number of edges scanned is therefore at most 3jV j=2. The complexity claim is obvious as
scanning an edge entails only a constant number of operations.
We now prove the second part of the theorem. Consider an augmented BFS that starts at a root
v 0 of a SELC C. Note, according to the above six rules, that if the BFS halts while scanning the
neighbors of a vertex v, the even cycle found has a length of at most 2(d(v) 1).
Suppose that C is a SELC of type one w.r.t. v 0 (type one and type two SELCs were defined at the
end of the previous section). Then v are both in level of the BFS. Suppose that
v k+1 is processed after v k\Gamma1 . If an even cycle is found before the edge (v its length
must be 2k (it cannot be shorter, of course). Otherwise, an even cycle of length 2k is found, using
rule 3, when the edge (v
Suppose that C is a SELC of type two, with index are all
in level of the BFS. If an even cycle of length 2k is not found before processing the vertex v k ,
such a cycle is found, using rule 5, when v k is processed as it is adjacent to two vertices in its level.
Finally, suppose that C is a SELC of type two, with are in level
of the BFS (and v k+1 is in level k \Gamma 2). We claim that ae(v therefore an even
cycle is found, using rule 6, when the edge (v if such a cycle were not found before.
First, note that '(v 2k\Gammaj (both are in level j, there is an edge between them, and we did not
halt at level j). Second, note that (v
are shortest paths in G (refer to Fig. 4). As these shortest paths connect vertices whose distance is
less than k, they must be the unique shortest paths between these vertices (cf. Lemma 3.2). These
paths must therefore be tree paths, i.e., they must be contained in the BFS tree. It follows that
is the ancestor of v k at level j. Therefore, ae(v k ) 6= 0. If ae(v are done. Otherwise
are the proper ancestors of v
unmatched). Assume, for contradiction, that ae(v k matched ancestor of
is an ancestor of v 2k\Gammaj \Gamma1 . Let be the match of v m , and
let v 2k\Gammar be the lowest common ancestor, in the BFS tree, of wm and v 2k\Gammaj (v 2k\Gammar may be v 0 ). We
obtain the following even cycle (cycle C 1 in Fig. 4) in G: v m -
denote the tree paths between these vertices,
and are the edges matching these vertices. The tree paths v m -
may coincide initially, this causes no problems. The cycle C 1 is indeed a cycle, i.e.,
it is simple, because it is composed of tree paths that cannot interset one another. The length of C 1
is contradicting the minimality of C. 2
As a corollary of Theorem 4.1, we get that any graph containing more than 3(V \Gamma 1)=2 edges contains
an even cycle. A simple example shows that this bound is best possible. Just take any connected
graph whose biconnected components are triangles. Furthermore, checking whether a graph contains
an even cycle and exhibiting one if it does can be done in O(V ) time. Just perform one augmented
BFS from an arbitrary vertex.
Finally, we point out that the result of this section is not implied by the results of Section 2. We
cannot afford checking, for whether the graph contains a C 2k as the length of the
smallest even cycle may be large.
5 Finding a Shortest Odd Cycle in Undirected and Directed
Graphs
Shortest odd length cycles (SOLCs) can be found in polynomial time in both directed and undirected
graphs. Our objective in this section is to describe very simple, yet efficient, algorithms for both
these problems. Monien [6] obtained a simple O(VE) time algorithm for finding SOLCs in undirected
graphs. Using fast Boolean matrix multiplication algorithms we obtain an O(M(V
for the same task. This algorithm is more efficient than Monien's algorithm for dense graphs.
Theorem 5.1 There is an O(M(V that finds a shortest odd cycle in an
undirected graph E).
Proof: Let A be the adjacency matrix of G. We assume that G is non-bipartite as otherwise it
contains no odd cycles. Recall that A k (i; there is a closed walk of length k from i to itself
(the multiplications used to obtain A k are assumed to be Boolean). Since any closed walk of an odd
length contains an odd cycle, the length of the SOLCs of G is the minimal odd k for which there exists
an i such that A k (i; As G is undirected, A t (i; 1. We can therefore
look for this minimal k using the following approach. Start computing A; A 3
binary search along the odd numbers between 2
then be used to find k. The number of Boolean matrix multiplication required is clearly O(log V ).
A specific SOLC of length k can be found without increasing the complexity of the algorithm. 2
We turn our attention now to finding shortest odd cycles in directed graphs. Unlike in the undirected
case, subpaths of SOLCs are not necessarily shortest paths, and therefore a simple BFS from every
vertex does not suffice. Let ed(u; v) be the length of a shortest even length directed walk from u to v.
Similarly, let od(u; v) be the length of a shortest odd length directed walk from u to v. If no odd
length walk exists we set od(u; 1). Note that the existence of a walk of
length ed(u; v) (od(u; v)) does not imply the existence of a simple walk of length ed(u; v) (od(u; v)).
Lemma 5.2 If of a directed graph G then ed(v
.
Proof: Any closed walk of an odd length contains an odd cycle. There is an odd length closed walk
containing v 0 whose length is ed(v 2i. The minimality of C implies that ed(v
There is however a path of length 2i between v 0 and v 2i and therefore ed(v 2i. The second
equality in the statement of the lemma follows using similar arguments. 2
Given a vertex s, we can easily compute ed(s; v) and od(s; v), for every, v 2 V as follows. Construct
a graph G
The graph G 0 is a directed bipartite graph that contains an even representative v e and an odd
representative v o for every vertex . It is easily seen that ed(u;
denotes the distance between u 0 and v 0
in G 0 . By performing a BFS on G 0 from s e , we can therefore find ed(s; v) and od(s; v), for every
assume the graph contains no isolated vertices).
For every s 2 V , we can find, in O(E) time, a shortest odd length closed walk that contains s. We
simply compute Eg. If oc(s) 6= 1, then a closed walk of length
oc(s), which is the minimal possible odd length, is easily found by tracing a shortest odd path from s
to any vertex for which the minimum was achieved. The shortest odd length closed walk found in
this way must be a SOLC. We thus obtain the following:
Theorem 5.3 A shortest odd length cycle in a directed graph one exists, can be found
in O(VE) time.
6 Concluding Remarks
We have shown that interesting combinatorial properties of even cycles in undirected graphs lead to
very efficient algorithms for finding even cycles of a given length and for finding shortest even cycles.
Note that if the input graph is given using an adjacency matrix then these O(V 2 ) algorithms are
optimal. It seems plausible to conjecture that O(V 2 ) is the best possible bound, in terms of V , for
these problems even if the adjacency lists of the graphs are given as input. Note that O(V 2 ) time is
currently the best known time even for finding quadrilaterals (C 4 's).
Based on the results of this paper, Alon, Yuster and Zwick [2] have recently obtained an
finding a C 4 in undirected graphs. More generally, a C 4k can be found in
These algorithms are better than the O(V 2 presented here
for relatively sparse graphs. It is interesting to note that the hardest cases for the C 4 problem, for
example, are graphs with \Theta(V 3=2 ) edges.
The authors would like to thank Noga Alon for many helpful discussions.



--R

Color-coding. Journal of the ACM
Finding and counting given length cycles.
Extremal graph theory.
Cycles of even length in graphs.
Finding a minimum circuit in a graph.
The complexity of determining a shortest cycle of even length.
How to find long paths efficiently.
Finding cycles of a given length.
Even cycles in directed graphs.
Graph algorithms.
--TR

--CTR
Friedrich Eisenbrand , Fabrizio Grandoni, Detecting directed 4-cycles still faster, Information Processing Letters, v.87 n.1, p.13-15, July
Harold N. Gabow , Shuxin Nie, Finding a long directed cycle, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
graph algorithms;cycles