Hello ! I want to deal with both at the same time. I think I just found how to do it, but I will need to write all the stuff I was writing about in my previous message.. Could you ask your colleague if there is some flow in my reasoning :
A graph is acyclic if and only if the is no non-null circulation. A circulation ( http://en.wikipedia.org/wiki/Flow_network ) is the problem you obtain when you write flow conservation on each vertex of your graph. For me, a non-null circulation implies that the graph contains a cycle. So, let us say you have binary variables c_e on each one of your arcs ( in a directed graph ). You want to remove the least number of arcs ( set the minimal number of c_e to 1, so you minimize the sum of them ) such that there is no non-null circulation. So if you set the capacity of your edges to 1- c_e ( an edge you remove is a broken link ), you write a Maximization problem which is your circulation, in which you wan to maximize the sum of the flows. To ensure that is problem has no non-null solution, you want to ensure that its DUAL can be less than 0. And here is your condition that your graph is cycle-free !!! You want to minimize the number of arcs you remove such that your graph is circuit-free, which means that the dual of a circulation can be less than 0. Does it seem ok to you ? When your graph is undirected, a colleague of mine gave me a good trick : you take the directed version of your undirected graph ( replacing is edge by both arcs ), and split each vertex x in two vertices (x_in and x_out). all the in-arcs to x now go to x_in, all the out-arcs from x now leave from x_out, and there is an arc from x_in to x_out of weight 0. You have to bring small modifications to the LP program, but it is not so hard and with the trick of the dual it seems pretty easy to do !!! How did you plan to write yours ??? I if you already write one, perhaps I will just write the stuff about duals and LP merging for a start, in such a way that the two of us won't work at the same time on the same function ;-) Nathann On 13 sep, 12:22, Alexandre Blondin Massé <alexandre.blondin.ma...@gmail.com> wrote: > Are you studying the directed version of the minimum feedback vertex > or the undirected one or both ? > I'm currently working on the directed one and I'm not using linear > programming. I plan to write a patch soon about it. > Moreover, some teacher told me that this problem is hard to tackle > with linear programming : the problem is that the number of > constraints can be exponential since the number of cycles in a graph > can be really huge. I don't have any reference for this, though. > Alex > > 2009/9/12 Nathann Cohen <nathann.co...@gmail.com>: > > > Hello everybody !!!! > > > I have been thinking for a while about different ways to build something > > great from the support for Linear Programming in Sage. There's one idea I > > would like to explore, and I need to know if some of you would be : > > - Interested in using it > > - Interesting in helping me to write it > > > It may have to deal with a new "type" of symbolics in Sage, I do not know > > yet, and you're all so full of experience I will probable keep asking > > questions for the next month... ;-) > > > Here is what I thought about : > > > I wanted to write an algorithm in Sage for the Minimum Feedback Vertex Set > > problem (http://en.wikipedia.org/wiki/Feedback_vertex_set). This problem > > is the following : given a graph G, what is a vertex subset S of minimum > > cardinality such that the graph minus S is a forest ( contains no cycle ). > > > It is very easy to say it, a bit harder ( at least for me ) to write it as a > > linear program. I know which function I want to minimize, but I do not know > > how to write a linear program testing that "there is no cycle in the graph". > > I know, though, how to write a linear program GIRTH computing the smallest > > cycle ( girth ) of the graph. What I need, then, to ensure that a graph is > > cycle free "smallest cycle in the graph" is to ensure that the DUAL of the > > GIRTH program can be at least the size of the graph+1. > > > So this is what I think we need in Sage : first, a way to compute duals (but > > this I can write pretty quickly), and a way to merge programs one into the > > other to build bigger ones. In the lab I work in, people are constantly > > trying to build networks of minimum cost under very specific constraint ( > > some multiflow is feasible, the graph is k-connected, etc, etc ... ). > > > They --always-- have to rewrite all the LP programs, name the variables, > > into a looong Linear Program. And this, as a coder, I can not stand :-) > > > Linear Programming needs a way to merge programs, to obtain duals without > > more than a call to a .dual() method, and a big database of Linear Programs > > from where other ones can be easily defined. > > > I do not know much of what can be done in GLPK, Ampl, Cplex, Coin-Or, and a > > lot of other LP-related softwares I have no clues about, which you may > > perfectly know.... Is it something you have already seen somewhere, in which > > case I could try to give it a look to spare some time, or is it new and does > > it need to be built from scratch ? > > > More importantely, do you think it is -- useful -- ? > > > Thank you for your help !!! > > > Nathann --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
