proof to \[proofs:regular\].

\[lemma:regular\] Given a directed weighted graph $G=(V,E)$ of $n$ vertices and $m$ edges with non negative edge weights, one can construct a graph $H$ in $O(m)$ time of $O(n)$ vertices and $O(m)$ edges with non negative edge weights and of maximum degree $O(m/n)$ such that

1.  All roundtrip distances (between pairs of vertices in $G$) in $H$ and in $G$ are the same.

2.  Given a cycle in $H$, one can find in $O(m)$ time a cycle in $G$ of the same length.

3.  Given a subgraph $H'$ of $H$, one can find in $O(m)$ time a subgraph $G'$ of $G$ such that the number of edges in $G'$ is at most the number of edges in $H'$ and the roundtrip distances in $H'$ and $G'$ are the same.

An $\tilde{O}(m \sqrt{n})$ Time $3$-approximation to Girth  {#sec:girth3}
-----------------------------------------------------------

In this section we show a procedure that given a directed weighted graph $G$ and a girth estimate $R$, returns a cycle of length at most $3R$ if the girth in $G$ is at most $R$. The algorithm is given by ${\textsc{GirthApprox}}$ (See \[algo:girth3\]) which in turn invokes the subroutine ${\textsc{SimilarSet}}$ (See \[alg:similar\_vertices\]).

In order to approximate the girth 