Abstract

The radius and diameter are fundamental graph parameters, with several natural definitions for directed graphs. All versions can be solved via reduction to all-pairs shortest paths (APSP). 

However, solving APSP on $n$ node subgraphs requires $\Omega(n^2)$ time, even in sparse graphs. When can radius and diameter in sparse graphs be solved in truly subquadratic time, and when is such an algorithm unlikely?

Using the Orthogonal Vectors conjecture, and a new differently-quantified variant we present as the Hitting Set conjecture, we give inapproximability results for truly subquadratic algorithms. Motivated by these conditional lower bounds, we also find truly subquadratic algorithms with matching approximation guarantees for most versions. For example, there is a $2$-approximation algorithm for directed Radius with one-way distances that runs in $\tilde{O}(m\sqrt{n})$ time, while a $(2-\delta)$-approximation algorithm in $O(n^{2-\eps})$ time is unlikely.

Using these conjectures, we can also rule out an $(3/2-\delta)$ approximation algorithm for any version that runs on graphs of treewidth $k$ in $2^{o(k)}n^{2-\eps}$ time, while all versions can be solved in $2^{O(k\log{k})}n^{1+o(1)}$ time. This shows an interesting tradeoff between the dependence on k and the polynomial factor of an FPT algorithm, and serves as a first result for our Fixed Parameter Tractability in P framework.

Video Recording