Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized - MathOverflow

Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized

2011-04-29T21:46:27Z

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?

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.

Answer by Nathann Cohen for Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized

2011-04-30T16:04:43Z

The graph library of Sage solves this problem through linear programming. I don't know how large the instance you want to work on are, but I think it's worth a try :-)

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_edge_set

Nathann

Answer by andras frank for Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized

2011-05-22T19:12:25Z

If the digraph is planar, there is a (strongly) polynomial algorithm for the min-cost version, because in this case, by taking the planar dual, we arrive a min-max theorem of Lucchesi and Younger and there is an algorithm for its weighted version of Lucchesi-Younger even for non-planar digraphs.

Andras Frank

p.s. If one is interested in details, I can give a pointer to localize the algorithm.