# Min cost max flow in bipartite run time

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?
-
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 '14 at 22:14

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

-
What algorithm would one use to solve this in $O(n^{1.5})$? – Niklas B. Mar 18 '14 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 '14 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 '14 at 4:20

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.

-