$\delta = 2m/n$ and that also the maximum degree in the graph is also $O(\delta)$.

The subroutine ${\textsc{SimilarSet}}$ gets as an input the graph $G$ and the target distance $R$ and either returns a cycle of length at most $3R$ or returns a subset $A_v$ of vertices for every $v\in V$. The subset $A_v$ for a vertex $v\in V$ consists of vertices at distance at most $R/2$ from $v$ with the guarantee that $A_v$ contains all vertices that are

1.  At distance at most $R/2$ from $v$ and

2.  On a cycle of length $R$ with $v$.

Procedure ${\textsc{GirthApprox}}$ invokes the Procedure ${\textsc{SimilarSet}}$ twice, once on $G$ and once on the reversed graph of $G$ (the graph obtained by reversing every edge of $G$). If a cycle of length $3R$ is returned in one of these calls then procedure ${\textsc{GirthApprox}}$ returns such a cycle. Otherwise, let $\{A_v^{\mathrm{in}}\}_{v \in V}$ be the sets returned from invoking ${\textsc{SimilarSet}}$ on the graph $G$ and $\{A_v^{\mathrm{out}}\}_{v \in V}$ on the reversed graph. Next, the procedure for every $v\in V$ checks if there is a cycle containing $v$ of length at most $R$ in the induced graph of $A_v^{\mathrm{in}}\cup A_v^{\mathrm{out}}$. If such a cycle exists 