# Minimum diameter spanning tree problem

Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $$G(V, E)$$, weight function $$w: E \rightarrow R, w(e) > 0\ \forall e \in E$$, find the spanning tree $$T(V, E')$$ of $$G$$ such as maximal distance between vertices in $$T$$ is minimal.

I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $$\Theta(n^3)$$ solution exists here, but no full solution is anywhere.

I believe this community would benefit if solution is described here.

• You may be interested by researchgate.net/publication/…. I did not read the full article but the authors claim that a $\Theta(n^3)$ solution stands when working in Euclidian plane. The general weighted graph problem would be NP-complete. Mar 20 '19 at 9:38
• @Vince Are you allowing for non-positive edge weights as well when you say it is NPC?
– Juho
Mar 20 '19 at 9:48

The answer is given in the paper that you link to. Specifically, there is a $$O(mn+n^2 \log n)$$-time algorithm for the problem (with positive edge weights, as required) that works as follows.
The absolute 1-center is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $$T(v)$$ a shortest path tree connecting $$v$$ to all vertices in $$V$$. It holds that $$T(a)$$ is a minimum diameter spanning tree of $$G$$, where $$a$$ is an absolute 1-center of $$G$$. Here, if the absolute 1-center is an edge, we subdivide it to obtain the vertex $$a$$ from which $$T(a)$$ is then computed from.
An absolute 1-center $$a$$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $$T(a)$$ is computed by any standard shortest path algorithm.