How to find feedback edge set in undirected graph

Question

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 1

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.

Answer 2

To find a minimum-weight feedback edge set in a weighted digraph with positive weights:

By negating the weights, observe that it is equivalent to finding the maximum-weight feedback edge set. To find a maximum-weight feedback edge set, build an MST using either Prim's or Kruskal's algorithm. Then take the complement of that MST.

Why does it work? This is based on the following observation:

An edge is not in any MST if and only if there exists a cycle for which that edge has the maximum weight over all other edges in that cycle. Or, in other words, an edge is in some MST if and only if for every cycle to which that edge belongs, it is not of maximum weight over all other edges in that cycle.

Indeed, assume we have a maximum-weight feedback edge set with an edge such that there exists a cycle comprising that edge and another edge with greater weight, then replacing that edge with this other edge would provide a feedback edge set of greater weight.

For completeness, a proof of the observation:

<=) Suppose an edge has the maximum weight in a cycle. If it were in some MST, then replacing that edge with another edge from that cycle would provide an MST with smaller weight.

=>) Suppose that for every cycle to which a given edge belongs, there exists an edge with greater weight in that cycle. If it is not in any MST, then adding that edge to an MST would cause a cycle in an MST. Then removing the edge of maximum weight from that cycle (which is different from the given edge) would provide an MST with smaller weight (and comprising that given edge).