Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

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. Suppose that G is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set (MWFES).

There is large discussion about this problem in another question in programmers forum: https://stackoverflow.com/questions/10791689/how-to-find-feedback-edge-set-in-undirected-graph The conclusion of that discussion is that MWFSE are those edges that remain in graph after removal of edges that belong to the maximum-weight spanning tree (which is minimum-weight spanning tree on the graph with reversed weights, those spanning trees can be found by Kruskal algorith in polynomial time).

I have found simple counterexample of such strategy, see in pic. This counterexample takes into account the case when one edge can belong to two cycles and it can be more benefitial to chose this common edge instead of choosing two edges with minimum weights. So, in this example MWFES clearly consists from the one edge with weight 7, but minimum spanning tree have edges 7+100+101 and that leaves edges 5 and 6 for the MWFES, but MWFES with those two edges is not minimal one.

So, are there non-NP hard algorithms for finding MWFES?

p.s. One comment in the cited question goes like this "Note that you can easily find minimal (not minimum) solutions". So - what is distinction between minimum and minimal in such problems. Is there such distinction at all?

Answer 1

If the weight function is non-negative, then the set of edges not contained in a maximum weight spanning tree is indeed a MWFES. But if the weight function is arbitrary, a MWFES will contain all the non-positive weight edges and then a MWFES can be computed for the remaining edges.

Here the proof of the non-negative case. Let $\mathcal{T}$ be a maximum weight spanning tree in G and $w$ the weight function. It can be shown first that there exists a MWFES without edges from $\mathcal{T}$, and then, to conclude, that a FES without edges from $\mathcal{T}$ must contain all the edges not in $\mathcal{T}$.

The proof of the first statement: First of all a FES always exists (all the edges from G are a FES). Let $\mathcal{F}$ be a MWFES in graph G, and suppose that it contains an edge $e\in\mathcal{T}$. We will show that there exists a FES not containing $e$ and with weight at most the weight of $\mathcal{F}$. Let $\mathcal{C}_e$ denote the set of cycles $C$ in G such that $C \cap \mathcal{F} = \{e\}$ (i.e. cycles containing $e$ and not any other edge from $\mathcal{F}$). Notice that we can assume $|\mathcal{C}_e| = 1$: if it is zero, then $\mathcal{F}\setminus \{e\}$ is a FES with weight at most the weight of $\mathcal{F}$; if it is at least $2$, then let $C_1, C_2 \in \mathcal{C}_e$, $C_1 \neq C_2$. $C_1 \bigtriangleup C_2$ is a cycle (or a family of disjoint cycles) not containing $e$, and by definition of $\mathcal{C}_e$, not containing any edge from $\mathcal{F}$, which is a contradiction because $\mathcal{F}$ is a FES. The cycle in $\mathcal{C}_e$ must contain an edge $e'\notin \mathcal{T}$ such that $w(e') \le w(e)$ (otherwise $\mathcal{T} \cup \{e'\} \setminus \{e\}$ for any $e' \notin \mathcal{T}$ in the cycle would be a spanning tree with strictly larger weight). Then $\mathcal{F} \cup \{e'\} \setminus \{e\}$ is also a FES with weight at most the weight of $\mathcal{F}$, and hence a MWFES. Iterating this argument, we can show that there exists a MWFES without edges from $\mathcal{T}$.

Finally, each fundamental cycle (cycle in $\mathcal{T} \cup \{e\}$ for each $e \notin \mathcal{T}$) must be covered by an edge from the FES, so a FES without edges from $\mathcal{T}$ must contain all the edges $e\notin \mathcal{T}$. This shows that the set of edges not in $\mathcal{T}$ are a MWFES.

I hope it is clear enough. Best regards!

Answer 2

It is explained in an easier way at https://softwareengineering.stackexchange.com/a/291621. Consider only positive weights, otherwise proceed as explained above. Further, assume only one component, you can otherwise apply it separately to each component.

You first prove that the graph minus the feedback set must be a tree T (if it is a minimum feedback set). Then, giving the sum of all weights W, the total weight of F is (W - sum of weights in T). Hence, this weight is minimal if we construct a tree T of maximum weight. That is, T must be a maximum spanning tree.