2
$\begingroup$

I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). 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?

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.

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?

$\endgroup$
  • 1
    $\begingroup$ Adding a constraint is not the same as adding another optimization goal. $\endgroup$ – Raphael Oct 27 '16 at 9:41
  • $\begingroup$ "maximum number of edges" is right there in the abstract. That means... the number of edges. I can see a possible ambiguity if "diameter" was not defined, but it is defined. (Also at the top of p. 2.) $\endgroup$ – j_random_hacker Oct 27 '16 at 9:45
  • 1
    $\begingroup$ They want the spanning tree having minimum weight among all spanning trees that have diameter at most $d$. (The "diameter at most $d$" constraint is the same kind of constraint as the constraint that the subgraph to find be a tree, or that it contain every vertex from the original graph -- it just limits the set of possible subgraphs to consider.) $\endgroup$ – j_random_hacker Oct 27 '16 at 9:49
  • $\begingroup$ @Raphael I confused the two, thinking this problem had two conflicting optimization goals, but they are not. $\endgroup$ – Teodorico Levoff Oct 27 '16 at 16:35
  • $\begingroup$ @j_random_hacker I understand! I overlooked the diameter definition on page 2. So we are only interested in an MST with at most $d$ diameter. 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? $\endgroup$ – Teodorico Levoff Oct 27 '16 at 16:38
3
$\begingroup$

The diameter 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 geodesic distance). The measure that you choose depends on your particular application. In the paper that you mention, the authors focus on geodesic distance.

When you want to obtain a Minimum Spanning Tree (MST), you focus on edge weights because all spanning trees have the same number of edges: $|V|-1$.

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 the MST problem. 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).

To gain further insight into the notion of diameter (in the context of MSTs), consider the following example:

Example of DCMST

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

$\endgroup$
  • $\begingroup$ This makes much more sense. So the only thing we are optimizing is a minimum spanning tree and the diameter is a constraint? The geodesic distance is just 1 for each edge then? and the MST we consider the weights of the edge ofcourse? I asked a previous question(cs.stackexchange.com/questions/64791/…) and referring to the first diagram in your answer, the left most diagram would be the correct MST for this problem and not the right? Perhaps, you could use that diagram here? $\endgroup$ – Teodorico Levoff Oct 27 '16 at 16:33
  • $\begingroup$ The DCMST optimization problem is about finding an MST with the additional constraint that the diameter must be $\leq d$. Weights, of course, matter when calculating an MST. $\endgroup$ – Mario Cervera Oct 27 '16 at 19:24
  • $\begingroup$ I added an example. Note that, unlike in my other answer, I am ignoring weights when talking about the diameter. $\endgroup$ – Mario Cervera Oct 27 '16 at 19:24
  • $\begingroup$ Because in the previous answer, we say the diameter was a sum of the weights of those edges right? $\endgroup$ – Teodorico Levoff Oct 27 '16 at 21:05
  • $\begingroup$ Correct. In the other question, you didn't specify how to measure the diameter. $\endgroup$ – Mario Cervera Oct 27 '16 at 21:17

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.