4
$\begingroup$

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:

  1. Removing the edges in $E'$ from $E$ reduces the graph to a directed-acyclic-graph.
  2. 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.

|cite|improve this question
$\endgroup$
4
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Grant Apr 30 '11 at 18:35
  • 1
    $\begingroup$ 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/graphs/… (the constraint-generation based code is way faster) Nathann $\endgroup$ – Nathann Cohen Apr 30 '11 at 21:30
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Apr 30 '11 at 21:34
  • $\begingroup$ @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. $\endgroup$ – Grant May 1 '11 at 5:48
  • 1
    $\begingroup$ 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/graphs/… ) 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 $\endgroup$ – Nathann Cohen May 1 '11 at 10:47
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.