How to find all simple cycles in an undirected graph efficiently?

Min-Cost Fixed Flow in Undirected graph

• I need to solve following problem. I have undirected graph, source node S, sink node T, flow X to send from S to T, capacity C(i,j) of each vertex in undirected graph and price P(i,j) for single unit of flow for each vertex. Task is to find Min-Cost flow from S to T. Flow should be of X units. There are many algorithms found by Google for Directed graph. And not much for Undirected. We can apply Directed graph algorithms for Undirected case. However I believe that Undirected graph problem is easier one and can be solved in better O(). I need online materials and algorithms for the solution of the problem. There is one algorithm that I know, but I need better one. The algorithm is as follow: 1) Find shortest path (in respect of P(i,j)) from S to T. 2) Send K unit of flow through shortest path found in 1). K is smallest C(i,j) along the path. 3) X =- K 4) If X == 0 then solution is found else goto 1) I'll appreciate your answers. Thanks!

• Answer:

  Hi, kalitar-ga: A nice summary of the relationship between linear programming problems generally and those which correspond to (directed) network flow problems is provided here: [Network Flow] http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE167.HTM It also provides links to some top-end implementations: <quote> The highest-performance code available for solving maximum-flow in graphs is PRF [CG94], developed in the C language by Cherkassky and Goldberg. They report solving instances with over 250,000 vertices in under two minutes on a Sun Sparc-10 workstation. For minimum-cost max-flow, the highest-performance code available is CS [Gol92], capable of solving instances of over 30,000 vertices in a few minutes on Sun Sparc-2 workstations. Both of their codes are available by ftp for noncommercial use from: http://www.neci.nj.nec.com/homepages/avg.html <end-quote> See the page for further links, and for descriptions of various algorithmic approaches. Let's down into the issue you specifically raise of directed versus undirected graphs, and the impact of this distinction on algorithmic complexity. It is helpful to use the framework of general linear programming problems, qv. this page from the same site as above: [Linear Programming] http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK3/NODE141.HTM The simplex algorithm to solve general linear programming problems was proposed by George Danzig in 1947: [Simplex algorithm -- Wikipedia] http://en.wikipedia.org/wiki/Simplex_algorithm [simplex algorithm -- PlanetMath] http://planetmath.org/encyclopedia/SimplexAlgorithm.html [An Introduction to Linear Programming and the Simplex Algorithm] http://www.isye.gatech.edu/~spyros/LP/LP.html While Klee and Minty, and independently Zadeh, in 1972 gave examples to show that with a simple pivot rule, the simplex algorithm is in the worst case exponential in the number of unknowns, it is suprisingly efficient in practice. More sophisticated algorithms, based in particular on the ellipsoid algorithm, have been shown to have worst case polynomial times, but in practice their performance is not generally competitive. Dantzig, G. B. (1949). Programming of interdependent activities: II mathematical model. Econometrica. 17. 200-211. Karmarkar, N. (1984). A new polynomial algorithm for linear programming. Combinatorica. 4. 373-395. Khachiyan [Hajican], L. G. (1979). A polynomial algorithm for linear programming. Soviet Mathematics Doklady. 20. 191-194. Klee, V. and G. Minty. How good is the simplex algorithm. In Inequalities III, pages 159-172, New York, 1972. Academic Press. Zadeh, N. (1972). A bad network problem for the Simplex method and other minimum cost flow algorithms. Mathematical Programming. 5. 255-266 * * * * * * * * * * * * * * * * * * * * * * In an earlier comment we reduced a min-cost capacitated problem involving an undirected graph to terms comparable to one involving a directed graph using linear programming as the framework. It is probably worth noting that the reduction can already be made at the "outer" level of the graph formulation itself at a cost of introducing one additional node per edge. That is, for each undirected edge E of the original graph, we create a synthetic node C(E) through with all flow in one direction ("backflow") is redirected: edge E A------>>-------B \ / < < < < \ / C(E) To make this work the original "backflow" capacity of is assigned to both new edges, and the per unit cost for this can be split arbitrarily between the two edges. This enlarges the problem statement, adding as it does not only a node but three directed edges where previously there was one undirected edge, but it makes clear that at most a constant multiple is involved in the size of restated problem and thus (given a polynomial complexity algorithm is available) a constant multiple in time. The insight that one gains from the linear programming restatement is that no extra nodes are really needed, only twice as many unknowns (representing the unknown flow for an edge in either direction). [A clue to this fact is given by the arbitrariness of cost-splitting between a pair of new edges.] regards, mathtalk-ga