4
$\begingroup$

Orlin's algorithm 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?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ 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.) $\endgroup$
    – usul
    Feb 17, 2015 at 23:13
  • $\begingroup$ @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! $\endgroup$
    – iheap
    Feb 18, 2015 at 0:43
  • $\begingroup$ 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). $\endgroup$
    – Saeed
    Feb 18, 2015 at 11:58
  • $\begingroup$ @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. $\endgroup$
    – iheap
    Feb 18, 2015 at 19:22
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Feb 18, 2015 at 19:54

3 Answers 3

Reset to default
4
$\begingroup$

See this paper. 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 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – iheap
    Feb 18, 2015 at 19:49
  • $\begingroup$ I updated my answer to reflect cost and capacity. $\endgroup$
    – Chao Xu
    Feb 18, 2015 at 20:29
  • $\begingroup$ Please cite papers instead of only providing links so that the answer is still complete even if the link breaks. $\endgroup$
    – tjhighley
    Jun 8, 2019 at 2:55
3
$\begingroup$

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

In 1994, King et al. showed 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, 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 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}})$ for maximum cardinality bipartite matching.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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? $\endgroup$
    – iheap
    Feb 18, 2015 at 19:14
1
$\begingroup$

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"

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – iheap
    Feb 18, 2015 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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