I have a graph, G, with nodes, N, and edges, 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.