English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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$k\ge2$. A classic result by Bondy and Simonovits [J.Comb.Th.'74] implies thatif $m \ge100k n^{1+1/k}$, then $G$ contains a $C_{2k}$, further implying thatone 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 Yusterand Zwick [J.Disc.Math'97] as well as a $O(m^{2-(1+\lceilk/2\rceil^{-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$ ourbound yields a polynomial improvement in $m$.  Yuster and Zwick noted that it is "plausible to conjecture that $O(n^2)$ isthe best possible bound in terms of $n$". We show "conditional optimality": ifthis hypothesis holds then our $O(m^{2k/(k+1)})$ algorithm is tight as well.Furthermore, a folklore reduction implies that no combinatorial algorithm candetermine 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. Coupledwith our main result, this gives tight bounds for finding $6$-cyclescombinatorially and also separates the complexity of finding $4$- and$6$-cycles giving evidence that the exponent of $m$ in the running time shouldindeed 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 fixedordering. Our main technical contribution is an involved analysis provingseveral properties of such walks which may be of independent interest.

Finding Even Cycles Faster via Capped k-Walks