Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:29:31Z http://mathoverflow.net/feeds/question/63477 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63477/find-graph-cut-such-that-graph-becomes-a-dag-and-edge-weights-are-minimized Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized Grant 2011-04-29T21:46:27Z 2011-05-22T19:12:25Z <p>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:</p> <ol> <li>Removing the edges in E' from E reduces the graph to a directed-acyclic-graph.</li> <li>The sum of the weights on edges in E' is minimal.</li> </ol> <p>Are there also heuristics for approximating a solution which would make the algorithm significantly faster?</p> <p><strong>UPDATE 1</strong></p> <p>Nathan Cohen requested more context about the graph so here's some details:</p> <ul> <li>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)</li> <li>The graph may have hundreds of thousands of nodes.</li> <li>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.</li> </ul> <p>From Kali's comment, I found this pager on <a href="http://www.springerlink.com/content/xjyvlc3cjd3egada/" rel="nofollow">"Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" by G. Even, J. Naor, B. Schieber, M. Sudan</a> which looks promising.</p> http://mathoverflow.net/questions/63477/find-graph-cut-such-that-graph-becomes-a-dag-and-edge-weights-are-minimized/63540#63540 Answer by Nathann Cohen for Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized Nathann Cohen 2011-04-30T16:04:43Z 2011-04-30T16:04:43Z <p>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 <code>:-)</code></p> <p><a href="http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_edge_set" rel="nofollow">http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_edge_set</a></p> <p>Nathann</p> http://mathoverflow.net/questions/63477/find-graph-cut-such-that-graph-becomes-a-dag-and-edge-weights-are-minimized/65727#65727 Answer by andras frank for Find Graph Cut such that Graph becomes a DAG and Edge Weights are Minimized andras frank 2011-05-22T19:12:25Z 2011-05-22T19:12:25Z <p>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.</p> <p>Andras Frank </p> <p>p.s. If one is interested in details, I can give a pointer to localize the algorithm.</p>