It is known that a better than $2$-approximation algorithm for the girth in dense directed unweighted graphs needs $n^{3-o(1)}$ time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in $O(mn^{1-\epsilon})$ time (by Chechik et al.) is $3$. Is the true answer $2$ or $3$? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least $mn^{1-o(1)}$ time for some sparsity $m$ if it achieves a $(2-\epsilon)$-approximation for any $\epsilon>0$. Second we give a $2$-approximation algorithm for the girth of unweighted graphs running in $\tilde{O}(mn^{3/4})$ time, and a $(2+\epsilon)$-approximation algorithm (for any $\epsilon>0$) that works in weighted graphs and runs in $\tilde{O}(m\sqrt n)$ time. Our algorithms are combinatorial. We also obtain a $(4+\epsilon)$-approximation of the girth running in $\tilde{O}(mn^{\sqrt{2}-1})$ time, improving upon the previous best $\tilde{O}(m\sqrt n)$ running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a $(5+\epsilon)$-approximate roundtrip spanner on $\tilde{O}(n^{1.5}/\epsilon^2)$ edges in $\tilde{O}(m\sqrt n/\epsilon^2)$ time. This improves upon the previous approximation factor $(8+\epsilon)$ of Chechik et al. for the same running time.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok