4

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?

iheap
  • 195
  • 1
  • 8
  • 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.) – usul Feb 17 '15 at 23:13
  • @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 Feb 18 '15 at 00:43
  • 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 Feb 18 '15 at 11:58
  • @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 Feb 18 '15 at 19:22
  • @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 Feb 18 '15 at 19:54
  • @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 Feb 18 '15 at 20:01
  • @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 Feb 18 '15 at 20:03
  • 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 Feb 18 '15 at 20:07
  • You are right, $c = 1$ and $c = O(1)$ are definitely not the same. In this question, it is the latter. – iheap Feb 18 '15 at 20:10
  • Let us continue this discussion in chat. – iheap Feb 18 '15 at 20:11

3 Answers3

4

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.

Chao Xu
  • 4,399
  • 23
  • 32
  • 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 Feb 18 '15 at 19:49
  • I updated my answer to reflect cost and capacity. – Chao Xu Feb 18 '15 at 20:29
  • Please cite papers instead of only providing links so that the answer is still complete even if the link breaks. – tjhighley Jun 08 '19 at 02:55
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 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.

R B
  • 9,448
  • 5
  • 34
  • 74
  • 3
    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 Feb 18 '15 at 19:14
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"

Saeed
  • 3,440
  • 1
  • 22
  • 39
  • 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 Feb 18 '15 at 20:08