then the procedure returns such a cycle.

Procedure ${\textsc{SimilarSet}}$ works as follows. The algorithms starts by sampling $O(\log{n})$ independent subsets $S_i$ of expected size $O(\sqrt{n})$ each for $1 \le i \le M$ where $M=50\log{n}$. From every vertex $w \in \bigcup_{1 \le i \le M}{S_i}$ the algorithm runs Dijkstra from and to $w$ in $G$. If a cycle of length $3R$ is detected then the algorithm returns it.

Next for every vertex $v\in V$ and index $1 \le i \le M$ the algorithm defines a set $T_i(v) \subseteq S_i$. The sets $T_i(v)$ will be used to reduce the number of potential vertices that can be on a cycle of length at most $R$ with $v$. First, the set $T_0(v)$ consists of all vertices in $S_0$ that are at distance at most $R/2$ from $v$. Let $R_0(v)$ be a sampled set of $O(\log{n})$ vertices from $T_0(v)$. Now, the sets $T_{i}(v)$ and $R_{i}(v)$ are defined as follows. The set $T_{i}(v)$ is the set of all vertices $s \in S_i$ 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 i-1}{R_{j}(v)}$. Again, define $R_i(v)$ as a sampled set of $O(\log n)$ vertices from $T_i(v)$.

To 