2
$\begingroup$

For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.

A $(1+\epsilon)$-approximating of APSP for a directed graph with edge weights in range $[1, M]$ can be found in $O(n^{\omega}/\epsilon \log(M/\epsilon))$, where $\omega$ is the matrix multiplication exponent ($\omega < 2.373$) [2]. Therefore, we have a $(1+\epsilon)$-approximating algorithm for radius with the same running time.

If we restrict our algorithm not to use matrix multiplication (intuitively, only combinatorial algorithms), then we have a (3/2)-approximation algorithm in time $O(n^{2.5})$ [3] (Theorem 3).

My questions are:

  1. Is there any other algorithm for approximating the radius in (dense) graphs?
  2. Is there any hardness results for approximating the radius in (dense) graphs?

[1] Abboud A, Grandoni F, Williams VV. Subcubic equivalences between graph centrality problems, APSP and diameter. In SODA, 2015, SIAM.

[2] Zwick U. All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In FOCS, 1998, IEEE.

[3] Roditty L, Williams VV. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, 2013, ACM.


Dense graph: a graph with no restriction on the number of edges, in contrary to a sparse graph which can have only a few edges.

Radius of a graph G = $min_{c\in V(G)} max_{v\in V(G)} dis(c, v)$

$\endgroup$
  • $\begingroup$ I thought the papers you cite prove lower bounds and tradeoffs for various ranges of approximation. Also, if one wants a 2-approximation in undirected graphs you can simply do Dijkstra's from any vertex. $\endgroup$ – Chandra Chekuri Jun 17 '17 at 15:12
  • $\begingroup$ The only lower bound for radius to the best of my knowledge is in the 3rd parer, and is for sparse graphs, not dense graphs. The methods are very different. The 2-approximation is trivial. Therefore, it's good only when we have a hardness result. And here, we have a better approximation algorithm for $O(n^{2.5})$ and no lower bounds. $\endgroup$ – Mohemnist Jun 17 '17 at 15:30
  • $\begingroup$ If we take a sparse graph and add a clique of size n to one of the nodes we don't change much other than making the graph dense. If the results in [3] hold for m that is super linear then you may get some hardness from that even in the dense case. $\endgroup$ – Chandra Chekuri Jun 17 '17 at 19:05
  • $\begingroup$ No you cannot! In [3] we have such a result: For graphs where the number of edges is $m = \tilde O(n)$, we cannot approximate the radius within a factor of $3/2-\epsilon$ in time $O(n^{2-\delta})$. As you can see the number of edges is not in the time complexity. Therefore, you cannot deduce anything for the dense case. $\endgroup$ – Mohemnist Jun 18 '17 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.