Finding even cycles faster via capped k-walks

DOI10.1145/3055399.3055459MaRDI QIDQ4977965zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.10380

zbMATH Keywords

graph algorithmscyclesparameterized algorithmsconditional lower boundsgraph walkscapped walks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Abstract: In this paper, we consider the problem of finding a cycle of length $2k$ (a $C_{2k}$) in an undirected graph $G$ with $n$ nodes and $m$ edges for constant $kge2$. A classic result by Bondy and Simonovits [J.Comb.Th.'74] implies that if $mge100k{n}^{1+1/k}$, then $G$ contains a $C_{2k}$, further implying that one needs to consider only graphs with $m=O(n^{1+1/k})$. Previously the best known algorithms were an $O(n^2)$ algorithm due to Yuster and Zwick [J.Disc.Math'97] as well as a $O(m^{2-(1+lceilk/2cei{l}^{-1})/(k+1)})$ algorithm by Alon et al. [Algorithmica'97]. We present an algorithm that uses $O(m^{2k/(k+1)})$ time and finds a $C_{2k}$ if one exists. This bound is $O(n^2)$ exactly when $m=Theta(n^{1+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(n^2)$ is the best possible bound in terms of $n$". We show "conditional optimality": if this hypothesis holds then our $O(m^{2k/(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(m^{3/2-epsilon})$ for any $epsilon>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.

Recommendations

• Finding even cycles even faster
• Finding Even Cycles Even Faster
• Finding cycles and trees in sublinear time
• An efficient approximation algorithm for counting \(n\)-cycles in a graph
• scientific article; zbMATH DE number 1215999
• Finding short cycles in embedded graph in polynomial time
• Finding \(k\) simple shortest paths and cycles
• Searching for a cycle with maximum coverage in undirected graphs
• A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering
• Shortest enclosing walks and cycles in embedded graphs

Cited in

(5)

• Removing additive structure in 3SUM-based reductions
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles

This page was built for publication: Finding even cycles faster via capped k-walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977965)