License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.35
URN: urn:nbn:de:0030-drops-124421
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12442/
Dalirrooyfard, Mina ;
Vassilevska Williams, Virginia
Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph
Abstract
The girth is one of the most basic graph parameters, and its computation has been studied for many decades. Under widely believed fine-grained assumptions, computing the girth exactly is known to require mn^{1-o(1)} time, both in sparse and dense m-edge, n-node graphs, motivating the search for fast approximations. Fast good quality approximation algorithms for undirected graphs have been known for decades. For the girth in directed graphs, until recently the only constant factor approximation algorithms ran in O(n^ω) time, where ω < 2.373 is the matrix multiplication exponent. These algorithms have two drawbacks: (1) they only offer an improvement over the mn running time for dense graphs, and (2) the current fast matrix multiplication methods are impractical. The first constant factor approximation algorithm that runs in O(mn^{1-ε}) time for ε > 0 and all sparsities m was only recently obtained by Chechik et al. [STOC 2020]; it is also combinatorial.
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}/ε²) edges in Õ(m√n/ε²) time. This improves upon the previous approximation factor (8+ε) of Chechik et al. for the same running time.
BibTeX - Entry
@InProceedings{dalirrooyfard_et_al:LIPIcs:2020:12442,
author = {Mina Dalirrooyfard and Virginia Vassilevska Williams},
title = {{Conditionally Optimal Approximation Algorithms for the Girth of a Directed Graph}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12442},
URN = {urn:nbn:de:0030-drops-124421},
doi = {10.4230/LIPIcs.ICALP.2020.35},
annote = {Keywords: Shortest cycle, Girth, Graph algorithms, Approximation algorithms, Fine-grained complexity, Roundtrip Spanner}
}
|
Keywords: |
|
Shortest cycle, Girth, Graph algorithms, Approximation algorithms, Fine-grained complexity, Roundtrip Spanner |
|
Collection: |
|
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
29.06.2020 |
