Google Answers Logo
View Question
Q: Min-Cost Fixed Flow in Undirected graph ( Answered 5 out of 5 stars,   6 Comments )
Subject: Min-Cost Fixed Flow in Undirected graph
Category: Computers > Algorithms
Asked by: kalitar-ga
List Price: $30.00
Posted: 17 Mar 2005 14:11 PST
Expires: 16 Apr 2005 15:11 PDT
Question ID: 496389
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.
Subject: Re: Min-Cost Fixed Flow in Undirected graph
Answered By: mathtalk-ga on 16 Apr 2005 11:17 PDT
Rated:5 out of 5 stars
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]

It also provides links to some top-end implementations:


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:


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]

The simplex algorithm to solve general linear programming problems was
proposed by George Danzig in 1947:

[Simplex algorithm -- Wikipedia]

[simplex algorithm -- PlanetMath]

[An Introduction to Linear Programming and the Simplex Algorithm]

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.

*  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *  *

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

 \             /
   <         <
     <     <
       \ /

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.]

kalitar-ga rated this answer:5 out of 5 stars

Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: mathtalk-ga on 18 Mar 2005 05:39 PST
Hi, kalitar-ga:

You are correct to see a close connection between solving shortest
path problems and the solution to the capacitated minimum cost flow
problem.  Perhaps the following link (to a download a PDF paper) will
be helpful to you in clarifying this aspect:

[A faster strongly polynomial minimum cost flow algorithm]
(James B. Orlin; 1988)

The importance of shortest path algorithms is also highlighted in this
more recent paper on minimum cost for submodular flows, a
generalization of the minimum cost flow problem:

[A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow]
(Lisa Fleischer, Satoru Iwata, and S. Thomas McCormick; 1999,2001)

You seem to be quite familiar with the treatment of an undirected
graph in terms of directed graphs (by "duplicating" edges), so please
forgive me if I seem to belabor the point.

I would not expect an undirected graph to be more easily solved than
the equivalent (directed) network flow.  While you might conceive of
the problem intuitively as having fewer constraints, it has at the
same time more unknowns to determine, ie. to find the direction as
well as magnitude of flow along each edge.

The minimum cost network flow problem has many typical features of a
linear programming problem.  Here feasibility corresponds to
determining whether the capacities of the edges allow X units to be
transported from S to T at any cost; only if the problem is feasible
can we define a minimum cost solution.

It is a usual tactic in linear programming problems which deal with
unknowns that may not necessarily be >= 0 to impose a "standard"
formulation (eg. nonnegativity constraints) by expressing each such
unknown as the difference of two variables which are nonnegative. 
Such a reduction to standard form is necessary, for example, in order
to apply primal/dual methods.

regards, mathtalk-ga
Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: kalitar-ga on 18 Mar 2005 09:50 PST
Orlin algorithm works only in either (i,j) or (j,i) arc is in graph,
but not both. So I believe it will be hard to convert Undirected graph
to directed one and use this algorith.

In general if for each undirected vertex (i,j) with C(i,j) and P(i,j)
and 2 directed arcs (i,j) with C'(i,j) = C(i,j) and P'(i,j) = P(i,j)
and (j,i) with C'(j,i) = C(i,j) and P'(j,i) = P(i,j) will this be
sufficient to solve the undirected case of the problem?

Also how can express undirected case of the problem as Linear program.

Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: mathtalk-ga on 19 Mar 2005 13:20 PST
Hi, Vassil:

Let's use lower case letters u,v to refer to nodes of your
(undirected) graph, with special reference to the single source s
(start) and single sink t (terminal).

Now a "directed" edge is an ordered pair (u,v).  To formulate the
minimum cost fixed-flow problem as a linear program, it is not so much
necessary to think of the graph as "directed" as it is to define
quantities both known and unknown in terms of these ordered pairs.

So consider from a mathematical point of view f(u,v) and f(v,u) (the
flow from u to v and the flow from v to u) simply as distinct values. 
Correspondingly the capacities C(u,v) and C(v,u) may or may not be the
same, and the (positive) prices per unit flow P(u,v) and P(v,u) may or
may not be equal.  If it suits your application to define them as
equals, then let it be so.

The minimum cost for a total flow of X from s to t can then be stated
as this (nonstandard) linear program:

  Minimize  SUM  P(u,v)*f(u,v)

such that:

  SUM (f(u,v) - f(v,u)) = 0   for all u not in {s,t}

  SUM (f(s,v) - f(v,s)) = X

  SUM (f(t,v) - f(v,t)) = -X

   0  <=  f(u,v)  <=  C(u,v)   for all (u,v)

Note that for "edges" (u,v) that are not present in the network or
graph, one can simply treat these flow values f(u,v) as zero by
omitting them from the equations, which would be the equivalent of
setting a capacity C(u,v) = 0 for these.

Note further that because prices P > 0 and we are minimizing the sum
of P*f, wherever there are two unknowns f(u,v) and f(v,u), we are
guaranteed that any optimum occurs with at least one of them equal to
zero (as otherwise we could simply improve the objective function by
subtracting the minimum of f(u,v) and f(v,u) from both of them).

There is no guarantee from the mere formulation of the problem as a
linear program that it has a feasible solution.  After all X may
exceed the maximum flow of the network.  Furthermore the literature of
minimum cost fixed-flow algorithms can perhaps be understood as
specialized methods for solving these linear programs by exploiting
shortest-path or other efficient building blocks to "drive" the linear
program to an optimum.

It is certainly tempting to think that when X is a low value in
relationship to the network's maximum flow capacity, that one can
expeditiously build a minimum cost flow up to that level through
"augmenting paths" discovered by the shortest-path heuristic.  On the
other hand when X is very close to the maximum feasible flow, it might
be more attractive to start from the max-flow/min-cut operating point
and incrementally reduce costs from there by discovering the highest
cost contributions to that flow.

regards, mathtalk-ga
Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: kalitar-ga on 19 Mar 2005 15:18 PST

I believe this explanatio answers my questions!
Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: mathtalk-ga on 19 Mar 2005 21:45 PST
Hi, Vassil:

Great!  Let me try to dress it up a bit with some links to
downloadable code for these kinds of problems & a sketch of what's
known about time complexity, and I'll post it as an Answer for you.

regards, mathtalk-ga
Subject: Re: Min-Cost Fixed Flow in Undirected graph
From: kalitar-ga on 22 Mar 2005 06:56 PST


Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy