Subset of vertices

8
votes

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.

2
c++algorithm
Try to work out the solution yourself first of all. – Coding Mash
"N vertices and N edges" - is that correct? The same number of vertices and edges? That would mean the graph is a tree with one "extra" edge. – AnT
Yes "N vertices and N edges" is correct. – user1907615
en.wikipedia.org/wiki/Vertex_cover – AnT
Oh, yes. Note that the problem in the general case (not restricted to N edges) is vertex cover problem, a classic NP-Complete problem. However, my gut tells me it is not the case for the simpler problem. – amit

2 Answers

2
votes

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:

  • w0[k] = 0 (for leaf nodes)
  • w1[k] = vertex_cost (for leaf nodes)
  • w0[k] = w1[k+1] (for nodes with one descendant)
  • w1[k] = vertex_cost + min(w0[k+1], w1[k+1]) (for nodes with one descendant)
  • w0[k] = sum(w1[k+1], x1[k+1], ...) (for branch nodes)
  • w1[k] = vertex_cost + sum(min(w0[k+1], w1[k+1]), min(x0[k+1], x1[k+1]), ...)

Here k is the node depth (distance from root), w0 is cost of the sub-tree starting from node w when w is not in the "subset", w1 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: w0 and w1. But for nodes that were on the cycle we need 4 values: wi,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(u0,1, u1,0, u1,1). To get the "subset" itself, store back-pointers along with each sub-tree cost, and use them to reconstruct the subset.

1
votes

Due to the number of edges are strict to the same number of vertices, so it's not the common Vertex cover problem which is NP-Complete. I think there's a polynomial solution here:

  1. An N vertices and (N-1) edges graph is a tree. Your graph has N vertices and N edges. Firstly find the awful edge causing a loop and make the graph to a tree. You could use DFS to find the loop (O(N)). Removing any one of the edges in the loop would make a possible tree. In extreme condition you would get N possible trees (the raw graph is a circle).

  2. Apply a simple dynamic planning algorithm (O(N)) to each possible tree (O(N^2)), then find the one with the least cost.