8

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?

Adri C.S.
  • 2,909
  • 5
  • 36
  • 63
sabari
  • 779
  • 2
  • 8
  • 14

2 Answers2

4

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

Khaled.K
  • 5,828
  • 1
  • 33
  • 51
  • Gomory-Hu tree does not work for directed graphs(unless capacity (u,v)=(v,u) for all arcs).The cuts are not symmetric submodular functions, which is required for Gomory-Hu tree to work. – Chao Xu May 09 '14 at 20:03
  • @ChaoXu Thank you for the comment, I'll note it in my answer. – Khaled.K Dec 19 '16 at 05:42
  • You have T(min-cut) as O(2|V|-2) in your text. What algorithm is that? E-K is O(|V| * |E|^2) ~ O(|V|^5) and Dinic is O(|V|^2 * |E|) ~ O(|V|^4), leaving your Gomory-Hu build at O(|V|^5), not O(|V|^2). – Boyd Stephen Smith Jr. Aug 05 '17 at 22:36
2

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.

Chao Xu
  • 2,156
  • 2
  • 22
  • 31