randomness and improves the approximation factor in Pachocki [*et al.*]{} [@PRSTV18], and our third is the first time versus quality trade-off for obtaining constant approximations.
author:
- |
    Shiri Chechik\
    Tel Aviv University\
    [shiri.chechik@gmail.com]{} [^1]
- |
    Yang P. Liu\
    Stanford University\
    `yangpatil@gmail.com` [^2]
- |
    Omer Rotem\
    Tel Aviv University\
    [omer.rotem1@gmail.com]{}
- |
    Aaron Sidford\
    Stanford University\
    `sidford@stanford.edu` [^3]
bibliography:
- 'refs.bib'
title: |
    Constant Girth Approximation for Directed Graphs in\
    Subquadratic Time
---

Introduction
============

The *girth* of a graph $G$ is the length of the shortest cycle in $G$. It is an important graph quantity that has been studied extensively in both combinatorial settings (see Bollobás’s book [@Bollobas] for a discussion) and computational settings. In particular, exact algorithms for the girth running in time $O(mn)$ in weighted directed graphs [@OS17] are known. On the other hand, a result of Vassilevska W. and Williams show that a truly subcubic algorithm for girth (i.e. running in time $n^{3-{\varepsilon}}$ for some ${\varepsilon}> 0$) implies a truly subcubic algorithm for the All Pairs Shortest Path (APSP) problem [@VW10]. As it is a longstanding open problem whether APSP admits a truly subcubic time algorithm, exact computation of the girth in truly subcubic 