Article Source

• Conditionally optimal approximation algorithms for the girth of a directed graph

Conditionally optimal approximation algorithms for the girth of a directed graph

• Paper: https://arxiv.org/abs/2004.11445
• ICALP-A 2020
• Conditionally optimal approximation algorithms for the girth of a directed graph
• Mina Dalirrooyfard, Virginia Vassilevska Williams

Abstract

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-ϵ) 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-ϵ)-approximation for any ϵ>0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in Õ(mn^3/4) time, and a (2+ϵ)-approximation algorithm (for any ϵ>0) that works in weighted graphs and runs in Õ(m√(n)) time. Our algorithms are combinatorial. We also obtain a (4+ϵ)-approximation of the girth running in Õ(mn^√(2)-1) time, improving upon the previous best Õ(m√(n)) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5+ϵ)-approximate roundtrip spanner on Õ(n^1.5/ϵ^2) edges in Õ(m√(n)/ϵ^2) time. This improves upon the previous approximation factor (8+ϵ) of Chechik et al. for the same running time.