Minimal spanning tree with degree constraint

Question

I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of minimal spanning tree in which the degree of vertex 1 is at most $k$ (we don't care about other vertices' degrees). We can assume that such a tree exists.

Can someone give an idea how to approach the solution?

What I've already tried:

1) I know how to find essential edges from vertex 1. We can use dfs and start from a random edge of vertex 1. When we return to vertex 1 we can check if this edge (another vertex 1 edge) has lower weight than the previous one. If yes, than the previous one is not essential.

2) After that I wanted to use Kruskal's algorithm (adding in the beginning of the algorithm all essential edges). But the problem is that sometimes we should not take an edge with minimal weight to construct the required tree.

For example: 9-node undirected graph, $k = 3$

(vertex1 vertex2 weight)
1 2 1
2 3 5
3 4 6
4 5 7
5 1 1
1 6 1
6 7 8
7 8 9
8 9 10
9 1 2

So essentials will be (1,2) and (1, 6) (or (1, 5) and (1,6)). Kruskal will take (1,5) (or (1,2)) anyway. And the weight will be 41, but the correct answer is 39. So I don't know how to use Kruskal's algorithm here.

(The same example visualized, vertex 1 = vertex A)

I thought that we may construct a minimal spanning tree without constraints and after that try to transform it to the required one, but I don't know how to do this (how to transform without brute force).

Answer 1

As D.W. suggested, you can start as follows:

• Temporarily delete vertex $1$.
• For each of the resulting connected components $C_1, \dotsc, C_m$ find a MST, using e.g. Kruskal's or Prim's algorithm.
• Re-add vertex $1$ and for each $C_i$ add the cheapest edge between $1$ and $C_i$.
• If $m=k$, you are done.

If $m<k$, you can now do the following:

• For each edge $\{1,v_j\}$ not yet added, determine the most expensive edge on the path from $1$ to $v_j$ in the current tree. Call this edge $e_j$ and compute $d_j = \operatorname{cost}(e_j) - \operatorname{cost}(\{1,v_j\})$, the cost savings of replacing $e_j$ by $\{1,v_j\}$ in the spanning tree.
• Create a priority queue of the tuples $(v_j, e_j, d_j)$, ordered by decreasing value of $d_j$.
• As long as $\operatorname{deg}(1) < k$ and the first value $d_j > 0$, consider the first tuple from the proority queue:
  • If $e_j$ has already been removed, find the edge $e_j$ and the value $d_j$ corresponding to the current tree. Update the tuple and its position in the priority queue.
  • Otherwise replace $e_j$ by $\{1,v_j\}$ in the spanning tree and remove the tuple from the queue.

Finding $e_j$ can be done in ${\cal O}(n)$, using e.g. a modified DFS. This makes the second phase ${\cal O}(n^2)$. Since Prim's algorithm is ${\cal O}(n^2)$ as well, this is also the running time for the complete algorithm.

Answer 2

One way to go is to try them all. 'them' meaning all $(\le k)$-subsets of edges connected to the root. You throw the other edges (connected to the root) away and run Kruskal then take the minimum over all of them. The number of times you invoke Kruskal is $\sum_{i=1}^k {d \choose i}$, where $d=\text{deg}(1)$. A terrible algorithm for large values of $k$ but it's correct.

Answer 3

I think the following might help a little bit:

Imagine deleting the vertex $1$ from the graph and all edges incident to vertex $1$, then decomposing the resulting graph into connected components. It's easy to see that we need at least one edge from vertex $1$ to each of those connected components.

Let the resulting connected components be $C_1,C_2,\dots,C_m$. If $m>k$, the problem is not solvable. If $m=k$, the problem is trivial: for each $i$, you pick the lowest cost edge between vertex $1$ and component $C_i$. If $m<k$, you have some more work to do. In this case, we want to pick $n_i$ edges from vertex $1$ to component $C_i$, subject to the restriction that $1 \le n_i$ for each $i$ and $n_1+n_2+\dots+n_m \le k$.

At this point, I think you might be able to run Kruskal's algorithm, but taking care to ensure that those constraints will be satisfied, i.e., to make sure you're not taking yourself into a dead end. At each step, you choose the lightest edge that's allowable. To test whether an edge is allowable, look at the forest $F$ that would result if you add it to the forest so far. In $F$, count up the number of edges out of vertex $1$ that are in $F$, and count the number of connected components that haven't yet been connected to vertex $1$ (by $F$); if that exceeds $k$, then the edge you were considering isn't allowable and must be skipped over (choosing it would leave you stuck in a dead end). Of course, as always in Kruskal's algorithm, any edge that would create a cycle is not allowable, either. I think this might work. It's your exercise, so I'll let you check the details.