runtime $|G_M(v)| = {\tilde{O}}(\sqrt{n})$ for that vertex $v$.

Formalizing this final step, the algorithm computes a shortest path tree $T(v)$ from $v$ up to depth $R/2$, keeping only vertices $s \in V$ such that $d(v,s) \le R/2$ and $d(s, t) \le 3R/2 \text{ for all } t\in \bigcup_{0 \le j \le M}{R_{j}(v)}$. The set $A_v$ is the set of vertices in $T(v)$.

Invoke ${\textsc{SimilarSet}}(G,R)$ to either find a cycle of length at most $3R$ or set $A_v^{\mathrm{out}}\subseteq V$ for each $v \in V(G)$. \[line:similar\_search\_1\] Invoke ${\textsc{SimilarSet}}({G^{\mathrm{rev}}},R)$ where ${G^{\mathrm{rev}}}$ is the graph where the direction of every edge is reversed to either find a cycle of length at most $3R$ or sets $A_v^{\mathrm{in}}\subseteq V$ for each $v \in V(G)$. If a cycle of length at most $3R$ has yet to be found for each $v \in V(G)$ perform Dijsktra from $v$ in the graph induced by $A_v^{{\mathrm{out}}} \cup A_v^{{\mathrm{in}}}$ to find a cycle of length at most $R$ through one of the $v$. \[line:search\_union\] Return any cycle of length at most $3R$ found. \[line:final\_ball-search\]

For $M = 50\log n$, sample sets $S_0, S_1, \cdots, S_M \subseteq V(G)$, each of expected size $O(n^{1/2})$ by sampling every vertex $v \in V$ independently with 