0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 ? $\endgroup$
    – François
    Commented Apr 5, 2015 at 17:14
  • 1
    $\begingroup$ @FrançoisG., yeah, it's linear in the total representation size - $\Theta(n+m)$. $\endgroup$
    – Luke Mathieson
    Commented Apr 6, 2015 at 1:50
  • $\begingroup$ 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$. $\endgroup$
    – Louis
    Commented Apr 6, 2015 at 7:49
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Commented Apr 7, 2015 at 8:34

1 Answer 1

Reset to default
4
$\begingroup$

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

  • The diameter is the length of the longest shortest path, so any shortest path provides a lower bound for the diameter.
  • 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.