Minimum cut problem using bases of extended polymatroids (Q1385774)

A common subproblem in combinatorial optimization requires finding the maximum flow and the minimum cut on a network with one source and one sink. It is therefore important to reduce the time complexity of this problem as far as possible. The labeling method proposed for its solution runs in exponential time in the worst case. Modifying this method, Edmonds and Karp showed that if the flow along the shortest path between the source and the sink is augmented in each labeling method iteration, then this problem can be solved in time \(O(m^2n)\) (here and in what follows, \(n\) is the number of nodes and \(m\) the number of arcs in the network). The labeling method was further improved by Dinits, who proposed to augment the flow in each iteration along all shortest paths between the source and the sink on the layered network constructed by the algorithm. This improved the time to solve the maximum flow problem to \(O(mn^2)\). In the Dinits algorithm, the flow through the shortest path is equal to the minimum capacity of the arcs included in this path. Karzanov proposed to augment the flow immediately to the full capacity of the arcs incident on the source (preflow), and to try to push it in the direction of the sink through the intermediate nodes while conserving the flow at these nodes (balancing). This approach to flow augmentation reduces the time complexity of the maximum-flow problem to \(O(n^3)\), and this appears to be the best algorithm for nearly complete graphs. For networks that are not very ``dense'', the best algorithm is that of Goldberg and Tarjan, which runs in time \(O(mn \times\log n^2/m)\). This algorithm differs from its predecessors in that it neither searches for the shortest paths nor constructs a layered network in each iteration: instead, the algorithm attempts to push the preflow to the sink through close nodes. As a measure of closeness of two nodes, the algorithm uses the distance metric on the network with certain properties. The algorithm proposed in this article first finds the minimum cut \(R(A,V - A)\) on the network, and then computes, if necessary, the maximum flow through the network edges. This algorithm can be used as an oracle for solving problems that require the set \(A\).