MINIMAL EDGE-COVERINGS OF PAIRS OF SETS

We derive a new min-max formula for the minimum number of new edges to be added to a given directed graph to make it k-node-connected. This gives rise to a polynomial time algorithm (via the ellipsoid method) t o compute the augmenting edge set of minimum cardinality. (Such an alg orithm or formula was previously known only for k=1). Our main result is actually a new min-max theorem concerning ''bisupermodular'' functi ons on pairs of sets. This implies the node-connectivity augmentation theorem mentioned above as well as a generalization of an earlier resu lt of the first author on the minimum number of new directed edges who se addition makes a digraph k-edge-connected. As further special cases of the main theorem, we derive an extension of (Lubiw's extension of) Gyori's theorem on intervals, Mader's theorem on splitting off edges in directed graphs, and Edmonds' theorem on matroid partitions. (C) 19 95 Academic Press, Inc.