Understanding the Diameter Constrained MST Problem - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-19T13:08:41Z https://cs.stackexchange.com/feeds/question/65177 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/65177 2 Understanding the Diameter Constrained MST Problem Teodorico Levoff https://cs.stackexchange.com/users/29555 2016-10-27T04:24:48Z 2016-10-27T19:19:06Z <p>I am interested in understanding the DCMST problem, explained in this paper (<a href="http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf" rel="nofollow">http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf</a>). I don't think I understand it as I should. Here is how I understand it, we have a undirected connected graph $G=(V,E)$, a cost $c$ for every edge $e(i,j) \in E$ and a value $d$ we want to find an minimum spanning tree whose diameter is at most $d$. This paper say's that the diameter is of a tree is equal to the number of edges in the longest path between any pair of its nodes. Does this mean that the cost or weight of the edges are not considered when computing the diameter, in other words the weights do not add any meaning for the diameter? To compute the diameter we treat every edge as constant $1$? But I would assume the weights have meaning for the MST? Also, what are we minimizing here, the spanning tree or the diameter, because I don't think it can be both? </p> <p>Clearly, I am misunderstanding something here. Could someone explain this problem in more detail? I've been cracking my head with this problem for some days now.</p> <p>For example if we find an MST with $k$ diameter less than $d$ , and a spanning tree with a lower diameter than k but it's total weight is greater then the MST we found prior, the correct solution would be the MST because it is most minimum and the diameter constraint is satisfied, and does not need to be the most minimum diameter? or which is the correct solution and why? </p> https://cs.stackexchange.com/questions/65177/-/65183#65183 3 Answer by Mario Cervera for Understanding the Diameter Constrained MST Problem Mario Cervera https://cs.stackexchange.com/users/57681 2016-10-27T09:41:53Z 2016-10-27T19:19:06Z <p>The <strong>diameter</strong> of a graph is the longest shortest-path distance over all pairs of vertices. This distance can be measured in terms of edge weights or in terms of number of edges (which is known as <a href="https://en.wikipedia.org/wiki/Distance_(graph_theory)" rel="nofollow noreferrer">geodesic distance</a>). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance.</p> <p>When you want to obtain a <strong>Minimum Spanning Tree</strong> (MST), you focus on edge weights because all spanning trees have the same number of edges: $|V|-1$.</p> <p>Aiming for an MST that is constrained by a maximum diameter is perfectly possible. The authors of the paper are not setting two conflicting optimization goals, but, rather, just adding an additional constraint to <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow noreferrer">the MST problem</a>. Adding this contraint, however, turns the MST problem into an NP-Hard problem (even though computing the diameter of a graph and obtaining an MST, separately, are problems that can be solved in polynomial time).</p> <p>To gain further insight into the notion of diameter (in the context of MSTs), consider the following example:</p> <p><a href="https://i.stack.imgur.com/qkeQE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qkeQE.png" alt="Example of DCMST"></a></p> <p>The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total weight (i.e., the sum of the weights of its edges) is 7 and its diameter is 5 (because the vertices that are farthest from each other are 5 edges apart). If we add the constraint that the diameter must be at most 2 (that is, $d=2)$, then the diameter-constrained MST is the tree on the right. Its total cost is 12 (higher than the tree on the left), but it is the only spanning tree whose diameter (ignoring weights) is $\leq 2$. </p>