# Approximating the diameter of graph G

Anyone has an idea how to solve this problem:

Let G be an undirected, unit-weighted connected graph. Design a linear-time algorithm to obtain a 2-approximation of the diameter of G. I.e., the largest shortest-path distance between a pair of vertices of G.

I thought about running BFS from an arbitrary node, in the worst case it should be half of the graph diameter (radius), but how can I prove it?

Thanks.

• I suppose it must be linear in the edges number, not in the vertices number. Hint : How can you compare the diameter and the longest shortest-path between an arbitrary fixed vertex and all vertices ? – François Apr 5 '15 at 17:14
• @FrançoisG., yeah, it's linear in the total representation size - $\Theta(n+m)$. – Luke Mathieson Apr 6 '15 at 1:50
• I have to say, it seems pretty clear what's being asked, despite the votes to close. Here's a hint: let $L$ be the length of a maximum shortest path from an arbitrarily chosen vertex and $D$ the diameter. Show that $L\le D\le 2L$. – Louis Apr 6 '15 at 7:49
• Now that there is a specific question. Try to prove what I said in the hint by using the fact that in your setup the graph metric has the triangle inequality. – Louis Apr 7 '15 at 8:34

Constructing a breadth-first tree is the correct way to go. This gives you the running time of $\Theta(n+m)$ where $n$ is the number of vertices and $m$ the number of edges respectively.
One of the central facts needed is that a breadth-first tree $T$ rooted at vertex $r$, in an [undirected,] unweighted (equivalent to unit weight) graph $G$ is also a shortest path tree. That is, for every vertex $v$, the length of the shortest path between $r$ and $v$ in $G$ is equal to the length of the path from $r$ to $v$ is $T$.
So we pick (arbitrarily) a starting vertex $r$, and construct our tree $T$. What does this tell us about the diameter of $G$?
• If $v$ is the furthest vertex from $r$ in $T$ (and hence in $G$), at distance $d(r,v)$ then $d(u,w) \leq 2\cdot d(r,v)$.
Thus the length of the longest shortest path is between $d(r,v)$ and $2\cdot d(r,v)$. That is, the diameter $D$ is at least $d(r,v)$, thus $2\cdot D \geq 2 \cdot d(r,v)$. Which gives our factor two approximation.
You can make it a little tighter (sort of) and take the two longest distances $D'$ and $D''$ from $r$ in $T$. Without loss of generality assume $D' \leq D''$. Then $D'' \leq D \leq D'+D'' \leq 2\cdot D''$. The worst case is that $D' = D''$, so we don't prove anything further though.