1 Introduction↩︎

Let \(G=(V,E)\) be an unweighted undirected graph with \(n\) vertices and \(m\) edges. A set of vertices \(C_\ell=\{ v_1,v_2,\cdots,v_{\ell+1}\}\) in \(G\), where \(\ell \geq 2\), is a cycle of length \(\ell\) if \(v_1=v_{\ell+1}\) and \((v_i,v_{i+1})\in E\), for every \(1\leq i \leq \ell\). A \(C_{\leq \ell}\) is a cycle of length at most \(\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 [1] showed that the girth can be computed in \(O(mn)\) time or in \(O(n^\omega)\) time, where \(\omega< 2.371552\) [2], 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 [3] 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 [4], [5], [6]). 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 \(\hat{g}\) of \(g\) (where \(\alpha \geq 1\) and \(\beta \geq 0\)), satisfies \(g\leq \hat{g} \leq \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 [1] 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 \(\Omega(n^2)\) is inevitable since the output size is \(\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 [7] presented a \(\frac{8}{3}\)-approximation algorithm that runs in \(\tilde{O}(n^{3/2})\) time, and Roditty and V. Williams [8] presented a \(2\)-approximation algorithm that runs in \(\tilde{O}(n^{5/3})\) time. Dahlgaard, Knudsen and Stöckel [9] presented two tradeoffs between running time and approximation. One generalizes the algorithms of [7], [8] and computes a cycle of length at most \(2\lceil \frac{g}{2}\rceil+2\lceil \frac{g}{2(\ell-1)}\rceil\) in \(\tilde{O}(n^{2-1/\ell})\) time. The other computes, whp, a \(C_{\leq 2^\ell g}\), for any integer \(\ell\geq 2\), in \(\tilde{O}(n^{1+1/\ell})\) time.

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

These two algorithms of Kadria et al., as well as few other approximation algorithms (see for example, [7], [11], [12]), 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 \(\mathcal{A}\) that gets as an input an integer \(\tilde{g}\) which is a guess for the value of \(g\). In each step of the search \(\mathcal{A}\) either returns a cycle \(C_{\leq 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 \(\mathcal{A}\) returns a cycle, because for this value we have \(g> \tilde{g}-1\) (and thus \(g\geq \tilde{g}\)), and algorithm \(\mathcal{A}\) returns a \(C_{\leq f(\tilde{g})}\). This cycle is of length at most \(f(g)\) since \(g\geq \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 \(\mathcal{A}\) 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. [10] 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\geq 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\geq 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}\geq 3\). This algorithm provides an affirmative answer to Problem 1, albeit the \((\frac{k+1}{\alpha-1}+\alpha)\) factor in the running time.

Kadria et al. [10] 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\geq 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\geq5\), in the case of \(m < O(n^{1+1/k})\) (when \(m \geq 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 \(\widetilde{O}(n^{1+1/(2-\varepsilon)})\) time algorithm of Kadria et al. [10] that computes a cycle of length at most \(4\lceil \frac{g}{2}\rceil - 2\lfloor \varepsilon \lceil \frac{g}{2}\rceil \rfloor \leq (2-\varepsilon)g+4\), for every graph with \(g={\rm polylog}(n)\). Our generalized algorithm runs in \(\tilde{O}(\ell\cdot n^{1+1/(\ell-\varepsilon)})\) time, whp, and returns a cycle of length at most \(2\ell\lceil \frac{g}{2}\rceil - 2\lfloor \varepsilon \lceil \frac{g}{2}\rceil \rfloor \leq (\ell-\varepsilon)g+\ell+2\), where \(\ell\geq 2\) is an integer and \(\varepsilon\in [0,1]\), for every graph with \(g={\rm 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}(\ell\cdot m^{1+1/(\ell-\varepsilon)})\) time, whp, and returns a cycle of length at most \((\ell-\varepsilon)g-\ell+2\varepsilon\), where \(\ell\geq 3\) is an integer and \(\varepsilon\in [0,1)\), for every graph with \(g={\rm polylog}(n)\).

Our \(\tilde{O}(\ell\cdot n^{1+1/(\ell- \varepsilon)})\)-time algorithm also generalizes the \(\tilde{O}(n^{1+1/\ell})\)-time algorithm of Kadria et al. [10], which computes a \(C_{\leq 2\ell \lceil g/2\rceil}\) for every integer \(\ell \geq 1\). In our algorithm, the integer parameter \(\ell\) that appears in the exponent of the running time is replaced by a real-valued parameter \(\ell- \varepsilon\). Thus, we introduce many new points on the tradeoff curve between running time and approximation ratio. Specifically, for every integer \(\ell \leq {\rm polylog}(n)\), up to \(\lceil g / 2 \rceil - 1\) additional tradeoff points are added.⁴ For example, consider \(\ell = 3\) and a graph with girth \(g = 5\) or \(g = 6\). Our algorithm yields two additional points on the tradeoff curve, corresponding to \(\varepsilon = \frac{1}{3}\) and \(\varepsilon = \frac{2}{3}\). For \(\varepsilon = \frac{1}{3}\), we compute a \(C_{\leq 16}\) in \(\tilde{O}(n^{1 + \frac{3}{8}})\) time, and for \(\varepsilon = \frac{2}{3}\), we compute a \(C_{\leq 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. [10], which computes either a \(C_{\leq 12}\) in \(\tilde{O}(n^{1 + \frac{3}{6}})\) time or a \(C_{\leq 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. [10] that we generalize encompass several other known results, including those of Itai and Rodeh [1], Lingas and Lundell [7], Roditty and V. Williams [8] and the first tradeoff of Dahlgaard et al. [9] (when \(g={\rm 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.

2 Overview↩︎

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_{\leq 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_{\leq 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{\ell -1}{\ell+1}})\)-time, \((+1)\)-approximation of the girth, where \(g=2\ell\) or \(g=2\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 [13] for \(C_{2k}\) detection, it is possible to obtain a \((+1)\)-approximation in \(\tilde{O}(\ell^{O(\ell)}\cdot m^{1+\frac{\ell -1}{\ell+1}})\) time (see Section 5.2 for more details). However, the additional \(\ell^{O(\ell)}\) factor might be significant even for small values of \(\ell\).

The second is the \(( \max \{2k,g\}, \tilde{g})\)-hybrid algorithm that solves Problem 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\leq 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 \(\texttt{Cycle}\) of Kadria et al. [10], an \(O(m+n^{1+\frac{1}{\ell}})\)-time,⁵ \((2\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}{\ell}})\)-time, \(2 \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 \(\ell\alpha\) of \(\texttt{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. See Figure 3 for a comparison.⁶

The flexibility of our algorithm is also demonstrated in Figure 4. 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 \(\texttt{Cycle}\) to output a \(C_{\leq 2k}\), then \(\lfloor \frac{k}{\alpha} \rfloor\) is the largest \(\ell\) that we can choose, since \(\ell\) must be an integer. The running time is \(O(n^{1+1/\ell}) = O(n^{1+1/\lfloor \frac{k}{\alpha} \rfloor})\). Our algorithm achieves a better running time if \(k\) is not divisible by \(\alpha\). (In Figure 4 we choose \(\alpha=3\).)

Next, we overview our \((2k,2\alpha)\)-hybrid algorithm that either finds a \(C_{\leq 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\geq 2\alpha\), we can check for every \(v\in V\) if \(v\) is on a \(C_{\leq 2\alpha}\) (and either find a \(C_{\leq 2k}\) since \(\alpha\leq k\), or return that \(g>2\alpha\)). If \(v\) is on a \(C_{\leq 2\alpha}\), then all the vertices and edges of this \(C_{\leq 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_{\leq 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 \(\texttt{BfsSample}\) in Section 6), whose goal is to sparsify the graph, or to return a \(C_{\leq 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_{\leq 2k}\), we check whether all the vertices up to a possibly further distance from \(s\) are on a \(C_{\leq 2\alpha}\), for \(\alpha\leq k\), and if not we mark them so that they can be removed later.

If the iterative sampling procedure ends without finding a \(C_{\leq 2k}\) then there are two possibilities. Let \(r=(k+1) \bmod (\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 \(\texttt{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}})\).

3 Preliminaries↩︎

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'=(V',E')\), let \(G \setminus G'\) be \(G\setminus V'\). We say that \(G \subseteq G'\) if \(V\subseteq V'\) and \(E \subseteq E'\). 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 \(\ell\), we denote a cycle of length (at most) \(\ell\) by (\(C_{\leq \ell}\)) \(C_\ell\).⁷ Let \(E(v)\) be the edges incident to \(v\) and \(E(v,i)\) the \(i\)th edge in \(E(v)\). Let \(deg_{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)\leq k\}\) and \(E_u^k(G)=\{e\in E \mid d_G(u,e)\leq k\}\) [10]. For an integer \(\ell \geq 0\) and a vertex \(u\in V\), Let \(L_u^\ell(G)= \{ w \mid d_{G}(u,w)=\ell\}\).⁸

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 \(\texttt{BallOrCycle}(G,v,R)\) [7], [10] (for completeness, we include a pseudo-code in Algorithm [A-BallOrCycle-modified]) that searches for a \(C_{\leq 2R}\) in the ball graph \(B(v,R)\). We summarize the properties of \(\texttt{BallOrCycle}\) in the next lemma.

Next, we obtain a simple \(t\)-hybrid algorithm, called \(\texttt{AllVtxBallOrCycle}\), using \(\texttt{BallOrCycle}\). \(\texttt{AllVtxBallOrCycle}\) (see Algorithm [A-dHybrid]) gets a graph \(G\) and an integer \(t\geq 2\), and runs \(\texttt{BallOrCycle}(v,t)\) from every \(v\in G\) as long as no cycle is found by \(\texttt{BallOrCycle}\). If \(\texttt{BallOrCycle}\) finds a cycle then \(\texttt{AllVtxBallOrCycle}\) stops and returns that cycle. If no cycle is found then \(\texttt{AllVtxBallOrCycle}\) returns \(\texttt{null}\). We prove the next lemma.

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

Next, we present procedure \(\texttt{IsDense}(G,w,T,r)\) from [10] (for completeness, we include a pseudo-code in Algorithm [A-Dense]). \(\texttt{IsDense}\) gets a graph \(G\), a vertex \(w\), a budget \(T \geq 1\) (real) and a distance \(r\geq 0\) (integer). In the procedure a BFS is executed from \(w\). The BFS counts the edges that are scanned as long as their total number is less than \(T\) and the farthest vertex from \(w\) is at distance at most \(r\).

Given a vertex \(v\) and a distance \(R\) we sometimes want to bound \(|E_{v}^{R}|\). Therefore, we adapt a lemma and a corollary of [10] from vertices to edges.

Using Lemma 5, we prove following corollary.

We also adapt procedure \(\texttt{SparseOrCycle}(G,D,x,y)\) of [10] to our needs. \(\texttt{SparseOrCycle}\) (see Algorithm [A-SparseOrCycleM]) gets a graph \(G\), a parameter \(D \geq 1\), and two integers \(x, y >0\), and iterates over vertices using a for-each loop. Let \(w\) be the vertex currently considered and \(G(w)\) the current graph. If \(\texttt{IsDense}(G(w),w,D^{x},x)=\texttt{Yes}\) then \(\texttt{BallOrCycle}(G(w),w,x-1+y)\) is called. If \(\texttt{BallOrCycle}\) returns a cycle \(C\) then \(C\) is returned by \(\texttt{SparseOrCycle}\). Otherwise, the vertex set \(V_w^{x-1}\) is removed from \(G(w)\) along with the edge set \(E_w^x\). After the loop ends, if no cycle was found, we return \(\texttt{null}\). Let \(W\subseteq V\) be the set of vertices for which \(\texttt{BallOrCycle}\) was called and no cycle was found, and \(\hat{G}=(\hat{V},\hat{E})\) the graph after \(\texttt{SparseOrCycle}\) ends.

The following lemma is similar to the corresponding lemmas from [10]. We provide here the proof for completeness.

Similarly to \(\texttt{AllVtxBallOrCycle}\), we show for \(\texttt{SparseOrCycle}\) that if \(G\) satisfies a certain sparsity property, the running time can be bounded as follows.

Finally, we include a standard lemma about sampling a hitting set (see, e.g., [14], [7], [15]).

We remark that some of our algorithms get a graph \(G\) that is being updated during their run. Within their scope, \(G\) denotes the current graph that includes all updates done so far.

4 A new cycle searching technique↩︎

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

Consider a vertex \(s\in V\). It is straightforward to check whether \(s\) is on a \(C_{\leq 2k}\), for every integer \(k\), using \(\texttt{BallOrCycle}(G,s,k)\) in \(O(n)\) time. If \(\texttt{BallOrCycle}(G,s,k)\) does not return a \(C_{\leq 2k}\) then for every \(x,y\in N(s)\) it holds that \(V_x^{k-1}(G')\cap V_y^{k-1}(G')= \emptyset\), where \(G'= G\setminus \{s\}\), as otherwise there was a \(C_{\leq 2k}\) passing through \(s\) and \(\texttt{BallOrCycle}(G,s,k)\) would have returned a \(C_{\leq 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_{\leq 2k}\), using \(\texttt{BallOrCycle}(G', v,k)\), in \(O(n+m)\) time instead of \(O(deg(s) \cdot n)\). More specifically, we present algorithm \(\texttt{NbrBallOrCycle}(G, s, k)\) (see Algorithm [A-DoubleBfsCycle1]) that gets a graph \(G\), a vertex \(s\), and an integer \(k\geq 2\). We first initialize \(\hat{U}\) to \(\emptyset\). Then, we run \(\texttt{BallOrCycle}(G,s,k)\). If a cycle \(C\) is found by \(\texttt{BallOrCycle}(G, s,k)\) then \(C\) is returned by \(\texttt{NbrBallOrCycle}\). Otherwise, we add the vertex \(s\) to \(\hat{U}\), keep the neighbors of \(s\) in \(N_s\), and then remove \(s\) from \(G\). Recall that \(G'\) equals \(G\setminus \{s\}\). Next, for every \(v\in N_s\) we run \(\texttt{BallOrCycle}(G',v,k)\), as long as a cycle is not found. If a cycle \(C\) is returned by \(\texttt{BallOrCycle}(G',v,k)\) then \(C\) is returned by \(\texttt{NbrBallOrCycle}\).¹⁰ Otherwise, \(v\) is added to \(\hat{U}\). After the loop ends, the vertex \(s\) and its adjacent edges are added back to the graph, and the set \(\hat{U}\) is returned by \(\texttt{NbrBallOrCycle}\). We prove the following lemma.

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

We use Lemma 9 to bound the running time of \(\texttt{NbrBallOrCycle}\).

5 A \(2k\)-hybrid algorithm and a \((+1)\)-approximation of the girth↩︎

In this section we first show how to use algorithm \(\texttt{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_{\leq 2k}\) or determines that \(g>2k\). Then, we use the \(2k\)-hybrid algorithm to compute a \((+1)\)-approximation of \(g\).

5.1 A \(2k\)-hybrid algorithm↩︎

We first present algorithm \(\texttt{2-SparseOrCycle}(G,k)\) that gets a graph \(G\) and an integer \(k\geq 2\). Let \(G_0\) (\(G_1\)) be \(G\) before (after) running \(\texttt{2-SparseOrCycle}\). \(\texttt{2-SparseOrCycle}(G,k)\) either finds a \(C_{\leq 2k}\) or removes vertices that are not on a \(C_{\leq 2k}\), such that for every \(u\in G_1\), the ball graph \(B(G_1,u,2)\) is relatively sparse, that is, \(|E_u^2(G_1)|< m^{\frac{2}{k+1}}\). \(\texttt{2-SparseOrCycle}\) (see Algorithm [A-2sparseorcycle]) iterates over vertices using a for-each loop. Let \(s\) be the vertex currently considered. If \(\sum_{v \in N(s)} deg(v) \geq m^{\frac{2}{k+1}}\) then \(\texttt{NbrBallOrCycle}(G,s,k)\) is called. If \(\texttt{NbrBallOrCycle}\) returns a cycle \(C\) then \(\texttt{2-SparseOrCycle}\) returns \(C\). If \(\texttt{NbrBallOrCycle}\) returns a vertex set \(\hat{U}\) then \(\hat{U}\) is removed from \(G\). After the loop ends, if no cycle was found, we return \(\texttt{null}\).

We prove the following lemma.

Next, we use \(\texttt{2-SparseOrCycle}\) to design a \(2k\)-hybrid algorithm called \(\texttt{2k-Hybrid}\). Notice first that if \(|E_u^{k-1}|< m^{\frac{k-1}{k+1}}\) for every \(u\in V\), then it is straightforward to obtain an \(O(m^{1+\frac{k-1}{k+1}})\)-time \(2k\)-hybrid algorithm, by running \(\texttt{AllVtxBallOrCycle}(G,k)\). Thus, in \(\texttt{2k-Hybrid}\) we ensure that if we call \(\texttt{AllVtxBallOrCycle}\) then it holds for every \(u\in V\) that \(|E_u^{k-1}|< m^{\frac{k-1}{k+1}}\). To do so, we run \(\texttt{2-SparseOrCycle}\) and possibly \(\texttt{SparseOrCycle}\). If no cycle was returned then it holds that \(|E_u^{k-1}|< m^{\frac{k-1}{k+1}}\) for every \(u\in V\), and we can safely run \(\texttt{AllVtxBallOrCycle}\).

\(\texttt{2k-Hybrid}\) (see Algorithm [A-kHybrid]) gets a graph \(G\) and an integer \(k\geq 2\). \(\texttt{2k-Hybrid}\) is composed of three stages. In the first stage we call \(\texttt{2-SparseOrCycle}(G,k)\). If \(\texttt{2-SparseOrCycle}\) returns a cycle \(C\) then \(\texttt{2k-Hybrid}\) stops and returns \(C\), otherwise we proceed to the second stage. In the second stage, if \((k-1) \bmod 2 \neq 0\), we call \(\texttt{SparseOrCycle}(G, m^{\frac{1}{k+1}}, 1, k)\). If \(\texttt{SparseOrCycle}\) returns a cycle \(C\) then \(\texttt{2k-Hybrid}\) stops and returns \(C\), otherwise we proceed to the last stage. In the last stage, we call \(\texttt{AllVtxBallOrCycle}(G,k)\). If \(\texttt{AllVtxBallOrCycle}\) returns a cycle \(C\) then \(\texttt{2k-Hybrid}\) stops and returns \(C\), otherwise \(\texttt{2k-Hybrid}\) returns \(\texttt{null}\). In the next lemma we prove the correctness and analyze the running time of \(\texttt{2k-Hybrid}(G,k)\).

5.2 A \((+1)\)-approximation of the girth↩︎

Next, we describe algorithm \(\texttt{AdtvGirthApprox}\), which uses \(\texttt{2k-Hybrid}\) and the framework described in Section 1, to obtain a \((+1)\)-approximation of \(g\), when \(g\leq \log n\). \(\texttt{AdtvGirthApprox}\) (see Algorithm [A-AdditiveGirthApprox]) gets a graph \(G\). In \(\texttt{AdtvGirthApprox}\), we set \(k\) to \(2\) and start a while loop. In each iteration, we create a copy \(G'\) of \(G\) and call \(\texttt{2k-Hybrid}(G',k)\). If \(\texttt{2k-Hybrid}\) finds a cycle \(C\) then \(\texttt{AdtvGirthApprox}\) stops and returns \(C\), otherwise we increment \(k\) by \(1\) and continue to the next iteration. We prove the following theorem.

::: {#T-Main-Approx .@theorem} Theorem 1. Algorithm \(\texttt{AdtvGirthApprox}(G)\) returns either a \(C_{g}\) or a \(C_{g+1}\), and runs in \(\tilde{O}(m^{1+\frac{\ell -1}{\ell+1}})\) time, where \(g=2\ell\) or \(g=2\ell -1\) and \(2\leq \ell < \log n\).¹¹ :::

6 A general hybrid algorithm↩︎

Algorithm \(\texttt{2k-Hybrid}(G,k)\), presented in the previous section, either returns a \(C_{\leq 2k}\) or determines that \(g>2k\), in \(O(m^{1+\frac{k-1}{k+1}})\) time. In this section we introduce an additional parameter \(2\leq \alpha\leq k\) and present a \((2k,2\alpha)\)-hybrid algorithm that either returns a \(C_{\leq 2k}\) or determines that \(g>2\alpha\), in \(O((\frac{k+1}{\alpha-1}+\alpha) \cdot m^{1+\frac{\alpha-1}{k+1}})\) time. In Section 7 we use the \((2k,2\alpha)\)-hybrid algorithm to present two tradeoffs for girth approximation.

In order to obtain the \((2k,2\alpha)\)-hybrid algorithm we first extend algorithm \(\texttt{NbrBallOrCycle}\). Then, we use the extended \(\texttt{NbrBallOrCycle}\) together with additional tools that we develop to either return a \(C_{\leq 2k}\) or sparsify dense regions of the graph, so that we can check whether \(g>2\alpha\) (or return a \(C_{\leq 2k}\)) in \(O(m^{1+\frac{\alpha-1}{k+1}})\) time, by running \(\texttt{AllVtxBallOrCycle}(G,\alpha)\).

6.1 Extending \(\texttt{NbrBallOrCycle}\)↩︎

In algorithm \(\texttt{NbrBallOrCycle}\) we mark vertices that can be removed from the graph, by using the property that if \(\texttt{BallOrCycle}(v,k)\) did not return a \(C_{\leq 2k}\) then \(v\) is not on a \(C_{\leq 2k}\). In [10], they introduce an additional parameter \(\alpha\) and used the following extended version of this property: If \(\texttt{BallOrCycle}(v,k)\) did not return a \(C_{\leq 2k}\) then no vertex of \(V_v^{k-\alpha}\) is on a \(C_{\leq 2\alpha}\). We use the same approach and modify \(\texttt{NbrBallOrCycle}\) to get an additional integer parameter \(\alpha\) such that \(2\leq\alpha\leq k\). After each call to \(\texttt{BallOrCycle}(G',v,k)\), where \(v \in N_s\), if no cycle was found we add \(V_v^{k-\alpha}\), instead of \(v\), to \(\hat{U}\). The modified pseudo-code appears in Algorithm [A-DoubleBfsCycle]. We rephrase Lemma 8 to suit this modification.

For the running time, we note that the sets \(V_{v}^{k}\) are computed during the execution of \(\texttt{BallOrCycle}(G',v,k)\), for every \((s,v)\in N_s\) for which no cycle was found. Their total size is also \(O(n+m)\), and we can obtain from them the sets \(V_{v}^{k-\alpha}\) and add these sets to \(\hat{U}\) in \(O(n+m)\) time. Therefore, the modified \(\texttt{NbrBallOrCycle}\) also runs in \(O(n+m)\) time.

6.2 A \((\max\{2k,g\},\tilde{g})\)-hybrid algorithm↩︎

In this section we present a \((\max\{2k,g\},2\alpha)\)-hybrid algorithm called \(\texttt{ShortCycle}\), where \(\alpha = \lceil \frac{\tilde{g}}{2}\rceil\). \(\texttt{ShortCycle}\) (see Algorithm [A:OneAlg]) gets a graph \(G\) and two integers \(\alpha, k\geq 2\). If \(m \geq 1+\lceil n\cdot (1+n^{1/k})\rceil\) then we run algorithm \(\texttt{ShortCycleDense}(G,k)\), which is based on algorithm \(\texttt{DegenerateOrCycle}\) of [10] (for completeness, we include a pseudo-code in Algorithm [A:srtCycDns]). If \(m < 1+\lceil n\cdot (1+n^{1/k})\rceil\) then the main challenge is when \(\alpha \leq k< \frac{n}{2}\). In this case we run algorithm \(\texttt{ShortCycleSparse}(G,k,\alpha)\) (described later). The cases that \(k\geq \frac{n}{2}\) or \(k<\alpha\) are relatively simple and are treated by algorithm \(\texttt{SpecialCases}(G,k,\alpha)\) (see Section 6.2.1). We summarize the properties of \(\texttt{ShortCycle}(G,k,\alpha)\) in the next theorem.

::: {#Thm-One-Alg .@theorem} Theorem 2. Let \(\alpha,k\geq2\) be integers. \(\texttt{ShortCycle}(G,k,\alpha)\) 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 and either returns a \(C_{\leq \max\{2k,g\}}\), or determines that \(g > 2\alpha\). :::

The next corollary follows from Theorem 2, when \(\alpha \leq k\).

In the rest of this section, we present the proof of Theorem 2. As follows from [10], if \(m \geq 1+\lceil n\cdot (1+n^{1/k})\rceil\) then \(\texttt{ShortCycleDense}(G,k)\) returns in \(O(\min\{m,n^{1+1/k}\})\) time a \(C_{\leq 2k}\). We now consider the case in which \(m < 1+\lceil n\cdot (1+n^{1/k})\rceil\). We prove in Section 6.2.1 that \(\texttt{SpecialCases}(G,k,\alpha)\) satisfies the claim of Theorem 2, when \(k\geq\frac{n}{2}\) or \(k<\alpha\).

Our main technical contribution is algorithm \(\texttt{ShortCycleSparse}\) that handles the case of \(\alpha \leq k < \frac{n}{2}\). Notice that if \(|E_u^{\alpha-1}|< m^{\frac{\alpha-1}{k+1}}\) for every \(u\in V\), then \(\texttt{AllVtxBallOrCycle}(G,\alpha)\) is a \((2k,2\alpha)\)-hybrid algorithm that either finds a \(C_{\leq 2\alpha}\) (which is also a \(C_{\leq 2k}\) as \(\alpha \leq k\)) or determines that \(g>2\alpha\), in \(O(m^{1+\frac{\alpha-1}{k+1}})\) time. Thus, in \(\texttt{ShortCycleSparse}\) we ensure that if we call \(\texttt{AllVtxBallOrCycle}\), the property that \(|E_u^{\alpha-1}|< m^{\frac{\alpha-1}{k+1}}\), for every \(u\in V\) (whp), holds. To do so, we run \(\texttt{BfsSample}\) and possibly \(\texttt{HandleRemainder}\). If no cycle was returned, the property holds, and we can safely run \(\texttt{AllVtxBallOrCycle}\).

\(\texttt{ShortCycleSparse}\) (see Algorithm [A-BigKM]) gets a graph \(G\) and two integers \(\alpha, k\geq 2\) such that \(\alpha \leq k < \frac{n}{2}\), and is composed of three stages. In the first stage we call \(\texttt{BfsSample}(G,k,\alpha)\) (described later). If \(\texttt{BfsSample}\) returns a cycle \(C\) then \(\texttt{ShortCycleSparse}\) stops and returns \(C\), otherwise we proceed to the second stage. In the second stage, if \((k+1) \bmod (\alpha-1) \neq 0\), we call \(\texttt{HandleRemainder}(G,k,\alpha)\) (also described later). If \(\texttt{HandleRemainder}\) returns a cycle \(C\) then \(\texttt{ShortCycleSparse}\) stops and returns \(C\), otherwise we proceed to the last stage. In the last stage, we call \(\texttt{AllVtxBallOrCycle}(G,\alpha)\). If \(\texttt{AllVtxBallOrCycle}\) returns a cycle \(C\) then \(\texttt{2k-Hybrid}\) stops and returns \(C\), otherwise \(\texttt{ShortCycleSparse}\) returns \(\texttt{null}\).

Next, we give a high level description of \(\texttt{BfsSample}\). The goal of \(\texttt{BfsSample}\) is to either sparsify the graph without removing any \(C_{\leq 2\alpha}\), or to report a \(C_{\leq 2k}\). For simplicity assume that \((k+1) \bmod (\alpha-1) =0\). In such a case, if \(\texttt{BfsSample}\) does not report a \(C_{\leq 2k}\), then the graph after \(\texttt{BfsSample}\) ends contains every \(C_{\leq 2\alpha}\) that was in the original graph, and satisfies, whp, the following sparsity property: For every \(u\in V\) it holds that \(|E_u^{\alpha-1}| < m^{\frac{\alpha-1}{k+1}}\).

This implies that in \(\texttt{BfsSample}\) we need to find every \(u\in V\) which is in a dense region with \(|E_u^{\alpha-1}| \geq m^{\frac{\alpha-1}{k+1}}\), and to check if \(u\) is in a \(C_{\leq 2\alpha}\), so that if not we can remove \(u\). Finding every such \(u\) is possible within the time limit by running \(\texttt{IsDense}(G,u,m^{\frac{\alpha-1}{k+1}}, \alpha - 1)\) for every \(u \in V\). The problem is that checking whether \(u\) is on a \(C_{\leq 2\alpha}\) for every such \(u\) is too costly since there might be \(n\) such vertices, and this check costs \(O(n)\) using \(\texttt{BallOrCycle}(G,u,\alpha)\).

One way to overcome this problem is to sample an edge set \(S\) of size \(\tilde{\Theta}(m^{1-\frac{\alpha-1}{k+1}})\) that hits the \(m^{\frac{\alpha-1}{k+1}}\) closest edges of each vertex, and then use \(S\) to detect the vertices in the dense regions that are not on a \(C_{\leq 2\alpha}\). In \(\texttt{BfsSample}\) we use a detection process in which we call \(\texttt{BallOrCycle}\) or \(\texttt{NbrBallOrCycle}\) from the endpoints of \(S\)’s edges, and then, if no cycle was found, we use the information obtained from this call to identify vertices that are not on a \(C_{\leq 2\alpha}\). The detection process either detects vertices that are not on a \(C_{\leq 2\alpha}\) and can be removed, or reports a \(C_{\leq 2k}\). However, it is not clear how to implement this detection process efficiently, since just running \(\texttt{BallOrCycle}\) from the endpoints of \(S\)’s edges takes \(O(n m^{1-\frac{\alpha-1}{k+1}})\) time which might be too much. Our solution is an iterative sampling procedure that starts with a smaller hitting set of edges, of size \(\tilde{\Theta}(m^{\frac{\alpha-1}{k+1}})\). For such a hitting set we can run our detection process. If a \(C_{\leq 2k}\) was not reported, then we remove the appropriate vertices and sparsify the graph without removing any \(C_{\leq 2\alpha}\). When the graph is sparser, the running time of our detection process becomes faster. Thus, in the following iteration we can sample a larger hitting set for which we run this process, and either return a \(C_{\leq 2k}\) or sparsify the graph further for the next iteration. We continue the iterative sampling procedure until we get to the required sparsity property in which \(|E_u^{\alpha-1}| < m^{\frac{\alpha-1}{k+1}}\) for every \(u\in V\) (whp).

We remark that in the first iteration of \(\texttt{BfsSample}\), the detection process calls \(\texttt{NbrBallOrCycle}\), while in the rest of the iterations \(\texttt{BallOrCycle}\) is called. The use of \(\texttt{NbrBallOrCycle}\) allows us, in the case that no \(C_{\leq 2k}\) is reported, to bound \(|E_v^d|\) with \(m^{\frac{d}{k+1}}\) for every \(v\in V\), rather than \(|E_v^{d-1}|\). This is used to achieve the required sparsity property. Since \(\texttt{NbrBallOrCycle}\) runs in \(O(m)\) time we can only use it in the first iteration when the sampled set is small enough. In the rest of the iterations we use \(\texttt{BallOrCycle}\) instead.

We now formally describe \(\texttt{BfsSample}\). \(\texttt{BfsSample}\) (see Algorithm [BFSSample-M]) gets a graph \(G\) and two integers \(\alpha , k \geq 2\) such that \(\alpha \leq k < \frac{n}{2}\). We first set \(y\) to \(\lceil \frac{k+1}{\alpha-1}\rceil-1\). Then, we start the main for loop that has at most \(y\) iterations. In the \(i\)th iteration, we initialize \(\hat{V}\) to \(\emptyset\) and sample a set \(S_i\subseteq E\) of size \(\tilde{\Theta}(m^\frac{i\cdot(\alpha-1)}{k+1})\). Next, we scan the endpoints in \(V(S_i)\) using an inner for-each loop.

If \(i=1\), we call \(\texttt{NbrBallOrCycle}(G,s,k,\alpha)\) from every endpoint \(s\in V(S_1)\). \(\texttt{NbrBallOrCycle}\) returns either a cycle or a set of vertices \(\hat{U}\). If \(\texttt{NbrBallOrCycle}\) returns a cycle then the cycle is returned by \(\texttt{BfsSample}\). Otherwise, we add \(\hat{U}\) to \(\hat{V}\).

If \(i>1\) then we call \(\texttt{BallOrCycle}(s, k_i)\), where \(k_i=(k+1)-(i-1)\cdot(\alpha-1)\), from every endpoint \(s\in V(S_i)\). If a cycle is found by \(\texttt{BallOrCycle}\) then the cycle is returned by \(\texttt{BfsSample}\). If \(\texttt{BallOrCycle}\) does not return a cycle then we add \(V_{u_j}^{k_i -\alpha}\) to \(\hat{V}\).

Right after the inner for-each loop ends, we remove \(\hat{V}\) from \(G\), and continue to the next iteration of the main for loop. If no cycle was found after \(y\) iterations, we return \(\texttt{null}\). Let \(\ell \leq y\) be the last iteration in which vertices were removed. Let \(\hat{V_i}\) be the set of vertices that were removed during the \(i\)th iteration, where \(\hat{V_i} = \emptyset\) for \(i>\ell\). Let \(G_0\) (\(G_1\)) be \(G\) before (after) running \(\texttt{BfsSample}\). Figure ¿fig:fig:BFSSampleMFirstIteration? and Figure 5 illustrate the key steps of the first and the following iterations of \(\texttt{BfsSample}\), respectively. We summarize the properties \(\texttt{BfsSample}\) in the next lemma.

The first iteration of \(\texttt{BfsSample}\). (a) The edge \((x,y)\) is a sampled edge from a dense region of \(u\). (b) The run of \(\texttt{NbrBallOrCycle}\) from \(x\) and \(y\) leads to the removal of \(u\).

Recall that our goal is to obtain the sparsity property that \(|E_u^{\alpha-1}| < m^{\frac{\alpha-1}{k+1}}\), for every \(u\in V\), so that we can run \(\texttt{AllVtxBallOrCycle}(G,\alpha)\). However, after running \(\texttt{BfsSample}\) the required sparsity property is guaranteed to hold (whp) only if \((k+1) \bmod (\alpha-1) = 0\). In the case that \((k+1) \bmod (\alpha-1) \neq 0\) we need an additional step which is implemented in \(\texttt{HandleRemainder}\), to guarantee that the required sparsity property holds.

Next, we formally describe \(\texttt{HandleRemainder}\). \(\texttt{HandleRemainder}\) (see Algorithm [A-handleRM]) gets a graph \(G\) and two integers \(\alpha,k \geq 2\) such that \(k+1=q(\alpha-1)+r\) where \(q\geq 1\) and \(r>0\). We set \(D\) to \(m^{\frac{1}{k+1}}\) and \(r\) to \((k+1) \bmod (\alpha-1)\). Then, a while loop runs as long as \((\alpha-1) \bmod r \neq 0\). Let \(r_i\) be the value of \(r\) when the \(i\)th iteration begins, so that \(r_1\) is \((k+1) \bmod (\alpha-1)\). Let \(\ell\) be the total number of iterations and \(r_{\ell +1}\) the value of \(r\) after the \(\ell\)th iteration. During the \(i\)th iteration, we set \(r_{i+1}\) to \((\lceil \frac{\alpha-1}{r_i} \rceil \cdot r_i) - (\alpha-1)\), where \(\lceil \frac{\alpha-1}{r_i} \rceil \cdot r_i\) is the smallest multiple of \(r_i\) that is at least \(\alpha-1\) (see Figure 6). Then, we call \(\texttt{SparseOrCycle}(G, D, r_{i+1}, \alpha)\). If \(\texttt{SparseOrCycle}\) returns a cycle \(C\) then \(\texttt{HandleRemainder}\) returns \(C\). If \(\texttt{SparseOrCycle}\) does not return a cycle then it might be that some vertices were removed from \(G\), and we continue to the next iteration. If the while loop ends without returning a cycle then we return \(\texttt{null}\). Let \(G_0\) (\(G_1\)) be \(G\) before (after) running \(\texttt{HandleRemainder}\). Next, we prove two properties on the value of \(r\) during the run of \(\texttt{HandleRemainder}\).

We now prove the main lemma regarding \(\texttt{HandleRemainder}\).

Now we are ready to prove the correctness and running time of \(\texttt{ShortCycleSparse}\).

Since \(\texttt{ShortCycleSparse}\) is run by \(\texttt{ShortCycle}\) when \(m\leq O(n^{1+\frac{1}{k}})\) and when \(\alpha\leq k\) and so \(1+\frac{\alpha-1}{k+1}\leq 2\), we have \(m^{1+\frac{\alpha-1}{k+1}}\leq O(n^{1+\frac{\alpha}{k}})\). Thus, the running time of \(\texttt{ShortCycleSparse}\) is whp \(\tilde{O}(( q+r) \cdot \min\{ m^{1+\frac{\alpha-1}{k+1}}, n^{1+\frac{\alpha}{k}} \})\), which is at most \(\tilde{O}(( \frac{k+1}{\alpha-1}+\alpha) \cdot \min\{ m^{1+\frac{\alpha-1}{k+1}}, n^{1+\frac{\alpha}{k}} \})\).

6.2.1 Algorithm \(\texttt{SpecialCases}\)↩︎

We now present algorithm \(\texttt{SpecialCases}\) that handles special cases of \(k\) and \(\alpha\). \(\texttt{SpecialCases}(G,k,\alpha)\) gets as an input a graph \(G\) and two integers \(k\geq 2\) and \(\alpha \geq 2\).

If \(k\geq \frac{n}{2}\), the algorithm simply runs \(\texttt{BallOrCycle}(G,w,n)\) from an arbitrary vertex \(w\in V\) in \(O(n)\leq O(\min\{m^{1+\frac{\alpha-1}{k+1}},n^{1+\frac{\alpha}{k}}\})\) time, to check whether \(G\) contains a cycle. If a cycle is found then its length is at most \(n\leq 2k\), and we return a \(C_{\leq 2k}\). Otherwise, \(g=\infty\) so for every integer \(\alpha\) we return that \(g>2\alpha\).

If \(k \leq \alpha -1\), we check if the graph contains a \(C_d\) for \(d\gets 3,\dots, 2\alpha\), using an algorithm of Alon, Yuster and Zwick [16]. Their algorithm decides whether \(G\) contains a \(C_{2 \ell-1}\) or a \(C_{2 \ell}\), and finds such a cycle if it does, in \(O(m^{2-\frac{1}{\ell}})\) time. Applying this algorithm with increasing cycle lengths until a length of \(2\alpha\) (the values of \(\ell\) are in the worst case \(2,3,\dots,\alpha\)), we can either find a shortest cycle or determine that \(g> 2\alpha\). The running time is \(O(m^{2-\frac{1}{2}}+m^{2-\frac{1}{3}}+\dots+ m^{2-\frac{1}{\alpha}})= O(\alpha \cdot m^{2-\frac{1}{\alpha}}) = O(\alpha \cdot m^{1+\frac{\alpha-1}{\alpha}})\) time¹⁴. Since \(k\leq \alpha-1\), we have \(k+1 \leq \alpha\) and therefore \(O(\alpha\cdot m^{1+\frac{\alpha-1}{\alpha}}) \leq O(\alpha\cdot m^{1+\frac{\alpha-1}{k+1}})\). In addition, since \(m\leq O(n^{1+\frac{1}{k}})\) and since \(1+\frac{\alpha-1}{\alpha}\leq 2\), we have \(m^{1+\frac{\alpha-1}{\alpha}} \leq O(n^{(1+\frac{1}{k})\cdot (1+\frac{\alpha-1}{\alpha})}) \leq O(n^{(1+\frac{1}{k})\cdot (1+\frac{\alpha-1}{k+1})}) = O(n^{1+\frac{\alpha}{k}})\). Therefore, the running time is \(O(\alpha\cdot m^{1+\frac{\alpha-1}{\alpha}})\leq O(\alpha\cdot \min\{m^{1+\frac{\alpha-1}{k+1}},n^{1+\frac{\alpha}{k}}\})\).

By choosing which algorithm to run according to the relation between \(k\), \(\alpha\) and \(\frac{n}{2}\), we get that for every two integers \(\alpha\geq2\) and \(k\geq 2\), algorithm \(\texttt{ShortCycle}(G,k,\alpha)\) 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 and either returns a \(C_{\leq \max\{2k,g\}}\), or determines that \(g > 2\alpha\). This completes the proof of Theorem 2.

7 Approximation of the girth↩︎

In this section we present two new tradeoffs for girth approximation that follow from Corollary 4. In these tradeoffs we use \(\texttt{ShortCycle}\) with \(2\leq \alpha \leq k\), so by Corollary 4, \(\texttt{ShortCycle}\) is an \(\tilde{O}((\frac{k+1}{\alpha-1}+\alpha) \cdot \min \{m^{1+\frac{\alpha-1}{k+1}},n^{1+\frac{\alpha}{k}}\})\)-time, \((2k,2\alpha)\)-hybrid algorithm.

7.1 Dense graphs↩︎

Kadria et al. [10] presented an \(O((\alpha-c)\cdot n^{1+\frac{\alpha}{2\alpha - c}})\)-time, \((4\alpha-2c, 2\alpha)\)-hybrid algorithm, where \(0 < c \leq \alpha\) are two integers (see footnote 4 in Section 2). This algorithm, combined with a binary search, was used by [10] to compute for every \(\varepsilon\in (0,1]\) a cycle \(C\) such that \(wt(C) \leq 4\lceil \frac{g}{2}\rceil - 2\lfloor \varepsilon \lceil \frac{g}{2}\rceil \rfloor \leq (2-\varepsilon)g+4\), in \(\widetilde{O}(n^{1+1/(2-\varepsilon)})\) time, if \(g\leq \log^2 n\). We use \(\texttt{ShortCycle}\) in a similar way and prove:

::: {#L-approx-n .@theorem} Theorem 3. Let \(\ell\geq 2\) be an integer, \(\varepsilon\in [0,1]\) and \(g\leq \log^2 n\). It is possible to compute, whp, in \(\widetilde{O}(\ell\cdot n^{1+1/(\ell-\varepsilon)})\) time, a cycle \(C\) such that \(wt(C) \leq 2\ell\lceil \frac{g}{2}\rceil - 2\lfloor \varepsilon \lceil \frac{g}{2}\rceil \rfloor \leq (\ell-\varepsilon)g+\ell+2\).¹⁵ :::

Our algorithm can be viewed as a natural generalization of a couple of algorithms from [10]. By setting \(\ell=2\) in Theorem 3 we get the \((2-\varepsilon)g+4\) approximation of [10]. By setting \(\varepsilon=0\) we get an \(\widetilde{O}(\ell\cdot n^{1+1/\ell})\) time algorithm that computes a \(C_{\leq 2\ell\lceil \frac{g}{2}\rceil}\), which is similar to the \(\widetilde{O}(n^{1+1/\ell})\) time algorithm of [10] that computes a \(C_{\leq 2\ell \lceil \frac{g}{2}\rceil}\).

7.2 Sparse graphs↩︎

We use a similar approach to obtain a tradeoff for girth approximation in sparse graphs. We prove the following theorem.

::: {#L-approx-m .@theorem} Theorem 4. Let \(\ell\geq 3\) be an integer, \(\varepsilon\in [0,1)\) and \(g\leq \log^2 n\). It is possible to compute, whp, in \(\widetilde{O}(\ell\cdot m^{1+1/(\ell-\varepsilon)})\) time, a cycle \(C\) such that \(wt(C) \leq 2\ell(\lceil \frac{g}{2}\rceil-1) - 2\lfloor \varepsilon (\lceil \frac{g}{2}\rceil-1) \rfloor-2 \leq (\ell-\varepsilon)g-\ell+2\varepsilon\). :::

By setting \(\varepsilon=0\) we get an \(\widetilde{O}(\ell\cdot m^{1+1/\ell})\)-time algorithm that computes a \(C_{\leq 2\ell(\lceil \frac{g}{2}\rceil-1)}\), as opposed to the \(\widetilde{O}(\ell\cdot n^{1+1/\ell})\) time algorithm that computes a \(C_{\leq2\ell\lceil \frac{g}{2}\rceil}\).

References↩︎

---

1. Department of Computer Science, Bar Ilan University, Ramat Gan 5290002, Israel. E-mail liam.roditty@biu.ac.il. Supported in part by BSF grants 2016365 and 2020356.↩︎

2. Department of Computer Science, Bar Ilan University, Ramat Gan 5290002, Israel. E-mail plia.trabelsi@gmail.com.↩︎

3. \(O(n^{3-c})\) time for a constant \(c > 0\).↩︎

4. Up to \(\lceil g / 2 \rceil - 1\) tradeoff points are added since for every such \(\ell\), when \(\varepsilon\) is a multiple of \(\frac{1}{\lceil g/2\rceil}\), we get an \(\tilde{O}(n^{1+1/(\ell-\varepsilon)})\)-time algorithm which computes a \(C_{\leq 2(\ell -\varepsilon) \lceil g/2\rceil}\).↩︎

5. \(\texttt{Cycle}\) runs in \(O(n^{1+\frac{1}{\ell}}+m)\) time, which can be reduced to \(O(n^{1+\frac{1}{\ell}})\) time, as shown in [10].↩︎

6. Kadria et al. [10] presented also an \(O((\alpha-c)\cdot n^{1+\frac{\alpha}{2\alpha - c}})\)-time, \((4\alpha-2c, 2\alpha)\)-hybrid algorithm, where \(0 < c \leq \alpha\) 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 \(0 < c\leq \alpha\), the possible values of \(k\) are restricted and must satisfy \(\alpha \leq k < 2\alpha\). 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\). ↩︎

7. Both \(C_{\ell}\) and \(C_{\leq \ell}\) might not be simple cycles. However, the cycles that our algorithms return are simple.↩︎

8. When the graph is clear from the context, we sometimes omit \(G\) from the notations.↩︎

9. If \(V_v^R\) is returned then we assume that \(V_v^R\) is ordered by the distance from \(v\), and for every \(u \in V_v^R\) we store \(d(u,v)\) with \(u\). Thus, given the set \(V_v^R\), we can find \(V_v^{R'}\) for every \(R'<R\) in \(O(|V_v^{R'}|)\) time.↩︎

10. For our needs it suffices to stop and return a cycle passing through an \(s\) neighbor once we find one, though \(\texttt{BallOrCycle}\) can be run from all the neighbors of \(s\) in the same running time bound of \(O(n+m)\).↩︎

11. We note that when \(\ell \geq \log n\), the \(O(n^2)\)-time, \((+1)\)-approximation of Itai and Rodeh [1] can be used.↩︎

12. This is the running time in the case that \(S_i\) was a hitting sets as described for every \(1\leq i \leq y\). This happens whp since we assume that \(k < \frac{n}{2} < n\) and therefore \(y < n\). For every \(1\leq i \leq y\) the probability that \(S_i\) is not such a hitting set is at most \(\frac{1}{n^c}\). Therefore, using the standard union bound argument, the probability that there exists \(1\leq i \leq y\) such that \(S_i\) is not a hitting set is at most \(y \cdot \frac{1}{n^c} \leq \frac{1}{n^{c-1}}\). For large enough \(c\), we get that \(S_i\) is a hitting set for every \(1\leq i \leq y\), whp.↩︎

13. Throughout the run of \(\texttt{ShortCycleSparse}\), some of the bounds that we get on \(|E_v^d|\) for vertices \(v\in V\) and distances \(d\), are whp, because the sets that we sample are hitting sets whp (see the proof of Lemma 14). Therefore, also the running times of \(\texttt{BfsSample}\), \(\texttt{HandleRemainder}\) and \(\texttt{AllVtxBallOrCycle}\) are whp, since they rely on these bounds.↩︎

14. It is possible to modify the algorithm of Alon et al. [16] to search in \(O(m^{2-\frac{1}{\ell}})\) time a shortest cycle of length at most \(2\ell\) instead of exactly \(2\ell-1\) or \(2\ell\), and then run it only with \(\ell = \alpha\), to avoid the \(\alpha\) factor in the running time.↩︎

15. We note that when \(\ell> \log n\), we can run the \(\tilde{O}(n^{1+1/\ell'})\)-time algorithm of [10], which computes a \(C_{\leq 2\ell' \lceil g/2\rceil}\), with \(\ell' = \ell -1\), to get the required approximation. Since \(\ell> \log n\), its running time is \(\tilde{O}(n)\). Thus, our running time becomes \(\tilde{O}(n^{1+1/{(\ell-\varepsilon)}})\), where the \(\ell\) factor is absorbed into the \(\tilde{O}\) notation.↩︎

16. The running time of each call to \(\texttt{ShortCycle}\) is whp. Since the number of calls to \(\texttt{ShortCycle}\) is at most \(\log^2 n < n\), using a union bound argument as in the proof of Lemma 14 we get that also the total running of all the calls is whp. ↩︎

17. See footnote 14.↩︎