I have a digraph $G=(V,E)$. Suppose $G$ is strongly-connected, that is, every node is reachable from every other node. Suppose also that every edge has an associated weight $W$. I'm interested in an algorithm that identifies a set of edges $E'$ that satisfies the following conditions:

- Removing the edges in $E'$ from $E$ reduces the graph to a directed-acyclic-graph.
- The sum of the weights on edges in $E'$ is minimal.

Are there also heuristics for approximating a solution which would make the algorithm significantly faster?

**UPDATE 1**

Nathan Cohen requested more context about the graph so here's some details:

- Edge weights are all greater than zero and typed by C++'s "double" data type. This puts values in the range of (0, 1.7E308). However, 99% of edge weights fall in the range of (0, 10000)
- The graph may have hundreds of thousands of nodes.
- The average successor edge count of nodes is likely to be low (99% likely to be less than 20) though the distribution will be bias toward a minority of nodes with high out-going edge count.

From Kali's comment, I found this pager on "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" by G. Even, J. Naor, B. Schieber, M. Sudan which looks promising.

`springerlink.com`

is broken, but the article can be found at doi:10.1007/PL00009191 (Zbl 0897.68078). $\endgroup$