CODEWITHSUNDEEP
algorithmtree
Yu Zhang
Yu Zhang

Reputation: 13

How do you determine whether a graph G has a spanning tree of weight k?

given k, a positive integer, and a connected graph G=(V, E), each e of E has a weight w(e), can anyone come up with an algo to determine if G has a spanning tree of weight k?

Upvotes: 0

Views: 1068

Answers (1)

ruakh
ruakh

Reputation: 183504

Your problem is NP-hard. We can show this by reduction from the following formulation of the subset sum problem:

Given the […] natural numbers w1, …, wn, does any subset of them sum to precisely W?

To wit, suppose that we have an algorithm for solving your problem. We can then solve the subset sum problem (in the formulation above) by creating a graph G consisting of the following:

  • vertices v1, …, vn corresponding to the elements of the set, plus two special vertices x and y.
  • an edge from x to each vi, with weight wi.
  • an edge from y to each vi, with weight 0.
  • an edge from x to y, with weight 0.

The original set has a subset with sum W if and only if your algorithm returns "yes" for graph G and k = W.

To see why:

  • If your algorithm returns "yes", then there is a spanning tree with weight W, meaning that the edges in the spanning tree add up to W. But the nonzero edge-weights are all distinct elements in the set, so this means we have a subset that sums to W.
  • Conversely, if there is a subset that sums to W, then we can construct a spanning tree with weight W by taking the edges from x to the vertices corresponding to that subset, plus the (zero-weight) edges from y to all other vertices, plus the (zero-weight) edge from x to y.

Of course, NP-hardness doesn't mean you can't do it. It just means that there's no known algorithm that's correct and efficient for all possible inputs.

One inefficient algorithm is to generate all possible spanning trees, and see if any of them have the correct weight.

You can also check some likely cases more efficiently; in particular, you can use Kruskal's algorithm to find the minimal spanning tree, and (with slight modification) to find the maximal spanning tree. This will let you quickly eliminate any k outside the range of possible spanning tree weights.

Another possible way to eliminate many values of k is to use some of the algorithms for subset sum problems (at the Wikipedia article I linked to above) in order to determine whether the graph has any subgraph with weight k.

Upvotes: 3

Related Questions