2017/03/30 by Dahlgaard, Søren, Knudsen, Mathias Bæk Tejs, Stöckel, Morten · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1703.10380
In this paper, we consider the problem of finding a cycle of length 2k (a C2k) in an undirected graph G with n nodes and m edges for constant k≥2. A classic result by Bondy and Simonovits [J.Comb.Th.'74] implies that if m ≥100k n1+1/k, then G contains a C2k, further implying that one needs to consider only graphs with m = O(n1+1/k). Previously the best known algorithms were an O(n2) algorithm due to Yuster and Zwick [J.Disc.Math'97] as well as a O(m^2-(1+\lceil k/2\rceil-1)/(k+1)) algorithm by Alon et al. [Algorithmica'97]. We present an algorithm that uses O(m2k/(k+1)) time and finds a C2k if one exists. This bound is O(n2) exactly when m=Θ(n1+1/k). For 4-cycles our new bound coincides with Alon et al., while for every k>2 our bound yields a polynomial improvement in m. Yuster and Zwick noted that it is "plausible to conjecture that O(n2) is the best possible bound in terms of n". We show "conditional optimality": if this hypothesis holds then our O(m2k/(k+1)) algorithm is tight as well. Furthermore, a folklore reduction implies that no combinatorial algorithm can determine if a graph contains a 6-cycle in time O(m3/2-ε) for any ε>0 under the widely believed combinatorial BMM conjecture. Coupled with our main result, this gives tight bounds for finding 6-cycles combinatorially and also separates the complexity of finding 4- and 6-cycles giving evidence that the exponent of m in the running time should indeed increase with k. The key ingredient in our algorithm is a new notion of capped k-walks, which are walks of length k that visit only nodes according to a fixed ordering. Our main technical contribution is an involved analysis proving several properties of such walks which may be of independent interest.