<p>See <a href="http://dl.acm.org/citation.cfm?id=196753" rel="nofollow">this paper</a>. I think adopting their technique, many(usually scaling based) min-cost flow algorithms with running time $O(f(n,m))$ can run in $O(f(n_1,m))$ time. Here $n_1$ is the size of the smaller bipartition.</p>

<p>If $f(n,m)$ is the best possible run time for min-cost flow on general graphs with $n$ vertices and $m$ edges. There is an easy argument that you can't expect anything running in $o(f(n_1,m))$ time. (with some reasonable assumptions, like $n\leq m$, $f(n,cm)=O(f(n,m))$ for any constant $c$)</p>

<p>Proof: Otherwise, you can apply the standard vertex splitting operation to the input graph and use the bipartite min-cost flow algorithm and get a better running time. </p>

<p>Finally, if you are restricting cost and capacities things, <a href="http://epubs.siam.org/doi/abs/10.1137/0218069" rel="nofollow">these scaling algorithms</a> is still pretty much state of the art(difference is at most $\log c$ for w/e parameter $c$ you care about). You can decipher that Theorem 3.5 to see which one of them gives you the best result. </p>

CC BY-SA 3.0
2015-02-18T19:49:47.977Z
Then, bipartiteness does not seem to help if $n_1$ is $O(n)$; i.e. if the graph is balanced. So, the only things left to exploit are the non-negative costs and the fact that $c$ and $w$ are small.
iheap
CC BY-SA 3.0
2015-02-18T20:29:21.743Z
I updated my answer to reflect cost and capacity.
Chao Xu
CC BY-SA 4.0
2019-06-08T02:55:48.847Z
Please cite papers instead of only providing links so that the answer is still complete even if the link breaks.
tjhighley
CC BY-SA 3.0
2015-02-18T19:36:00.990Z
2015-02-18T20:28:47.167Z
2015-02-18T20:28:47.167Z
Chao Xu
<p>The algorithm by Orlin you mention is quite old, and max flow algorithms came a long way since;</p>

<p>In 1994, <a href="http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/king-rao-tarjan.pdf" rel="nofollow">King et al. showed</a> that max flow can be solved in $O(n\cdot m)$ whenever $m=\omega(n^{1+\epsilon})$ for some $\epsilon &gt; 0$.</p>

<p>This result was lately <a href="http://jorlin.scripts.mit.edu/docs/O%28nm%29MaxFlow.pdf" rel="nofollow">complemented by Orlin himself</a>, which showed $O(nm)$ time complexity extends for $m=O(n^{\frac{16}{15}})$ (and also gave slight improvement for the $m=O(n)$ case).</p>

<p>If you are interested in more practical algorithms you can look at the <em>approximation</em> algorithms for max flow, (<a href="http://arxiv.org/pdf/1008.1975v4.pdf" rel="nofollow">see Mądry's paper</a> for example), which is able to produce $O(\log n)$ approximation in near linear time.</p>

<p>If you are also interested in single-unit capacities, <a href="http://people.csail.mit.edu/madry/docs/matching_flow.pdf" rel="nofollow">Mądry recently gave an (exact) $\widetilde O(m^{\frac{10}{7}})$</a> for maximum cardinality bipartite matching.</p>

CC BY-SA 3.0
2015-02-18T19:14:42.750Z
Do these algorithms compute minimum cost maximum flow, or just maximum flow? The papers do not talk about cost minimization at all. Can they be modified for cost minimization without incurring extra computational complexity?
iheap
CC BY-SA 3.0
2015-02-18T07:29:31.107Z
2015-02-18T07:29:31.107Z
R B
<p>I think Orlin's algorithm and many other algorithms, are not good in this case. Simplest algorithm is ford falkerson algorithm and is both practically and theoretically better than almost all of those algorithms. It runs in time $O(m\cdot max_f)$ were max_f is the size of maximum flow. In above problem indeed it's $max_f=O(n)$, because there are at most $n$ edge disjoint paths between two vertices and each of those paths rises $O(1)$ flow. Also if the graph is unit weighted in the bipartite case modified version of dinic algorithm give $O(m\sqrt{ n})$ algorithm and if one wants to find a latest algorithm suitable for this case I would suggest to search for improvement on different sorts of dinic algorithm or ford falkerson not hard improvements on edmond karp algorithm, they have different aspects. One improves running time by use of structure of corresponding graph and supposing weights are not important, the other improves the running time by getting rid of flow size, which is not obstacle in this case (when a max flow is O(n)).</p>

<p><strong>Update:</strong> Recently (STACS 15) Tarjan et al, improved the best known time complexity of min-cost max-flow algorithm for unit capacity graphs by improvement on sort of Dinic's algorithm, in fact based on cost scaling algorithms of Goldberg and Tarjan, in particular they improved weighted bipartite matching algorithms:</p>

<p>Sagi Hed, Haim Kaplan, Andrew Goldberg, and Robert Tarjan: </p>

<p>"Minimum Cost Flows in Graphs with Unit Capacities"</p>

CC BY-SA 3.0
2015-02-18T20:08:11.117Z
I agree that we can compute the maximum flow in $O(|E| \; |V|)$ using Ford-Fulkerson in my setting. Can we also get the minimum cost maximum flow via this algorithm? Or does it become equivalent to the minimum cost augmentation approach that I am currently using?
iheap
CC BY-SA 3.0
2015-02-18T13:16:31.923Z
2015-03-11T14:15:54.807Z
2015-03-11T14:15:54.807Z
Saeed
<p><a href="https://www.math.ubc.ca/~anstee/math523/StronglyPolynomialNetworkFlow.pdf" rel="nofollow">Orlin's algorithm</a> is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question.</p>

<p>If the graph $G(V = V_1 \cup V_2, E)$ is known to be bipartite (with $V_1$ and $V_2$ denoting the "left" and "right" node sets), can one compute the minimum cost maximum flow any faster? Here the flow is between an additional source that is connected to the nodes in $V_1$ and an additional sink that is connected to the nodes in $V_2$.</p>

<p>I'm also interested to hear about algorithms that do not have better time complexity, but perform well in practice.</p>

<p>You can assume that all capacities and costs are <em>non-negative</em> integers. There can be both limited-capacity and unlimited-capacity edges in the graph. Also, assume that both the maximum non-infinite capacity $c$, and the maximum edge cost $w$ is small; i.e. one can consider both as $O(1)$ terms for complexity purposes. </p>

<p>Thanks!</p>

<p><strong>Edit:</strong> My current-best solution is to use a minimum cost augmentation algorithm, which solves the problem in $O(|E| \; F \log |V|)$ time, where $F$ is the value of the maximum flow. Since $F$ is bounded by $c \;|V|$ (which is $O(|V|)$ under our assumptions), this approach results in an overall time complexity of $O(|E| \; |V| \; \log |V|)$. Is it possible to beat this?</p>

CC BY-SA 3.0
2015-02-17T23:13:07.837Z
When you say bipartite apart from the source and sink, are you assuming anything about the edges of the sort and sink? (For instance the source only connects to one side of the graph and the sink the other.)
usul
CC BY-SA 3.0
2015-02-18T00:43:04.487Z
@usul: Yes, the source connects to one side of the graph, and the sink the other. I changed the question text to clarify this point. Also, all costs are non-negative. Thanks!
iheap
CC BY-SA 3.0
2015-02-18T11:58:21.057Z
O(1) or exactly 1? for example if all of them are 2 we can assume all are one and this is differ from O(1).
Saeed
CC BY-SA 3.0
2015-02-18T19:22:59.433Z
@Saeed: For any algorithm whose time complexity depends on $c$ and $w$, you can substitute $1$ for these two numbers in the big-O expression. Note that the graph might have unlimited capacity edges; i.e. the number $c$ is the maximum *finite* capacity.
iheap
CC BY-SA 3.0
2015-02-18T19:54:31.837Z
@iheap, I think maybe it's better to read my answer then teach me. not all algorithms are relying on c. but if all capacities are c then there are free to use algorithms which I mentioned one of them in my answer (modified dinic algorithm), but if you want to use them e.g with capacities in {1,2} then you have to modify those algorithms and I don't know if modification is trivial. But why I asked this? 1. because of ur previous question that I commented and answer and that needs flow on unit capacity graph. 2. Your choice of algorithm as you wrote in your question it's a little bit strange.
Saeed
CC BY-SA 3.0
2015-02-18T20:01:39.930Z
@Saeed: I wasn't trying to teach you anything, I was just trying to clarify things for everybody's (including myself) benefit. No need to get defensive. I see where you are coming from (i.e. relating the other question and this), but they are really two separate questions.
iheap
CC BY-SA 3.0
2015-02-18T20:03:55.160Z
@Saeed: I started the discussion with Orlin's 1991 algorithm, because it is cited as the "fastest" algorithm known for this purpose in a (apparently outdated) textbook that I had. At this point in the discussion, it is obvious that it is not the best way to go under my assumptions.
iheap
CC BY-SA 3.0
2015-02-18T20:07:33.520Z
OK I understand that they are not related but still note that weight 1 and weight in {1,2} are not simply convertible. e.g TSP is trivial if all weights are 1 but npc if weights are {1,2}, this is an strange example but it says it's not easy to say that if for capacity c we have solution then for capacity in {1,...,c} we have solution with same running time.p.s: anyhow ford falkerson is even older, I see that you didn't notice your conditions carefully.
Saeed
CC BY-SA 3.0
2015-02-18T20:10:53.797Z
You are right, $c = 1$ and $c = O(1)$ are definitely not the same. In this question, it is the latter.
iheap
CC BY-SA 3.0
2015-02-18T20:11:02.053Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/21230/discussion-between-iheap-and-saeed).
iheap
<ds.algorithms><graph-algorithms><max-flow>
Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs
iheap
# Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs

(Asked by: username_0 on 2015-02-17)

[Orlin's algorithm](https://www.math.ubc.ca/~anstee/math523/StronglyPolynomialNetworkFlow.pdf) is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and the node sets of the graph $G(V, E)$ in question.

If the graph $G(V = V\_1 \cup V\_2, E)$ is known to be bipartite (with $V\_1$ and $V\_2$ denoting the "left" and "right" node sets), can one compute the minimum cost maximum flow any faster? Here the flow is between an additional source that is connected to the nodes in $V\_1$ and an additional sink that is connected to the nodes in $V\_2$.

I'm also interested to hear about algorithms that do not have better time complexity, but perform well in practice.

You can assume that all capacities and costs are *non-negative* integers. There can be both limited-capacity and unlimited-capacity edges in the graph. Also, assume that both the maximum non-infinite capacity $c$, and the maximum edge cost $w$ is small; i.e. one can consider both as $O(1)$ terms for complexity purposes.

Thanks!

**Edit:** My current-best solution is to use a minimum cost augmentation algorithm, which solves the problem in $O(|E| \; F \log |V|)$ time, where $F$ is the value of the maximum flow. Since $F$ is bounded by $c \;|V|$ (which is $O(|V|)$ under our assumptions), this approach results in an overall time complexity of $O(|E| \; |V| \; \log |V|)$. Is it possible to beat this?

**Tags:** ds.algorithms, graph-algorithms, max-flow

> **Comments:**
> **username_1**: When you say bipartite apart from the source and sink, are you assuming anything about the edges of the sort and sink? (For instance the source only connects to one side of the graph and the sink the other.)  
> **username_0**: @username_1: Yes, the source connects to one side of the graph, and the sink the other. I changed the question text to clarify this point. Also, all costs are non-negative. Thanks!  
> **username_2**: O(1) or exactly 1? for example if all of them are 2 we can assume all are one and this is differ from O(1).  
> **username_0**: @username_2: For any algorithm whose time complexity depends on $c$ and $w$, you can substitute $1$ for these two numbers in the big-O expression. Note that the graph might have unlimited capacity edges; i.e. the number $c$ is the maximum *finite* capacity.  
> **username_2**: @username_0, I think maybe it's better to read my answer then teach me. not all algorithms are relying on c. but if all capacities are c then there are free to use algorithms which I mentioned one of them in my answer (modified dinic algorithm), but if you want to use them e.g with capacities in {1,2} then you have to modify those algorithms and I don't know if modification is trivial. But why I asked this? 1. because of ur previous question that I commented and answer and that needs flow on unit capacity graph. 2. Your choice of algorithm as you wrote in your question it's a little bit strange.  
> **username_0**: @username_2: I wasn't trying to teach you anything, I was just trying to clarify things for everybody's (including myself) benefit. No need to get defensive. I see where you are coming from (i.e. relating the other question and this), but they are really two separate questions.  
> **username_0**: @username_2: I started the discussion with Orlin's 1991 algorithm, because it is cited as the "fastest" algorithm known for this purpose in a (apparently outdated) textbook that I had. At this point in the discussion, it is obvious that it is not the best way to go under my assumptions.  
> **username_2**: OK I understand that they are not related but still note that weight 1 and weight in {1,2} are not simply convertible. e.g TSP is trivial if all weights are 1 but npc if weights are {1,2}, this is an strange example but it says it's not easy to say that if for capacity c we have solution then for capacity in {1,...,c} we have solution with same running time.p.s: anyhow ford falkerson is even older, I see that you didn't notice your conditions carefully.  
> **username_0**: You are right, $c = 1$ and $c = O(1)$ are definitely not the same. In this question, it is the latter.  
> **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/21230/discussion-between-username_0-and-saeed).  

---

## 3 answers

### Answer by username_3 on 2015-02-18. Score: 4 | Accepted answer

See [this paper](http://dl.acm.org/citation.cfm?id=196753). I think adopting their technique, many(usually scaling based) min-cost flow algorithms with running time $O(f(n,m))$ can run in $O(f(n\_1,m))$ time. Here $n\_1$ is the size of the smaller bipartition.

If $f(n,m)$ is the best possible run time for min-cost flow on general graphs with $n$ vertices and $m$ edges. There is an easy argument that you can't expect anything running in $o(f(n\_1,m))$ time. (with some reasonable assumptions, like $n\leq m$, $f(n,cm)=O(f(n,m))$ for any constant $c$)

Proof: Otherwise, you can apply the standard vertex splitting operation to the input graph and use the bipartite min-cost flow algorithm and get a better running time.

Finally, if you are restricting cost and capacities things, [these scaling algorithms](http://epubs.siam.org/doi/abs/10.1137/0218069) is still pretty much state of the art(difference is at most $\log c$ for w/e parameter $c$ you care about). You can decipher that Theorem 3.5 to see which one of them gives you the best result.

> **Comments:**
> **username_0**: Then, bipartiteness does not seem to help if $n_1$ is $O(n)$; i.e. if the graph is balanced. So, the only things left to exploit are the non-negative costs and the fact that $c$ and $w$ are small.  
> **username_3**: I updated my answer to reflect cost and capacity.  
> **username_4**: Please cite papers instead of only providing links so that the answer is still complete even if the link breaks.  

---

### Answer by username_5 on 2015-02-18. Score: 3

The algorithm by Orlin you mention is quite old, and max flow algorithms came a long way since;

In 1994, [King et al. showed](http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/king-rao-tarjan.pdf) that max flow can be solved in $O(n\cdot m)$ whenever $m=\omega(n^{1+\epsilon})$ for some $\epsilon > 0$.

This result was lately [complemented by Orlin himself](http://jorlin.scripts.mit.edu/docs/O%28nm%29MaxFlow.pdf), which showed $O(nm)$ time complexity extends for $m=O(n^{\frac{16}{15}})$ (and also gave slight improvement for the $m=O(n)$ case).

If you are interested in more practical algorithms you can look at the *approximation* algorithms for max flow, ([see Mądry's paper](http://arxiv.org/pdf/1008.1975v4.pdf) for example), which is able to produce $O(\log n)$ approximation in near linear time.

If you are also interested in single-unit capacities, [Mądry recently gave an (exact) $\widetilde O(m^{\frac{10}{7}})$](http://people.csail.mit.edu/madry/docs/matching_flow.pdf) for maximum cardinality bipartite matching.

> **Comments:**
> **username_0**: Do these algorithms compute minimum cost maximum flow, or just maximum flow? The papers do not talk about cost minimization at all. Can they be modified for cost minimization without incurring extra computational complexity?  

---

### Answer by username_2 on 2015-02-18. Score: 1

I think Orlin's algorithm and many other algorithms, are not good in this case. Simplest algorithm is ford falkerson algorithm and is both practically and theoretically better than almost all of those algorithms. It runs in time $O(m\cdot max\_f)$ were max\_f is the size of maximum flow. In above problem indeed it's $max\_f=O(n)$, because there are at most $n$ edge disjoint paths between two vertices and each of those paths rises $O(1)$ flow. Also if the graph is unit weighted in the bipartite case modified version of dinic algorithm give $O(m\sqrt{ n})$ algorithm and if one wants to find a latest algorithm suitable for this case I would suggest to search for improvement on different sorts of dinic algorithm or ford falkerson not hard improvements on edmond karp algorithm, they have different aspects. One improves running time by use of structure of corresponding graph and supposing weights are not important, the other improves the running time by getting rid of flow size, which is not obstacle in this case (when a max flow is O(n)).

**Update:** Recently (STACS 15) Tarjan et al, improved the best known time complexity of min-cost max-flow algorithm for unit capacity graphs by improvement on sort of Dinic's algorithm, in fact based on cost scaling algorithms of Goldberg and Tarjan, in particular they improved weighted bipartite matching algorithms:

Sagi Hed, Haim Kaplan, Andrew Goldberg, and Robert Tarjan:

"Minimum Cost Flows in Graphs with Unit Capacities"

> **Comments:**
> **username_0**: I agree that we can compute the maximum flow in $O(|E| \; |V|)$ using Ford-Fulkerson in my setting. Can we also get the minimum cost maximum flow via this algorithm? Or does it become equivalent to the minimum cost augmentation approach that I am currently using?  

---

