This is a problem that came up in my study of rumour networks. I was wondering if anyone had thoughts or references on this problem.

If we have a rooted tree $T = (V,E)$ with root $r$, I first label the edges of the tree in the following way:

Starting from the root (let's say it has degree $d$), we will label the edges going to its subtrees $T_1, \ldots, T_d$ in decreasing order of size. The size of a tree is the number of nodes it has. So for example, the edges incident on the root will receive labels in $\{1,2 \ldots, $d$\}$ such that the edge with label 1 goes to the largest subtree, the edge with label 2 goes into the second largest subtree etc, and the edge with label $d$ goes into the smallest subtree.

We then label the rest of the edges in a similar way, by treating each vertex as a root of its subtree and labeling its edges in decreasing order of size of the subtree below it.

Given this labeling, if I look at a vertex $v$ in the tree, consider its path to the root. The cost of this vertex is the sum of the labels of the edges along this path.

The total cost of the tree is the sum of the costs of its vertices. Let us call the cost of a tree $\phi(T)$.

My goal is to come up with an algorithm for this problem: Given a general graph $G$, find a spanning tree of $G$ which minimizes $\phi(T)$.

  • $\begingroup$ Do you know the answer for the case where the input graph $G$ is a clique? $\endgroup$ – Gamow Mar 22 at 17:54
  • $\begingroup$ Gamow, you asked a very good question. I don't know the answer even if $G$ is a clique, but that would probably be a good place to start. $\endgroup$ – Karagounis Z Mar 23 at 4:09
  • 1
    $\begingroup$ Hi Gamow, I've thought about it more and I have shown that if $G$ is a clique, the optimal tree is in the form of a binomial heap en.wikipedia.org/wiki/Binomial_heap. $\endgroup$ – Karagounis Z Mar 23 at 20:09
  • $\begingroup$ Then the next step should be to study the complexity of the following problem: "Given an undirected graph $G$, does it contain a spanning binomial heap?" If this is hard, your minimzation problem is also hard. If this is easy, you will at least gain some valuable insights. $\endgroup$ – Gamow Mar 24 at 9:55
  • $\begingroup$ The following paper might be relevant for you. Christos H. Papadimitriou, Mihalis Yannakakis: "The complexity of restricted spanning tree problems", Journal of the ACM 29:285-309 (1982) $\endgroup$ – Gamow Mar 24 at 10:18

Your Answer

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

Browse other questions tagged or ask your own question.