New Algorithms for Girth and Cycle Detection

Let $G=(V,E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. A set of vertices $C_{\mathrm{\ell }}=\{v_1,v_2,\mathrm{\cdots },v_{\mathrm{\ell }+1}\}$ in $G$, where $\mathrm{\ell }\ge 2$, is a cycle of length $\mathrm{\ell }$ if $v_1=v_{\mathrm{\ell }+1}$ and $(v_i,v_{i+1})\in E$, for every $1\le i\le \mathrm{\ell }$. A $C_{\le \mathrm{\ell }}$ is a cycle of length at most $\mathrm{\ell }$. The girth $g$ of $G$ is the length of a shortest cycle in $G$. The girth of a graph has been studied extensively since the 1970s by researchers from both the graph theory and the algorithms communities.

Itai and Rodeh [6] showed that the girth can be computed in $O(mn)$ time or in $O(n^{\omega })$ time, where [16], if Fast Matrix Multiplication (FMM) algorithms are used. They also proved that the problem of computing the girth is equivalent to the problem of deciding whether there is a $C_3$ (triangle) in a graph or not.

In practice, algorithms for FMM have very large constant factors in their running time. Combinatorial algorithms, informally, are algorithms which do not use algebraic methods that are being used by FMM algorithms, and consequently are often more practical. Vassilevska W. and Williams [15] showed that if there exists a truly subcubic time combinatorial algorithm which detects if a graph has a triangle (and therefore also a subcubic time algorithm that computes the exact girth), then there exists a truly subcubic time combinatorial algorithm for Boolean Matrix Multiplication (BMM) (and therefore also for unweighted All Pairs Shortest Path (APSP), see [5], [13], [14]). Such an algorithm would be a major breakthrough. As a result, to get a faster running time for computing the girth, it is natural to settle for an approximation algorithm for the girth instead of an exact computation. An $(\alpha ,\beta )$-approximation $\widehat{g}$ of $g$ (where $\alpha \ge 1$ and $\beta \ge 0$), satisfies $g\le \widehat{g}\le \alpha \cdot g+\beta$. We denote an approximation as an $\alpha$-approximation if $\beta =0$ and as a $(+\beta )$-approximation if $\alpha =1$.

Itai and Rodeh [6] presented a $(+1)$-approximation algorithm that runs in $O(n^2)$ time. Notice that in contrast to the BMM or APSP problems, where a running time of $\mathrm{\Omega }(n^2)$ is inevitable since the output size is $\mathrm{\Omega }(n^2)$, in the girth problem the output is a single number, thus, there is no natural barrier for subquadratic time algorithms. Indeed, Lingas and Lundell [8] presented a $\frac{8}{3}$-approximation algorithm that runs in $\tilde{O}(n^{3/2})$ time, and Roditty and V. Williams [12] presented a $2$-approximation algorithm that runs in $\tilde{O}(n^{5/3})$ time. Dahlgaard, Knudsen and Stöckel [4] presented two tradeoffs between running time and approximation. One generalizes the algorithms of [8, 12] and computes a cycle of length at most $2\lceil \frac{g}{2}\rceil +2\lceil \frac{g}{2(\mathrm{\ell }-1)}\rceil$ in $\tilde{O}(n^{2-1/\mathrm{\ell }})$ time. The other computes, whp, a $C_{\le 2^{\mathrm{\ell }}g}$, for any integer $\mathrm{\ell }\ge 2$, in $\tilde{O}(n^{1+1/\mathrm{\ell }})$ time.

Kadria et al. [7] significantly improved upon the second algorithm of [4] and presented an algorithm, that for every integer $\mathrm{\ell }\ge 1$, computes a $C_{\le 2\mathrm{\ell }\lceil g/2\rceil }$ in $\tilde{O}(n^{1+1/\mathrm{\ell }})$ time. They also presented an algorithm, that for every $\epsilon \in (0,1)$, computes a cycle of length at most $4\lceil \frac{g}{2}\rceil -2\lfloor \epsilon \lceil \frac{g}{2}\rceil \rfloor \le (2-\epsilon )g+4$, in $\tilde{O}(n^{1+1/(2-\epsilon )})$ time, for every graph with $g=\mathrm{polylog}(n)$.

These two algorithms of Kadria et al., as well as few other approximation algorithms (see for example, [8], [2], [9]), were obtained using a general framework for girth approximation in which a search is performed over the range of possible values of $g$, using some algorithm $𝒜$ that gets as an input an integer $\tilde{g}$ which is a guess for the value of $g$. In each step of the search $𝒜$ either returns a cycle $C_{\le f(\tilde{g})}$, where $f$ is a non decreasing function, or determines that $g>\tilde{g}$. The goal of the search is to find the smallest $\tilde{g}$, for which $𝒜$ returns a cycle, because for this value we have $g>\tilde{g}-1$ (and thus $g\ge \tilde{g}$), and algorithm $𝒜$ returns a $C_{\le f(\tilde{g})}$. This cycle is of length at most $f(g)$ since $g\ge \tilde{g}$ and $f$ is a non decreasing function ($f$ can represent the approximation, for example $f(\tilde{g})=2\tilde{g}$ yields a $2$-approximation). The two possible outcomes of $𝒜$ and its usage in the general girth approximation framework inspired us to formally define the notion of a $(\gamma ,\delta )$-hybrid algorithm as follows:

When $\gamma =\delta$, the algorithm is referred to as a $\gamma$-hybrid algorithm. The girth approximation framework described above suggests that a possible approach for developing efficient girth approximation algorithms is by developing efficient $(\gamma ,\delta )$-hybrid algorithms.

Kadria et al. [7] designed several algorithms that satisfy the definition of $(\gamma ,\delta )$-hybrid algorithms. Their girth approximation algorithms mentioned above were obtained using two different $(f(\tilde{g}),\tilde{g})$-hybrid algorithms. Additionally, for every integer $k\ge 2$, they presented a $(2k,3)$-hybrid and a $(2k,4)$-hybrid algorithms that run in $O(\min \{m^{1+1/(k+1)},n^{1+2/k}\})$ time, and a $(\max \{2k,g\},5)$-hybrid algorithm that runs in $O(\min \{m^{1+2/(k+1)},n^{1+3/k}\})$ time. Therefore, for $k\ge 2$, $\tilde{g}\in \{3,4,5\}$ and $\alpha =\lceil \frac{\tilde{g}}{2}\rceil$, there is a $(\max \{2k,g\},\tilde{g})$-hybrid algorithm that runs in $O(\min \{m^{1+\frac{\alpha -1}{k+1}},n^{1+\frac{\alpha }{k}}\})$ time. A natural question is whether these three algorithms are only part of a general tradeoff between the running time, $\gamma$ and $\delta$.

In this paper we present a $(\max \{2k,g\},\tilde{g})$-hybrid algorithm that runs, whp, in $\tilde{O}((\frac{k+1}{\alpha -1}+\alpha )\cdot \min \{m^{1+\frac{\alpha -1}{k+1}},n^{1+\frac{\alpha }{k}}\})$ time, for every $\tilde{g}\ge 3$. This algorithm provides an affirmative answer to Problem 1.1, albeit the $(\frac{k+1}{\alpha -1}+\alpha )$ factor in the running time.

Kadria et al. [7] presented also a $(2k,6)$-hybrid algorithm whose running time is $\tilde{O}(\min \{n{m}^{\frac{1}{2}+\frac{1}{2(k+1)}},n^{\frac{3}{2}+\frac{1}{k}}\})$, for every integer $k\ge 4$. The running time of our algorithm when $\tilde{g}=6$ is $\tilde{O}(k\cdot \min \{m^{1+\frac{2}{k+1}},n^{1+\frac{3}{k}}\})$. We improve the running time for every constant $k\ge 5$, in the case of (when $m\ge O(n^{1+1/k})$ the two algorithms run a similar procedure and thus have the same asymptotic running time).

Using our $(\max \{2k,g\},\tilde{g})$-hybrid algorithm we obtain a generalization of the $\tilde{O}(n^{1+1/(2-\epsilon )})$ time algorithm of Kadria et al. [7] that computes a cycle of length at most $4\lceil \frac{g}{2}\rceil -2\lfloor \epsilon \lceil \frac{g}{2}\rceil \rfloor \le (2-\epsilon )g+4$, for every graph with $g=\mathrm{polylog}(n)$. Our generalized algorithm runs in $\tilde{O}(\mathrm{\ell }\cdot n^{1+1/(\mathrm{\ell }-\epsilon )})$ time, whp, and returns a cycle of length at most $2\mathrm{\ell }\lceil \frac{g}{2}\rceil -2\lfloor \epsilon \lceil \frac{g}{2}\rceil \rfloor \le (\mathrm{\ell }-\epsilon )g+\mathrm{\ell }+2$, where $\mathrm{\ell }\ge 2$ is an integer and $\epsilon \in [0,1]$, for every graph with $g=\mathrm{polylog}(n)$. We also show that if the graph is sparse then the approximation can be improved. More specifically, we present an algorithm that runs in $\tilde{O}(\mathrm{\ell }\cdot m^{1+1/(\mathrm{\ell }-\epsilon )})$ time, whp, and returns a cycle of length at most $(\mathrm{\ell }-\epsilon )g-\mathrm{\ell }+2\epsilon$, where $\mathrm{\ell }\ge 3$ is an integer and $\epsilon \in [0,1)$, for every graph with $g=\mathrm{polylog}(n)$.

Our $\tilde{O}(\mathrm{\ell }\cdot n^{1+1/(\mathrm{\ell }-\epsilon )})$-time algorithm also generalizes the $\tilde{O}(n^{1+1/\mathrm{\ell }})$-time algorithm of Kadria et al. [7], which computes a $C_{\le 2\mathrm{\ell }\lceil g/2\rceil }$ for every integer $\mathrm{\ell }\ge 1$. In our algorithm, the integer parameter $\mathrm{\ell }$ that appears in the exponent of the running time is replaced by a real-valued parameter $\mathrm{\ell }-\epsilon$. Thus, we introduce many new points on the tradeoff curve between running time and approximation ratio. Specifically, for every integer $\mathrm{\ell }\le \mathrm{polylog}(n)$, up to $\lceil g/2\rceil -1$ additional tradeoff points are added.¹¹1Up to $\lceil g/2\rceil -1$ tradeoff points are added since for every such $\mathrm{\ell }$, when $\epsilon$ is a multiple of $\frac{1}{\lceil g/2\rceil }$, we get an $\tilde{O}(n^{1+1/(\mathrm{\ell }-\epsilon )})$-time algorithm which computes a $C_{\le 2(\mathrm{\ell }-\epsilon )\lceil g/2\rceil }$. For example, consider $\mathrm{\ell }=3$ and a graph with girth $g=5$ or $g=6$. Our algorithm yields two additional points on the tradeoff curve, corresponding to $\epsilon =\frac{1}{3}$ and $\epsilon =\frac{2}{3}$. For $\epsilon =\frac{1}{3}$, we compute a $C_{\le 16}$ in $\tilde{O}(n^{1+\frac{3}{8}})$ time, and for $\epsilon =\frac{2}{3}$, we compute a $C_{\le 14}$ in $\tilde{O}(n^{1+\frac{3}{7}})$ time. These points lie between the two points on the tradeoff curve given by the algorithm of Kadria et al. [7], which computes either a $C_{\le 12}$ in $\tilde{O}(n^{1+\frac{3}{6}})$ time or a $C_{\le 18}$ in $\tilde{O}(n^{1+\frac{3}{9}})$ time. See Figure 1 for a comparison.

Together, the tradeoffs in the two algorithms of Kadria et al. [7] that we generalize encompass several other known results, including those of Itai and Rodeh [6], Lingas and Lundell [8], Roditty and V. Williams [12] and the first tradeoff of Dahlgaard et al. [4] (when $g=\mathrm{polylog}(n)$). Notably, some of these algorithms have resisted improvement for many years. Therefore, the unification of these algorithms within a single tradeoff curve in our result, together with the addition of new valid points on this curve, reinforces the possibility that it captures a fundamental relationship between running time and approximation quality. This, in turn, motivates further investigation into whether a matching lower bound exists for this tradeoff.

The rest of this paper is organized as follows. In Section 2 we provide an overview. Preliminaries are in Section 3. In Section 4, we present a new cycle searching technique that is used by our algorithms. In Section 5 we present a $2k$-hybrid algorithm and then use it to obtain a $(+1)$-approximation algorithm for the girth. In Section 6 we generalize the $2k$-hybrid algorithm and present a $(\max \{2k,g\},\tilde{g})$-hybrid algorithm. In Section 7 we use the hybrid algorithm from Section 6 to obtain two more approximation algorithms for the girth.

Among the techniques that we develop to obtain our new algorithms, is a new cycle searching technique that might be of independent interest. Our new technique exploits the property that if $s\in V$ is not on a $C_{\le 2k}$, then for any two neighbors $x$ and $y$ of $s$, the set of vertices at distance exactly $k-1$ from $x$ and $y$ that are also at distance $k$ from $s$ are disjoint (see Figure 2). This allows us to check efficiently for all the neighbors of $s$ if they are on a $C_{\le 2k}$. Using this technique, together with more tools that we develop, we obtain two hybrid algorithms.

The first is a relatively simple $O(m^{1+\frac{k-1}{k+1}})$-time, $2k$-hybrid algorithm. We use this hybrid algorithm in the girth approximation framework described earlier, to obtain an $\tilde{O}(m^{1+\frac{\mathrm{\ell }-1}{\mathrm{\ell }+1}})$-time, $(+1)$-approximation of the girth, where $g=2\mathrm{\ell }$ or $g=2\mathrm{\ell }-1$ (the running time can also be written as $\tilde{O}(m^{2-\frac{2}{\lceil g/2\rceil +1}})$). We remark that using an algorithm of [3] for $C_{2k}$ detection, it is possible to obtain a $(+1)$-approximation in $\tilde{O}({\mathrm{\ell }}^{O(\mathrm{\ell })}\cdot m^{1+\frac{\mathrm{\ell }-1}{\mathrm{\ell }+1}})$ time (see Section 5.2 for more details). However, the additional ${\mathrm{\ell }}^{O(\mathrm{\ell })}$ factor might be significant even for small values of $\mathrm{\ell }$.

The second is the $(\max \{2k,g\},\tilde{g})$-hybrid algorithm that solves Problem 1.1. Its main component is an $(2k,2\alpha )$-hybrid algorithm that runs in $\tilde{O}((\frac{k+1}{\alpha -1}+\alpha )\cdot m^{1+\frac{\alpha -1}{k+1}})$-time, whp, and generalizes the first $O(m^{1+\frac{k-1}{k+1}})$-time $2k$-hybrid algorithm, by introducing an additional parameter $\alpha \le k$. Using $\alpha$ we can tradeoff between the running time and the lower bound on $g$ and obtain a faster running time at the price of a worse lower bound.

We compare our $(2k,2\alpha )$-hybrid algorithm to algorithm Cycle of Kadria et al. [7], an $O(m+n^{1+\frac{1}{\mathrm{\ell }}})$-time,²²2Cycle runs in $O(n^{1+\frac{1}{\mathrm{\ell }}}+m)$ time, which can be reduced to $O(n^{1+\frac{1}{\mathrm{\ell }}})$ time, as shown in [7]. $(2\mathrm{\ell }\alpha ,\tilde{g})$-hybrid algorithm, where $\alpha =\lceil \tilde{g}/2\rceil$, that they used to obtain the $\tilde{O}(n^{1+\frac{1}{\mathrm{\ell }}})$-time, $2\mathrm{\ell }\lceil g/2\rceil$-approximation algorithm. As we show later, the running time of our $(2k,2\alpha )$-hybrid algorithm can be bounded by $\tilde{O}((\frac{k+1}{\alpha -1}+\alpha )\cdot n^{1+\frac{\alpha }{k}})$. Since in our algorithm $k$ is not necessarily a multiple of $\alpha$ (compared to the $\mathrm{\ell }\alpha$ of Cycle), our algorithm allows more flexibility, and we achieve many more possible tradeoffs between the running time and the output cycle length. For example, if we consider a multiplicative approximation better than $3$, when the value of $g$ is a constant known in advance, our algorithm can return longer cycles that are still shorter than $3g$, in a faster running time.³³3[7] presented also an $O((\alpha -c)\cdot n^{1+\frac{\alpha }{2\alpha -c}})$-time, $(4\alpha -2c,2\alpha )$-hybrid algorithm, where are integers. For $c=2\alpha -k$, this is an $O((k-\alpha )\cdot n^{1+\frac{\alpha }{k}})$-time, $(2k,2\alpha )$-hybrid algorithm, similar to our $(2k,2\alpha )$-hybrid algorithm. However, since , the possible values of $k$ are restricted and must satisfy . By choosing $\alpha =\lceil \frac{g}{2}\rceil$ and an appropriate $k$ the two algorithms have a similar flexibility for a $2$-approximation, but since in our algorithm also larger values of $k$ are allowed, we can achieve a faster running time for a $t$-approximation where $t>2$.

The flexibility of our algorithm is also demonstrated as follows. For a given constant value of $k$, if our $(2k,2\alpha )$-hybrid algorithm returns a cycle then its length is at most $2k$. If we want algorithm Cycle to output a $C_{\le 2k}$, then $\lfloor \frac{k}{\alpha }\rfloor$ is the largest $\mathrm{\ell }$ that we can choose, since $\mathrm{\ell }$ must be an integer. The running time is $O(n^{1+1/\mathrm{\ell }})=O(n^{1+1/\lfloor \frac{k}{\alpha }\rfloor })$. Our algorithm achieves a better running time if $k$ is not divisible by $\alpha$. (See the relevant figures in the full version of this paper [10] for a comparison).

Next, we overview our $(2k,2\alpha )$-hybrid algorithm that either finds a $C_{\le 2k}$ or determines that $g>2\alpha$ in $\tilde{O}((\frac{k+1}{\alpha -1}+\alpha )\cdot m^{1+\frac{\alpha -1}{k+1}})$ time. In order to determine that $g\ge 2\alpha$, we can check for every $v\in V$ if $v$ is on a $C_{\le 2\alpha }$ (and either find a $C_{\le 2k}$ since $\alpha \le k$, or return that $g>2\alpha$). If $v$ is on a $C_{\le 2\alpha }$, then all the vertices and edges of this $C_{\le 2\alpha }$ are at distance at most $\alpha$ from $v$. If, for every $v\in V$, the number of edges at distance at most $\alpha$ is $O(deg(v)\cdot m^{\frac{\alpha -1}{k+1}})$ then using standard techniques we can check for every $v\in V$ if $v$ is on a $C_{\le 2\alpha }$ in $O(m^{1+\frac{\alpha -1}{k+1}})$ time. However, this is not necessarily the case, and the region at distance at most $\alpha$ from some vertices might be dense. To deal with dense regions within the promised running time we develop an iterative sampling procedure (see BfsSample in Section 6), whose goal is to sparsify the graph, or to return a $C_{\le 2k}$. One component of the iterative sampling procedure is a generalization of our new cycle searching technique mentioned above. In the generalization instead of checking whether a vertex $s$ and its neighbors are on a $C_{\le 2k}$, we check whether all the vertices up to a possibly further distance from $s$ are on a $C_{\le 2\alpha }$, for $\alpha \le k$, and if not we mark them so that they can be removed later.

If the iterative sampling procedure ends without finding a $C_{\le 2k}$ then there are two possibilities. Let $r=(k+1)mod(\alpha -1)$. If $r=0$ then it holds that the number of edges at distance at most $\alpha$ from every $v\in V$ is $O(deg(v)\cdot m^{\frac{\alpha -1}{k+1}})$, whp, as required. If $r>0$ then it holds that the number of edges at distance at most $r$ from every $v\in V$ is $O(m^{\frac{r}{k+1}})$, whp. This does not necessarily imply that the graph is sparse enough for checking whether $g>2\alpha$. In this case, we run another algorithm (see HandleRemainder in Section 6) that continues to sparsify the graph until the number of edges at distance at most $\alpha$ from every $v\in V$ is $O(deg(v)\cdot m^{\frac{\alpha -1}{k+1}})$ and checking whether $g>2\alpha$ is possible within the required running time of $O(m^{1+\frac{\alpha -1}{k+1}})$.

Let $G=(V,E)$ be an unweighted undirected graph with $n$ vertices and $m$ edges. Let $U\subseteq V$ be a set of vertices and let $G\setminus U$ be the graph obtained from $G$ by deleting all the vertices of $U$ together with their incident edges. For two graphs $G=(V,E)$ and $G^{\prime }=(V^{\prime },E^{\prime })$, let $G\setminus G^{\prime }$ be $G\setminus V^{\prime }$. We say that $G\subseteq G^{\prime }$ if $V\subseteq V^{\prime }$ and $E\subseteq E^{\prime }$. For convenience, we use both $u\in V$ and $u\in G$ to say that $u\in V$. For every $u,v\in V$, let $d_G(u,v)$ be the length of a shortest path between $u$ and $v$ in $G$. The girth $g$ of $G$ is the length of a shortest cycle in $G$. Let $wt(C)$ be the length of a cycle $C$. For an integer $\mathrm{\ell }$, we denote a cycle of length (at most) $\mathrm{\ell }$ by ($C_{\le \mathrm{\ell }}$) $C_{\mathrm{\ell }}$.⁴⁴4Both $C_{\mathrm{\ell }}$ and $C_{\le \mathrm{\ell }}$ might not be simple cycles. However, the cycles that our algorithms return are simple. Let $E(v)$ be the edges incident to $v$ and $E(v,i)$ the $i$th edge in $E(v)$. Let $de{g}_G(v)$ be the degree of $v$ in $G$. Let $N(v)$ be the set of neighbors of $v$, namely $N(v)=\{w\mid (v,w)\in E\}$. For an edge set $S$, let $V(S)$ be the endpoints of $S$’s edges, that is, $V(S)=\{u\in V\mid \exists (u,v)\in S\}$. Let $e=(u,v)\in E$ and $w\in V$. The distance $d_G(w,e)$ between $w$ and $e$ is $\min \{d_G(w,u),d_G(w,v)\}+1$. For every $u\in V$ and a real number $k$ let $B(G,u,k)=(V_u^k(G),E_u^k(G))$ be the ball graph of $u$, where $V_u^k(G)=\{v\in V\mid d_G(u,v)\le k\}$ and $E_u^k(G)=\{e\in E\mid d_G(u,e)\le k\}$ [7]. For an integer $\mathrm{\ell }\ge 0$ and a vertex $u\in V$, Let $L_u^{\mathrm{\ell }}(G)=\{w\mid d_G(u,w)=\mathrm{\ell }\}$.⁵⁵5When the graph is clear from the context, we sometimes omit $G$ from the notations.

We now turn to present several essential tools that are required in order to obtain our new algorithms. We first restate an important property of the ball graph $B(v,R)$.

We use procedure $\text{BallOrCycle}(G,v,R)$ [7, 8] (pseudo-code in [10]) that searches for a $C_{\le 2R}$ in the ball graph $B(v,R)$. We summarize BallOrCycle’s properties in the next lemma.

Next, we obtain a simple $t$-hybrid algorithm, called AllVtxBallOrCycle, using BallOrCycle. AllVtxBallOrCycle (pseudo-code in [10]) gets a graph $G$ and an integer $t\ge 2$, and runs $\text{BallOrCycle}(v,t)$ from every $v\in G$ as long as no cycle is found by BallOrCycle. If BallOrCycle finds a cycle then AllVtxBallOrCycle stops and returns that cycle. If no cycle is found then AllVtxBallOrCycle returns null. We prove the next lemma in the full version of this paper [10].

We now show that if the input graph satisfies a certain sparsity property then the running time of $\text{AllVtxBallOrCycle}(G,t)$ can be bounded as follows.

In this section we introduce a new cycle searching technique implemented in algorithm NbrBallOrCycle. This technique exploits the property that a vertex $s\in V$ is not on a $C_{\le 2k}$, to check efficiently whether any neighbor of $s$ lies on a $C_{\le 2k}$.

Consider a vertex $s\in V$. It is straightforward to check whether $s$ is on a $C_{\le 2k}$, for every integer $k$, using $\text{BallOrCycle}(G,s,k)$ in $O(n)$ time. If $\text{BallOrCycle}(G,s,k)$ does not return a $C_{\le 2k}$ then for every $x,y\in N(s)$ it holds that $V_x^{k-1}(G^{\prime })\cap V_y^{k-1}(G^{\prime })=\mathrm{\varnothing }$, where $G^{\prime }=G\setminus \{s\}$, as otherwise there was a $C_{\le 2k}$ passing through $s$ and $\text{BallOrCycle}(G,s,k)$ would have returned a $C_{\le 2k}$ (see Figure 2). We show that it is possible to exploit this property to check for every $v\in N(s)$ whether $v$ is on a $C_{\le 2k}$, using $\text{BallOrCycle}(G^{\prime },v,k)$, in $O(n+m)$ time instead of $O(deg(s)\cdot n)$. More specifically, we present algorithm $\text{NbrBallOrCycle}(G,s,k)$ (see Algorithm 2) that gets a graph $G$, a vertex $s$, and an integer $k\ge 2$. We first initialize $\widehat{U}$ to $\mathrm{\varnothing }$. Then, we run $\text{BallOrCycle}(G,s,k)$. If a cycle $C$ is found by $\text{BallOrCycle}(G,s,k)$ then $C$ is returned by NbrBallOrCycle. Otherwise, we add the vertex $s$ to $\widehat{U}$, keep the neighbors of $s$ in $N_s$, and then remove $s$ from $G$. Recall that $G^{\prime }$ equals $G\setminus \{s\}$. Next, for every $v\in N_s$ we run $\text{BallOrCycle}(G^{\prime },v,k)$, as long as a cycle is not found. If a cycle $C$ is returned by $\text{BallOrCycle}(G^{\prime },v,k)$ then $C$ is returned by NbrBallOrCycle.⁷⁷7For our needs it suffices to stop and return a cycle passing through an $s$ neighbor once we find one, though BallOrCycle can be run from all the neighbors of $s$ in the same running time bound of $O(n+m)$. Otherwise, $v$ is added to $\widehat{U}$. After the loop ends, the vertex $s$ and its adjacent edges are added back to the graph, and the set $\widehat{U}$ is returned by NbrBallOrCycle. We prove the following lemma in the full version of this paper [10].

To bound the running time of NbrBallOrCycle, we show how to use the fact that no $C_{\le 2k}$ was found by $\text{BallOrCycle}(G,s,k)$, to efficiently run $\text{BallOrCycle}(G^{\prime },v,k)$ for every $v\in N_s$.

In this section we first show how to use algorithm NbrBallOrCycle from the previous section to obtain a $2k$-hybrid algorithm that in $O(m^{1+\frac{k-1}{k+1}})$ time, either returns a $C_{\le 2k}$ or determines that $g>2k$. Then, we use the $2k$-hybrid algorithm to compute a $(+1)$-approximation of $g$.