Don Wagner

Mathematical Optimization, Office of Naval Research

Dualizing Dijkstra's Algorithm for the Min-Cut Problem

Suppose we want to find a minimum-capacity (s,t)-cut in a graph. Then, of course, we can use any maximum-flow algorithm to compute a minimum (s,t)-cut. If the graph happens to be planar, then an alternative approach would be to first find the dual graph, and then find a shortest (s,t)-path using, say, Dijkstra's algorithm. If the graph is not planar, this alternative approach would appear to break down. In fact, we show that is not the case. In particular, an appropriate dual version of Dijkstra's algorithm can solve the minimum (s,t)-cut problem in class of graphs that includes and goes well beyond the class of planar graphs.