Finding even cycles faster via capped k-walks

DOI10.1145/3055399.3055459zbMATH Open1369.05192DBLPconf/stoc/DahlgaardKS17arXiv1703.10380OpenAlexW2604969355WikidataQ61971574 ScholiaQ61971574MaRDI QIDQ4977965FDOQ4977965

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)

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.

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

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

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)

Cited In (5)

• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Title not available (Why is that?)
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Removing additive structure in 3SUM-based reductions

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)