Mina Dalirooyfard, Massachusetts Institute of Technology

Abstract

There are only two sub-quadratic approximation algorithms known for directed diameter: a linear time 2 approximation and a O(n^3/2) time 3/2 approximation. Only the latter is proved to be optimal: Roditty and Williams (STOC'13) proved that any 3/2-e approximation requires m^{2-o(1)} time, And Backurs et al (STOC'18) showed that any 5/3-e approximation requires m^{3/2-o(1)} time (recently Li showed the same result for undirected graphs).

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-e 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 e>0, any (2k-1)/k-e approximation algorithm for Diameter on directed unweighted graphs requires m^{k/(k-1)-o(1)} time. 

joint work with Nicole Wein, to appear in STOC '21.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home