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?