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?
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.