New algorithms for girth and cycle detection

Abstract

Let $G=(V,E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Let $g$ be the girth of $G$, that is, the length of a shortest cycle in $G$. We present a randomized algorithm with a running time of $\tilde{O}(\ell \cdot n^{1+\frac{1}{\ell -\epsilon }})$ that returns a cycle of length at most $2\ell \lceil \frac{g}{2}\rceil -2\lfloor \epsilon \lceil \frac{g}{2}\rceil \rfloor ,$ where $\ell \ge 2$ is an integer and $\epsilon \in [0,1]$, for every graph with $g=polylog(n)$. Our algorithm generalizes an algorithm of Kadria \etal{} [SODA'22] that computes a cycle of length at most $4\lceil \frac{g}{2}\rceil -2\lfloor \epsilon \lceil \frac{g}{2}\rceil \rfloor$ in $\tilde{O}\left(n^{1+\frac{1}{2-\epsilon }}\right)$ time. Kadria \etal{} presented also an algorithm that finds a cycle of length at most $2\ell \lceil \frac{g}{2}\rceil$ in $\tilde{O}\left(n^{1+\frac{1}{\ell }}\right)$ time, where $\ell$ must be an integer. Our algorithm generalizes this algorithm, as well, by replacing the integer parameter $\ell$ in the running time exponent with a real-valued parameter $\ell -\epsilon$, thereby offering greater flexibility in parameter selection and enabling a broader spectrum of combinations between running times and cycle lengths. We also show that for sparse graphs a better tradeoff is possible, by presenting an $\tilde{O}(\ell \cdot m^{1+1/(\ell -\epsilon )})$ time randomized algorithm that returns a cycle of length at most $2\ell (\lfloor \frac{g-1}{2}\rfloor )-2(\lfloor \epsilon \lfloor \frac{g-1}{2}\rfloor \rfloor +1)$, where $\ell \ge 3$ is an integer and $\epsilon \in [0,1)$, for every graph with $g=polylog(n)$. To obtain our algorithms we develop several techniques and introduce a formal definition of hybrid cycle detection algorithms. [...]