All pair Maximum Flow

8
votes

Given a directed weighted graph, how to find the Maximum Flow ( or Minimum Edge Cut ) between all pairs of vertices.
The naive approach is simply to call a Max Flow algorithm like Dinic's, whose complexity is O((V^2)*E), for each pair.
Hence for all pairs it is O((V^4)*E).

Is it possible to reduce the complexity to O((V^3)*E) or to O(V^3) by some optimizations?

2
graphmax-flownetwork-flow
PS: This is not home work. – sabari
Have you looked into Gomory–Hu tree ? – mmgp
@mmgp : This is exactly want I wanted. Thanks! And can you post a link where the Gusfield's algorithm is described with examples and pseudocode? – sabari
cs.princeton.edu/~kt/cut-tree the code can be found by visiting the Experiments link. – mmgp
@mmgp Could you make the comment into an answer? – Pål GD

2 Answers

4
votes

Gomory-Hu Tree does not work with directed graphs, putting that aside, Gomory-Hu Tree will form a Graph maximum flow by applying minimum cuts.

The time complexity is:

O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)

* using an optimal minimum-cut algorithm (Max-Flow Min-Cut Reduction)

This example illustrate how Gomory-Hu Tree is constructed from a given Graph

2
votes

Gomory-Hu tree does not work for directed weighted graph.

It is an open problem whether there exist an algorithm to solve all pair maximum flow faster than running n^2 maximum flows on directed graphs.