5
$\begingroup$

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$, and root node $r$, find a spanning tree of $G$ which minimizes $\phi(T)$.

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you know the answer for the case where the input graph $G$ is a clique? $\endgroup$
    – Gamow
    Mar 22, 2021 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, 2021 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, 2021 at 20:09
  • 1
    $\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, 2021 at 9:55
  • 1
    $\begingroup$ In your problem specification, is the root specified in the input? $\endgroup$
    – Neal Young
    May 12, 2021 at 20:42

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.