Excluding a Simple Good Pair Approach to Directed Cuts

In 1972, Mader proved that every undirected graph has a good pair, that is, an ordered pair (u,v) of nodes such that the star of v is a minimum cut separating u and v. In 1992, Nagamochi and Ibaraki gave a simple procedure to find a good pair as the basis of an elegant and very efficient algorithm to find minimum cuts in graphs. This paper rules out the simple good pair approach for the problem of finding a minimum directed cut in a digraph and for the more general problem of minimizing submodular functions. In fact, we construct a digraph with no good pair. Note that if a graph has no good pair, then it may not possess a so-called cut-equivalent tree. Benczúr constructed a digraph with no cut-equivalent tree; our counterexample thus extends Benczúr's one. Received: March 12, 1999 Final version received: June 19, 2000