Minimal spanning tree with degree constraint

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?

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

• It seems to me that in that case the $k$ edges of least cost out of the "root" must be part of the tree, start e.g. Kruskal with those edges pre-selected. Mar 18 '14 at 23:14
• @vonbrand The OP's example is a counter example.
– mrk
Mar 19 '14 at 1:07
• Here is a starting optimization: Focus on an edge $(1,u)$. Let $w$ denote the weight of this edge. Suppose there is a path from $1$ to $u$ not traversing this edge such that every edge in the path has weight $< w$. Then, we can delete the edge $(1,u)$ from the graph, without loss of generality, since no MST can contain the edge $(1,u)$. Thus, you could start by iteratively deleting such edges from the graph until there are no more that you can delete. This might reduce the number of edges out of vertex $1$.
– D.W.
Mar 19 '14 at 2:45
• Is this a practical problem or a theory/algorithms problem? If it is a practical problem, one approach that doesn't require much thought might be to use the ILP sledge hammer. Of course there is no guarantee this will run in polynomial time, but for small or medium sized graphs, it might be OK.
– D.W.
Mar 19 '14 at 17:07

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.

• Nice algorithm! Do you see any sketch of an idea that might allow a proof of correctness?
– D.W.
Mar 19 '14 at 17:14
• @D.W. I'd say induction with $k=m$ as the base case should be pretty straightforward. In each step we would get a worse spanning tree (or none) if we added or removed a different edge. Mar 19 '14 at 23:00

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.

• @D.W. I mean $\sum_{i=1}^k {d \choose i}$. Thanks for pointing out.
– mrk
Mar 19 '14 at 12:46

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.

• If I understood your idea correctly, it won't work with my example. After picking the lowest edges we will have (1,2) and (1, 6) (or (1, 5) and (1,6)), and (1,5) (or (1,2)) is allowable, according to your algorithm, so the answer will be 41. Mar 19 '14 at 7:53
• @user3670, good point. You are right, of course. My algorithm does not work. Thank you!
– D.W.
Mar 19 '14 at 17:07