probability $p = n^{-1/2}$. Run Dijkstra to/from each vertex $v\in S_i$ for every $1 \leq i \leq M$. If there exists a vertex $v \in \cup_{1 \le i \le M}{S_i}$ such that $v$ is on a cycle of length $3R$ then return the shortest such cycle. \[line:returncycledetected\] Set $T_0(v) \gets \{s \in S_0 \mid d(v, s) \le R/2 \}$. Let $R_{i-1}(v)$ be $100 \log{n}$ vertices chosen independently at random from $T_{i-1}(v)$ Let $R_{i-1}(v) = T_{i-1}(v)$. $T_i(v) \gets \{ s \in S_{i} \mid d(v, s) \le R/2  \text{ and }
        d(s, t) \le 3R/2 \text{ for all } t\in \cup_{0 \le j \le i-1}{R_{j}(v)}\}$ Compute a shortest path tree $T(v)$ up to depth $R/2$ keeping only vertices $s$ such that $d(s, t) \le 3R/2 \text{ for all } t\in \cup_{0 \le j \le M}{R_{j}(v)}\}$. Set $A_v$ to be the set of vertices in $T(v)$. \[line:GrowSmallBall\] $A_v$ for all $v \in V$

Next we prove the correctness of our girth computation algorithm ${\textsc{GirthApprox}}$ (\[algo:girth3\]) and bound its running time. First we prove the following lemma which provides a fairly straightforward argument that the algorithm always outputs the correct result. The more challenging part of the analysis will be to bound its running 