Algorithm (MST, Prim's Algo, Kaskal's Algo)

Consider a connected, undirected, weighted graph G = (V, E, w), along with a single given hub node v V . A hub node is a vertex which has high degree, e.g., deg(v) |V |/2.

In general, an MST of G may contain an arbitrary number of edges which are incident to v. Instead, we want to find a minimum hub-independent spanning tree, defined as a spanning tree which uses at most two edges incident to v, and has weight less than or equal the weight of all other such spanning trees. Give an algorithm that solves this problem in O(E lg V + V 2 ) time.

1.. Note that for some input graph G and hub vertex v, it may be impossible to construct a spanning tree using only two edges incident to v. Find example of such a graph and hub vertex.

2.. Find example of a graph G and hub vertex v for which the spanning tree described above exists and is not an MST. Identify the minimum hub-independent spanning tree and an MST.

3.. Let K5 be the complete graph on 5 vertices and v be a fixed vertex. Assign weights to this graph such that any minimum hub-independent spanning tree has exactly two edges incident on v.