Subset of vertices

Question

I have a homework problem and i don't know how to solve it. If you could give me an idea i would be very grateful.

This is the problem: "You are given a connected undirected graph which has N vertices and N edges. Each vertex has a cost. You have to find a subset of vertices so that the total cost of the vertices in the subset is minimum, and each edge is incident with at least one vertex from the subset."

Thank you in advance!

P.S: I have tought about a solution for a long time, and the only ideas i came up with are backtracking or an minimum cost matching in bipartite graph but both ideas are too slow for N=100000.

Answer 1

This may be solved in linear time using dynamic programming.

A connected graph with N vertices and N edges contains exactly one cycle. Start with detecting this cycle (with the help of depth-first search).

Then remove any edge on this cycle. Two vertices incident to this edge are u and v. After this edge removal, we have a tree. Interpret it as a rooted tree with the root u.

Dynamic programming recurrence for this tree may be defined this way:

• w₀[k] = 0 (for leaf nodes)
• w₁[k] = vertex_cost (for leaf nodes)
• w₀[k] = w₁[k+1] (for nodes with one descendant)
• w₁[k] = vertex_cost + min(w₀[k+1], w₁[k+1]) (for nodes with one descendant)
• w₀[k] = sum(w₁[k+1], x₁[k+1], ...) (for branch nodes)
• w₁[k] = vertex_cost + sum(min(w₀[k+1], w₁[k+1]), min(x₀[k+1], x₁[k+1]), ...)

Here k is the node depth (distance from root), w₀ is cost of the sub-tree starting from node w when w is not in the "subset", w₁ is cost of the sub-tree starting from node w when w is in the "subset".

For each node only two values should be calculated: w₀ and w₁. But for nodes that were on the cycle we need 4 values: w_i,j, where i=0 if node v is not in the "subset", i=1 if node v is in the "subset", j=0 if current node is not in the "subset", j=1 if current node is in the "subset".

Optimal cost of the "subset" is determined as min(u_0,1, u_1,0, u_1,1). To get the "subset" itself, store back-pointers along with each sub-tree cost, and use them to reconstruct the subset.