CODEWITHSUNDEEP
graphgraph-algorithmminimum-spanning-treekruskals-algorithm
user1767774
user1767774

Reputation: 1825

A minimum spanning tree that minimizes the degree of a specific node

How can we find the minimum spanning tree that minimizes the degree of a node v (among all minimum spanning trees)?

Would modifying Kruskal algorithm such that if there are several edges with the same weight we choose the one that doesn't touch v solve the problem?

Upvotes: 2

Views: 667

Answers (1)

Codor
Codor

Reputation: 17595

To answer the question in part, modifiying Kruskal's algorithm as sketched in the question does not solve the problem. Consider the graph G=(V,E,w) where

V = {1,2,3},
E = {{1,2}, {2,3}, {3,1}},
w({1,2}) = 1,
w({1,3}) = 1,
w({2,3}) = 2

and 1 is the node of which the degree in the minimum spanning tree is to be minimized. Then, the edge set

S1={{1,2},{1,3}}

constitutes a minimum spanning tree of weight 2. However, the modified version of Kruskal's algorithm would without loss of generality select edge {1,2} which would result in {1,3} being forbidden, such that {2,3} is selected. In total, in the selected edge set

S2={{1,2},{2,3}}

the node 1 has lesser degree than in S2, but the total weight of S2 is 3, which means that it does not constitute a minimum spanning tree.

Furthermore, note that the degree of the node v which is to be minimized has to be at least 3 to have the possibility of more than one neighbourhood of v in minimum spanning trees.

In an exhaustive search, select any possible neighbourhood of v. As v has at most n neighbors, there are at most 2^n such neighbourhoods. Using the algorithm by Prim, expand each of these to a spanning tree which is cost-minimal with respect to containing the selected neighborhood of v; in all these solutions which are cost-minimal, select one in which the degree of v is minimized. However, the approach does not yield a polynomial-time algorithm.

Upvotes: 1

Related Questions