Minimum cut over all pairs of vertices in directed and strongly connected graph

Question

I have a graph G that is a directed and strongly connected graph, and I am asked to find a minimum cut over all pairs of vertices, meaning for every pair of S and T in the graph. This should be done in O(m² × n²) time.

The best I came up with was to consider all vertices to be S, and for each S consider all other vertices to be T, and for each of those run the Ford-Fulkerson algorithm, and then find the min cut. But If I am not mistaken, this algorthm will have complexity of O(m² × n² × C).

How can I do this task in O(m² × n²) time? Is it even possible ?

Answer 1

Notation:
m: number of edges
n: number of nodes
c_max: maximal single edge capacity
C: max flow value.

Dinic's algorithm in combination with can be employed to solve the task at hand. It runs in O(m * n^2). The brute-force approach of O(n^2) min cut computations then yield a total of O(m * n^2 * n^2), which is the desired result for m = O(n^2). For sparse graphs with m = o(n^2) I couldn't find a definite result; however, for m = O(n) this paper gives a result of O(n^2 + n^4 * log n) = O(m^2 * n^2 * log n).

There are several algorithms to compute the min cut ( or, equivalently, the max flow ) in a directed graph whose complexities stays below O( m * n^2 ). Wilf H.S., Algorithms and Complexity, 1st ed. has a survey on page 65. The most accessible algorithm is probably Dinic (O(m * n^2)).

Though at first glance the Ford-Fulkerson algorithm has a superior time complexity of O( m * C ), it sports some serious drawbacks:

• The time complexity is only valid for integer edge capacities. In fact, with irrational edge capacities, the algorithm is not even guaranteed to terminate at all nor to converge to the maximum flow ( see this paper for a provably minimal counterexample; this paper is also referenced in the wikipedia article ).

• The time complexity depends on the value of the maximum flow.

Significance of the flow value

The max flow value C is not necessarily a function of the number of nodes and edges. Even if it is (which depends on the graph topology), the following observation holds: the maximum possible flow value in any graph is the number of edges times the maximum edge capacity, m * c_max which amounts to O(m).

That turns the complexity of Ford-Fulkerson for integer edge capacities to O(m^2), unless the maximum capacity of a single edge is a function of the number of nodes or edges in the graph, which is a non-standard assumption.

For other algorithms there is no effect since its execution hinges on the graph topology and the edge capacities relative to each other, but not on the absolute edge capacities (and, by consequence, is no function of the max flow value either).