# About the 'trick' for finding the diameter of an graph in $O(n^2)$

The diameter of an undirected, unweighted graph can be found in $O(n^3)$ with e.g. the Floyd–Warshall algorithm. However, there is an idea how to improve the runtime:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

This idea fails; for instance, when starting at $v$ here: However, it is not immediately clear to me if we can not amend the above algorithm with another indirection, and also consider all nodes with maximum distance instead of only one. That is:

1. Pick a vertex $v$
2. Find the set $U$ such that $u \in U \implies d(v,u)$ is maximum
3. For each node $u$ in $U$, find the set $W_u$ such that $w \in W \implies d(u,w)$ is maximum
4. Merge these sets $W_u$ into a new set $W$
5. Calculate the eccentricity of all nodes in $W$
6. Return the maximum eccentricity found this way

The improved algorithm works for the above counterexample as well as others (e.g. this one).

I assume it is still wrong. If it were not, it would offer a significant improvement for at least some kinds of graphs. Is there a counterexample? And how could a counterexample for further additional indirections be constructed?

The diameter of the following graph is $2a+4$. If you start from $v$, you will need $i=2a+1$ iterations to have $s,t\in W_{i}$. It provides a family of counter-examples for an arbitrary large number of indirections (as $a \to \infty$). • Nice example! If I am not mistaken, the second set should contain not only v but also the two nodes below v, because they, too, have maximum distance from x and y, respectively. In a following indirection, the nodes besides x and y would then also be included, so the set grows and the algorithm would eventually discover s and t. However, that would take several steps, more than I proposed.
– mafu
Dec 5 '17 at 18:39
• I made a mistake - actually, in the example given, s and t would be discovered, as their distance to the nodes below v is 5, too. That can be fixed by making the sides a bit longer, so your idea still applies.
– mafu
Dec 5 '17 at 18:44
• @mafu: Hmmm yes, nice catch, I updated the picture. There might be off-by-one errors, but I think you got the idea.
– md5
Dec 5 '17 at 19:32