Welcome to MathOverflow

Question

3

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.

edited May 3 2011 at 18:02

asked Apr 29 2011 at 21:46

Grant
39●2

2

en.wikipedia.org/wiki/Feedback_arc_set – Thomas Kalinowski Apr 30 2011 at 10:38

some discussion on approximation: cstheory.stackexchange.com/q/423 – Thomas Kalinowski May 1 2011 at 6:16

Nathann Cohen · Answer 1 · 2011-04-30 16:04:43Z UTC

3

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

answered Apr 30 2011 at 16:04

Nathann Cohen
731●3●8

It looks like Sage can find a set of edges which is minimal in count. Rather than minimizing the number of edges, I want to minimize the sum of the weights of the edges in the set. Is it possible to adapt the functionality provided by Sage to solve that problem? – Grant Apr 30 2011 at 18:35

1

Oh yes, that's a short patch : one but needs to change the linear function optimized by the LP. That would require changing the function's code though. If you want to make it quick, the best is probably to copy the code of Sage's feedback_edge_set function in a file of your own and adapt it to your needs. Of course the best would be to send a patch so that everybody can use your modifications :-D Here is the code : hg.sagemath.org/sage-main/file/361a4ad7d52c/sage/… (the constraint-generation based code is way faster) Nathann – Nathann Cohen Apr 30 2011 at 21:30

If the weights were positive integers, you could simulate "weight" by "count"; just replace each edge with as many parallel edges as its weight. If the weights are not integers but positive rational numbers, multiply by a common denominator and apply the integer method (unless the multiplication gives you intractably large integers). If the weights are merely positive real numbers, then, except in degenerate cases, sufficiently close rational approximations should give the right answer. – Andreas Blass Apr 30 2011 at 21:34

@Andeas Blass, yes, I had thought of simulating wight by count in the method you describe. However, the weights are positive real numbers in the range representable by C++'s 'double' data type. In practice, some values are in the millions or billions which would make the LP solution impractical. – Grant May 1 2011 at 5:48

1

I don't remember how I coded this function, but I don't trust myself to have dealt with multiedges if I did not need to :-D Anyway replacing one edge by many would just impair the algorithm performance for no good design reason. The only sound thing to do is change this line ( hg.sagemath.org/sage-main/file/361a4ad7d52c/sage/… ) so that you optimize a weighted sum instead. How large is your graph anyway ? Does it have a known shape, like a GNP or something of the kind ? Can you explain how you generated it ? Some information on the degrees ? Nathann – Nathann Cohen May 1 2011 at 10:47

andras frank · Answer 2 · 2011-05-22 19:12:25Z UTC

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.

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.