<p>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.</p>
<p>If we have a rooted tree <span class="math-container">$T = (V,E)$</span> with root <span class="math-container">$r$</span>, I first label the edges of the tree in the following way:</p>
<p>Starting from the root (let's say it has degree <span class="math-container">$d$</span>), we will label the edges going to its subtrees <span class="math-container">$T_1, \ldots, T_d$</span> 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 <span class="math-container">$\{1,2 \ldots, $</span>d<span class="math-container">$\}$</span> 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 <span class="math-container">$d$</span> goes into the smallest subtree.</p>
<p>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.</p>
<p>Given this labeling, if I look at a vertex <span class="math-container">$v$</span> 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.</p>
<p>The total cost of the tree is the sum of the costs of its vertices. Let us call the cost of a tree <span class="math-container">$\phi(T)$</span>.</p>
<p>My goal is to come up with an algorithm for this problem: Given a general graph <span class="math-container">$G$</span>, and root node <span class="math-container">$r$</span>, find a spanning tree of <span class="math-container">$G$</span> which minimizes <span class="math-container">$\phi(T)$</span>.</p>

CC BY-SA 4.0
2021-03-22T17:54:42.980Z
Do you know the answer for the case where the input graph $G$ is a clique?
Gamow
CC BY-SA 4.0
2021-03-23T04:09:24.510Z
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.
Karagounis Z
CC BY-SA 4.0
2021-03-23T20:09:49.543Z
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 https://en.wikipedia.org/wiki/Binomial_heap.
Karagounis Z
CC BY-SA 4.0
2021-03-24T09:55:57.833Z
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.
Gamow
CC BY-SA 4.0
2021-03-24T10:18:02.030Z
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)
Gamow
CC BY-SA 4.0
2021-05-12T20:42:44.663Z
In your problem specification, is the root specified in the input?
Neal Young
CC BY-SA 4.0
2021-05-13T05:26:41.023Z
I don't think it matters too much, since we could try all possibilities for the root. But let us say that a root node is specified in the input (I edited the post).
Karagounis Z
<ds.algorithms><graph-theory><graph-algorithms><co.combinatorics><optimization>
Minimum spanning tree, but with an unusual objective function
Karagounis Z
# Minimum spanning tree, but with an unusual objective function

(Asked by: username_0 on 2021-03-22)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, co.combinatorics, optimization

> **Comments:**
> **username_1**: Do you know the answer for the case where the input graph $G$ is a clique?  
> **username_0**: username_1, 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.  
> **username_0**: Hi username_1, 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 https://en.wikipedia.org/wiki/Binomial_heap.  
> **username_1**: 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.  
> **username_1**: 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)  
> **username_2**: In your problem specification, is the root specified in the input?  
> **username_0**: I don't think it matters too much, since we could try all possibilities for the root. But let us say that a root node is specified in the input (I edited the post).  

---

## 0 answers

