A feedback set of any undirected, weighted graph is a subset of edges such that after removing the edges in the subset, the remaining graph is acyclic.
Given G = (V, E), an undirected and weighted graph, and an integer k, how can I determine if there is a feedback set with total weight no more than k?
Thank you!
The minimum feedback set will never contain an edge that disconnects two components of the graph, so removing the feedback set will not change the connected components, but it will render each connected component acyclic.
If an undirected graph is connected and acyclic, then it's a tree, so:
For each connected component in the graph, find the maximum weight spanning tree. You can use any of the mininum-weight spanning tree algorithms just by negating all the weights.
The edges that aren't in any of the maximum weight spanning trees are a minimum weight feedback set.
To find all the maximum weight trees, I recommend using Kruskal's algorithm on the whole graph with edges sorted by descending weight, since it will find them all at once. Then just select all the edges that aren't in any tree.