4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If the MST is unique, then it is indeed correct to say there there is no other MST with smaller diameter. $\endgroup$ – Yuval Filmus Oct 18 '16 at 19:46
  • $\begingroup$ If it isn't unique and there exist multiple MSTs, are you suggesting the diameters can vary? I'm trying to wrap my head around it. $\endgroup$ – Teodorico Levoff Oct 18 '16 at 21:21
  • 2
    $\begingroup$ Definitely. If it the MST isn't unique the diameter can vary. A lot. I gave an extreme example in my answer. $\endgroup$ – Yuval Filmus Oct 18 '16 at 22:02
7
$\begingroup$

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

Two examples of spanning trees with different diameters

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$):

Two examples of minimum spanning trees with different diameters

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).

$\endgroup$
  • $\begingroup$ To solve MDST problem with your first graph then the spanning tree on the top right would be the solution and not the one on the top left even though it is a MST? $\endgroup$ – Teodorico Levoff Oct 19 '16 at 5:07
  • 1
    $\begingroup$ Exactly. If you are looking for the Minimum-Diameter (not minimum total cost) Spanning Tree (MDST), then the solution is the graph on the right because it is not possible to find a spanning tree with diameter lower than 4. $\endgroup$ – Mario Cervera Oct 19 '16 at 6:50
8
$\begingroup$

Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.

$\endgroup$
  • $\begingroup$ I am interested in a graph where edges can have different weights/costs. I not understanding your answer very clear. $\endgroup$ – Teodorico Levoff Oct 18 '16 at 19:44
  • $\begingroup$ Well, unfortunately you haven't specified that requirement. It complicates the counterexample, but I would imagine that the conclusion would be similar. $\endgroup$ – Yuval Filmus Oct 18 '16 at 19:45
  • $\begingroup$ Ah! My apologies. I was looking for some paper or something that clearly addresses this with certainty but could not find any. $\endgroup$ – Teodorico Levoff Oct 18 '16 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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