Minimum k-spanning tree including a given node

1.2k Views Asked by At

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm.

A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard.

However, the problem at hand requires that a given node is present in the tree. Does this extra requirement make it easier or harder? How should I solve this?

Formally, given a graph G = (V, E), one must find the tree with K nodes, with minimum weight, and in which the node v is present, for a given v.

1

There are 1 best solutions below

5
On

I think the extra requirement does not make the problem any easier to solve than the k-minimum spanning tree. If you could solve it in polynomial time $p(n)$, where $n$ is the number of nodes, then you could simply solve it for every one of the $n$ nodes and take the solution that has minimum weight, this solving the $k$-minimum spanning tree in $n\cdot p(n)$, which is still polynomial.