<p>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.</p>

<p>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 &lt; 2.373$) [2]. Therefore, we have a $(1+\epsilon)$-approximating algorithm for radius with the same running time.</p>

<p>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).</p>

<p>My questions are:</p>

<ol>
<li>Is there any other algorithm for approximating the radius in (dense) graphs?</li>
<li>Is there any hardness results for approximating the radius in (dense) graphs?</li>
</ol>

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

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

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

<hr>

<p>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.</p>

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

CC BY-SA 3.0
2017-06-17T15:12:22.693Z
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.
Chandra Chekuri
CC BY-SA 3.0
2017-06-17T15:30:34.553Z
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.
Mohemnist
CC BY-SA 3.0
2017-06-17T19:05:53.327Z
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.
Chandra Chekuri
CC BY-SA 3.0
2017-06-18T07:55:55.517Z
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.
Mohemnist
<graph-algorithms><approximation-algorithms><approximation-hardness><approximation><fine-grained>
Approximating the Radius of a (Dense) Graph
Mohemnist
# Approximating the Radius of a (Dense) Graph

(Asked by: username_0 on 2017-06-15)

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)$

**Tags:** graph-algorithms, approximation-algorithms, approximation-hardness, approximation, fine-grained

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 0 answers

