Tight conditional lower bounds for approximating diameter in directed graphs

DOI10.1145/3406325.3451130MaRDI QIDQ6065286zbMATH OpenOpenAlexFDO

Authors M. Dalirrooyfard, Nicole Wein

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.03892

zbMATH Keywords

fine-grained complexitygraph algorithmsgraph diameter

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with $m$ edges requires $m^{2-o(1)}$ time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficient approximation algorithms for Diameter are desired. There is a folklore algorithm that gives a $2$-approximation for Diameter in $ildeO(m)$ time. Additionally, a line of work concludes with a $3/2$-approximation algorithm for Diameter in weighted directed graphs that runs in $ildeO(m^{3/2})$ time. The $3/2$-approximation algorithm is known to be tight under SETH: Roditty and Vassilevska W. proved that under SETH any $3/2-epsilon$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{2-o(1)}$ time, and then Backurs, Roditty, Segal, Vassilevska W., and Wein and the follow-up work of Li proved that under SETH any $5/3-epsilon$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{3/2-o(1)}$ time. Whether or not the folklore 2-approximation algorithm is tight, however, is unknown, and has been explicitly posed as an open problem in numerous papers. Towards this question, Bonnet recently proved that under SETH, any $7/4-epsilon$ approximation requires $m^{4/3-o(1)}$, only for directed weighted graphs. We completely resolve this question for directed graphs by proving that the folklore 2-approximation algorithm is conditionally optimal. In doing so, we obtain a series of conditional lower bounds that together with prior work, give a complete time-accuracy trade-off that is tight with all known algorithms for directed graphs. Specifically, we prove that under SETH for any $delta>0$, a $(frac2k-1k-delta)$-approximation algorithm for Diameter on directed unweighted graphs requires $m^{frackk-1-o(1)}$ time.

Cited in

(6)

• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
• Removing additive structure in 3SUM-based reductions
• Hardness of approximate diameter: now for undirected graphs
• Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
• Shortest paths in multimode graphs

This page was built for publication: Tight conditional lower bounds for approximating diameter in directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065286)