CODEWITHSUNDEEP
algorithmgraphgraph-algorithmminimum-spanning-treedegrees
besad
besad

Reputation: 109

Minimal spanning tree with degree constraint

I have to solve this problem:

Given a weighted connected undirected graph G=(V,E) and vertex u in V. Describe an algorithm that finds MST for G such that the degree of u is minimal; the output T of the algorithm is MST and for each another minimal spanning tree T' being the degree of u in T less than or equal to the degree of u in T'.

I thought about this algorithm (after some googling I found this solution for similar problem here):

EDIT:

I understood that this algorithm may get a wrong MST (see @AndyG comment) so I thought about another one:

This solution is based on the fact that Kruskal's algorithm iterate the edges ordered by weigh, so the difference between all the MSTs of G is each edge was chosen from among all edges of the same weight. Therefore, if we increase the degree of the adjacent edges of u, the algorithm will choose the others edges in the same degree and not the adjacent of u unless this edge is necessary for the MST and the degree of u will be the minimal in all the MSTs of G.

I still don't know if it works and how to prove the correctness of this algorithm.

I will appreciate any help.

Upvotes: 2

Views: 2022

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58201

To summarize the suggested algorithm [with tightened requirements on epsilon (which you called x)]:

  • Pick a tiny epsilon (such that epsilon * deg(u) is less than d, the smallest non-zero weight difference between any pair of subgraphs). In the case all the original weights are natural numbers, epsilon = 1/(deg(u)+1) suffices.
  • Add the epsilon to the weights of all edges incident to u
  • Find a minimal spanning tree.

We'll prove that this procedure finds an MST of the original graph that minimizes the number of edges incident to u.

Let W be the weight of any minimal spanning tree in the original graph.

First, we'll show every MST of the new graph is an MST of the original graph. Any non-MST in the original graph must have weight at least W + d. Any MST in the new graph must have weight at most W + deg(u)*epsilon (since any MST in the original graph has at most this weight in the new graph). Since we chose epsilon such that deg(u)*epsilon < d, we conclude that any MST in the new graph is also an MST in the original graph.

Second, we'll show that the MST of the new graph is the MST of the original graph that minimizes the number of edges incident to u. An MST, T, of the original graph has weight W + k * epsilon in the new graph, where k is the number of edges of T incident to u. We've already shown that every MST of the new graph is also an MST of the original graph. Therefore, the MST of the new graph is the MST of the original graph that minimizes k (the number of edges incident to u).

Upvotes: 2

Related Questions