  We consider the problem of approximating the girth, $g$, of an unweighted and
undirected graph $G=(V,E)$ with $n$ nodes and $m$ edges. A seminal result of
Itai and Rodeh [SICOMP'78] gave an additive $1$-approximation in $O(n^2)$ time,
and the main open question is thus how well we can do in subquadratic time.
  In this paper we present two main results. The first is a
$(1+\varepsilon,O(1))$-approximation in truly subquadratic time. Specifically,
for any $k\ge 2$ our algorithm returns a cycle of length $2\lceil
g/2\rceil+2\left\lceil\frac{g}{2(k-1)}\right\rceil$ in $\tilde{O}(n^{2-1/k})$
time. This generalizes the results of Lingas and Lundell [IPL'09] who showed it
for the special case of $k=2$ and Roditty and Vassilevska Williams [SODA'12]
who showed it for $k=3$. Our second result is to present an
$O(1)$-approximation running in $O(n^{1+\varepsilon})$ time for any
$\varepsilon > 0$. Prior to this work the fastest constant-factor approximation
was the $\tilde{O}(n^{3/2})$ time $8/3$-approximation of Lingas and Lundell
[IPL'09] using the algorithm corresponding to the special case $k=2$ of our
first result.
