[Solved]: Diameter-constrained Minimum Spanning Tree Problem

Problem Detail: 

The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of edges between vertices, and a constant $d$. The goal is to find an MST such that the diameter (i.e., the maximum distance of the shortest paths between vertices) of the MST is at most $d$. My question is that I am debating whether the following is true or not:

Once you have an MST of a graph $G$, if the diameter of the MST is $>d$, then is it true to say that there exist no feasible solution.

Also, once you have a MST of $G$, then is the diameter of that MST the maximum diameter of $G$? or minimum? or what could be said about the diameter of a MST?

Asked By : Teodorico Levoff

Answered By : Mario Cervera

There is no direct relationship between the diameter of a (minimum) spanning tree and the total cost of the tree¹. Consider the following example:

The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total cost is 7 and the diameter is equal to 5. In contrast, the spanning tree on the right is not minimum (since its total cost is 12), but it has a smaller diameter: 4.

The same situation may occur when two spanning trees are minimum, as suggested by Yuval. Consider the following example (for the complete graph $K_4$):

In this case, the total cost of the two Minimum Spanning Trees (MST) is 3; however, the MST on the left has a diameter that is equal to 3, while the MST on the right has a smaller diameter: 2.

This counter-example disproves your assumption:

It is, indeed, possible to find two different MSTs $T$ and $T'$ whose diameters are $\gt d$ and $\leq d$, respectively, within the same weighted undirected graph $G$.

---

_{1. Note that Minimum-Diameter Spanning Trees (MDST) can be found in polynomial time, but the problem becomes NP-Hard when we also want the MDST to be minimum (i.e., when we want the total cost of the tree to be minimized).}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64791

3.2K people like this

 Download Related Notes/Documents