Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

  1. Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
  2. Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
  3. If the answer is 'no', what are popular approximation algorithms and their associated run times?
share|improve this question
    
NetworkX is a popular graph/network library for Python that contains an implementation of MinCostMaxFlow. It should support MultiDiGraphs as well. However with $n \approx 100,000$ it may still take a good bit of time and memory. –  Nicholas Mancuso Oct 23 '12 at 15:37
    
There's lots of work on the network flow problem. What research have you done? Have you done a literature review of the known algorithms? Have you tried implementing any of them? –  D.W. Mar 18 at 22:14
add comment

2 Answers

Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.

share|improve this answer
    
What algorithm would one use to solve this in $O(n^{1.5})$? –  Niklas B. Mar 18 at 22:08
    
The Hungarian algorithm solves the problem in O(k^3) for a kxk matrix. Here, we have k = |V| and n := |E| = O(k^2). I guess this could be a bit confusing since in this question n means something different than normally in graph problems. –  Falk Hüffner Mar 19 at 4:09
    
Oh I see. I thought OP was saying $n = |V| = |E|$ or something :) Pardon my lack of reading comprehension –  Niklas B. Mar 19 at 4:20
add comment

I'm most familiar with the Cost-Scaling Algorithm by Goldberg. I'm pretty sure it behaves like $O( n^2 \log n \log U)$, where $\log U$ is (essentially) the number of bits in the representation of the edge costs.

This link provides a nice review.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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