Subset of vertices

Question

I have a problem with homework 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 that has N vertices and N edges. Each vertex has a cost. You must find a subset of vertices so that the total cost of the vertices in the subset is minimal and each edge falls on at least one vertex from a subset.

Thank you in advance!

PS: I have been dealing with a solution for a long time, and the only ideas I came up with are backtracking or comparing the minimum cost on a two-way chart, but both ideas are too slow for N = 100000.

Answer 1

This can be enabled in linear mode using dynamic programming.

A connected graph with N vertices and N edges contains exactly one cycle. Start by discovering this cycle (using depth search).

Then remove any edge in this loop. Two vertices incident to this edge, u and v . After this edge removal we have a tree. Interpret it as a root tree with root u .

The repetition of dynamic programming for this tree can be defined as follows:

• 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 depth of the node (distance from the root), w ₀ is the cost of the subtree, starting with node w when w is not in the “subset”, w ₁ is the cost of the subtree, starting with node w , when w is in the “subset” "

For each node, only two values ​​must be calculated: w ₀ and w ₁ . But for the nodes that were in the loop, 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 the current node is not in the "subset", j = 1 if the current node is in the "subset".

The optimal cost of a "subset" is defined as min ( u _0,1 , u _1,0 , u _1,1 ). To get a "subset", save the back pointers along with each value of the tree tree and use them to restore the subset.

Answer 2

Due to the number of edges, the same number of vertices is strict, so this is not a common problem, the problem with the vertex , which is NP-Complete, I think there is a polynomial solution here:

• N vertices and (N-1) graph graph is a tree. Your graph has N vertices and N edges. First find the terrible edge creating the loop and make the graph a tree. You can use DFS to search for a loop ( O(N) ). Removing any of the edges in the loop would create a possible tree. In extreme condition, you will get N possible trees (an unprocessed graph is a circle).

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