How to find feedback edge set in undirected graph
Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F.
(a) Suppose that G is unweighted. Design an efficient algorithm to find a minimum-size feedback-edge set.
(b) Suppose that G is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.
My solution (need suggestions):
a) Minimum size feedback edge set: since the graph is unweighted, we can use DFS. We start DFS from any vertex as usual. When we encounter a back edge, we insert it into set of feedback edges. When DFS completes, the set will be the answer.
b) Minimum weight feedback edge set: since the graph is weighted, we can use Kruskal. But Kruskal normally starts with edge of smallest weight. If we can negate all edge weights, and then run Kruskal, whenever we get an edge between vertices of same component, we can save that in feedback edge set. In the end, negate edge weights. The reason I propose to negate edge weights is because we need minimum weight feedback set. With negated weights, Kruskal will start with edges with smallest weight (actually largest), and will find edges for same component with smaller weights.
Can someone tell if this solution is correct?
Answer
Yes, your solution is correct. Minimum-weight feedback edge sets of undirected graphs are complements of maximum-weight spanning forests. All spanning forests have the same cardinality, so in the unweighted case any spanning forest (as found by DFS) will do. (Proof sketch: matroids.)
Feedback arc set is indeed NP-hard, but this is the undirected case.