2020/04/23 by Dalirrooyfard, Mina, Williams, Virginia Vassilevska
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2004.11445
It is known that a better than 2-approximation algorithm for the girth in dense directed unweighted graphs needs n3-o(1) time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in O(mn1-ε) 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 mn1-o(1) time for some sparsity m if it achieves a (2-ε)-approximation for any ε>0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in O(mn3/4) time, and a (2+ε)-approximation algorithm (for any ε>0) that works in weighted graphs and runs in O(m√ n) time. Our algorithms are combinatorial. We also obtain a (4+ε)-approximation of the girth running in O(mn√(2)-1) time, improving upon the previous best O(m√ n) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5+ε)-approximate roundtrip spanner on O(n1.5/ε2) edges in O(m√ n/ε2) time. This improves upon the previous approximation factor (8+ε) of Chechik et al. for the same running time.