deterministic algorithm are essential in obtaining this last result, and that more directly combining the ideas of [@PRSTV18] with our constant factor approximation algorithm does not seem to give an $O(k\log k)$ multiplicative girth approximation in ${\tilde{O}}(m^{1+1/k})$ time.

Overview of Approach {#sec:approach_overview}
--------------------

#### Summary of randomized $O(1)$ approach.

Our approach to obtaining a $3$-approximation in \[sec:constantapprox\] to the girth is rooted in the simple insight that if a vertex $v$ is in a cycle of length $R$ then every vertex in the ball of radius $\alpha$ from $v$ is at distance at most $\alpha + R$ from every vertex in the cycle. Consequently, for each vertex if we repeatedly prune vertices from its outball of radius $R$ if they do not have the property that they can reach every vertex in this ball by traversing a distance at most $2R$, then we will never prune away vertices in a cycle of length $R$ from that vertex.

Leveraging these insights, we can show that if we randomly compute distances to and from a random ${\tilde{O}}(\sqrt{n})$ vertices and if a cycle of length $O(R)$ is not discovered immediately then we can efficiently implement a pruning procedure so that each vertex only 