License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.2
URN: urn:nbn:de:0030-drops-186552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18655/
Abboud, Amir ;
Dalirrooyfard, Mina ;
Li, Ray ;
Vassilevska Williams, Virginia
On Diameter Approximation in Directed Graphs
Abstract
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time Hypothesis (SETH) yields a lower bound on the time vs. approximation trade-off that is quite close to the upper bounds.
In directed graphs, however, where only some of the upper bounds apply, much larger gaps remain. Since d(u,v) may not be the same as d(v,u), there are multiple ways to define the problem, the two most natural being the (one-way) diameter (max_(u,v) d(u,v)) and the roundtrip diameter (max_{u,v} d(u,v)+d(v,u)). In this paper we make progress on the outstanding open question for each of them.
- We design the first algorithm for diameter in sparse directed graphs to achieve n^{1.5-ε} time with an approximation factor better than 2. The new upper bound trade-off makes the directed case appear more similar to the undirected case. Notably, this is the first algorithm for diameter in sparse graphs that benefits from fast matrix multiplication.
- We design new hardness reductions separating roundtrip diameter from directed and undirected diameter. In particular, a 1.5-approximation in subquadratic time would refute the All-Nodes k-Cycle hypothesis, and any (2-ε)-approximation would imply a breakthrough algorithm for approximate ?_∞-Closest-Pair. Notably, these are the first conditional lower bounds for diameter that are not based on SETH.
BibTeX - Entry
@InProceedings{abboud_et_al:LIPIcs.ESA.2023.2,
author = {Abboud, Amir and Dalirrooyfard, Mina and Li, Ray and Vassilevska Williams, Virginia},
title = {{On Diameter Approximation in Directed Graphs}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {2:1--2:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18655},
URN = {urn:nbn:de:0030-drops-186552},
doi = {10.4230/LIPIcs.ESA.2023.2},
annote = {Keywords: Diameter, Directed Graphs, Approximation Algorithms, Fine-grained complexity}
}
|
Keywords: |
|
Diameter, Directed Graphs, Approximation Algorithms, Fine-grained complexity |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
