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.
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$?
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.
