We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results. Key Words. Graph algorithms, Cycles. 1. Introduction. TheproblemofdecidingwhetheragivengraphG = (V, E)contains a simple cycle of length k is among the most natural and easily stated algorithmic graph problems. If the cycle length k is part of the input, then the problem is clearly NPcomplete as it includes in particular the Hamiltonian cycle problem. For every fixed k, however, the problem can be solved in either O(VE) time [11]  where w < 2.376 is the exponent of matrix multiplication. The main contribution of this paper is a collection of new bounds on the complexity of finding simple cycles of length exactly k, where k > 3 is a fixed integer, in a directed or an undirected graph G = (V, E). These bounds are of the form O (E ~k ) or of the form O(E ~k .d(G)• where d(G) is the degeneracy of the graph (see below). The bounds improve upon previously known bounds when the graph in question is relatively sparse or relatively degenerate. We let Ck stand for a simple cycle of length k. When considering directed graphs, a Ck is assumed to be directed. We show that a Ck in a directed or undirected graph G = (V, E), if one exists, can be found in O(E 2-2/k) time, if k is even, and in O(E 2-2/(k+1)) time, if k is odd. For finding triangles (C3's), we get the slightly better bound of O(E 2~176 = O(EI41), where w < 2.376 is the exponent of matrix multiplication. Even cycles in undirected graphs can be found even faster. A C4k-2 in an undirected graph G = (V, E), if one exists, can be found in O(E 2-(l/2k)tl+l/k)) time. A Cak, if one exists, can be found in O(E 2-(l/k-t/(2k+~))) time. In particular, we can find an undirected Ca in O(E 4/3) time and an undirected C6 in O(E 13/8) time. The degeneracy d(G) of an undirected graph G ----(V, E) is the smallest number d for which there exists an acyclic orientation of G in which all the out-degrees are at most d. The degeneracy d(G) of a graph G is linearly related to the arboricity a(G) of the graph, i.e., a(G) = (-)(d(G)), where a(G) is the minimal number of forests needed I
Alon, Yuster and Zwick REF showed how to detect a triangle in O(e 2ω/(ω+1) ) time.
Finding and counting given length cycles
Algorithmica
Algorithmica
Computer Science Mathematics