$d_S(u {\leftrightarrows}v) \le \alpha \cdot d_G(u {\leftrightarrows}v)$ for all $u, v \in V(G).$

For weighted directed graph $G$ we define the *inball* and *outball* of radius $r$ around a vertex $v$ as $${B^{\mathrm{in}}}_v(r) {:=}G[\{ u : d(u, v) \le r \}] \text{ and } {B^{\mathrm{out}}}_v(r) {:=}G[\{ u : d(v, u) \le r \}]$$ respectively. In other words, the inball of radius $r$ around $v$ is the subgraph induced by vertices $u$ with $d(u, v) \le r.$ The outball is defined similarly. We define the *ball* of radius $r$ around vertex $v$ as $$B_v(r) {:=}G[\{ u : d(u {\leftrightarrows}v) \le r \}].$$ In other words, the ball of radius $r$ around $v$ is the subgraph induced by vertices $u$ within roundtrip distance $r$ of $v$.

Randomized Constant Approximations {#sec:constantapprox}
==================================

Here we provide algorithms for efficiently computing a 3-approximation to the girth \[sec:girth3\]. To simplify our algorithm and analysis we assume that the maximum degree of $G$ is bounded by $O(m/n)$, i.e. we assume it is only a constant larger than the average degree, which is $2m/n$. We justify this assumption by showing that we can always reduce to this case as is formalized in the following lemma. We defer the 