Finding a Spanning Tree with a Target Cost

I'm quite stumped on this one. New to posting, so forgive me if this is a silly question.

Say we are given a graph G=(V,E) with weighted edges. I would like to create spanning tree of G with a target cost of c, where a spanning tree's cost is defined as the sum of all its edge costs. How do we determine if there exists a spanning tree of G 开发者_Go百科with cost c?

Here's a stab at it. You can use dynamic programming to solve the subset sum problem then for each possible subset just check if it forms a spanning tree. The general formulation of subset sum goes: let C[i,S] be the boolean value of the statement

There is a subset of S that sums to i

Let e be an arbitrary edge. Then the recurrence usually goes:

C[i,S' U e] = true iff C[i, S'] or C[i - weight(e), S']

(you either use edge e or you don't and make sure that using the edge e doesn't forms a cycle).

If the target cost is c then you need to perform n sweeps for each 1 <= i <= c where n is the number of edges.

Finally verify that the number of edges picked is 1 less than the number of vertices and they are all connected.

The other approach is to just use backtracking recursion to search all spanning trees <= targetCost.