Minimal edge-coverings of pairs of sets (Q1898731)

The authors' main result is a max-min theorem concerning bisupermodular functions on pairs of sets. Their result has a number of non-trivial consequences. It gives rise to a max-min formula for the minimum number of edges to be added to a digraph \(D\) to make it \(k\)-node-connected and it implies a generalization of an edge-connectivity augmentation theorem of the first author; it also implies Mader's theorem on splitting of edges in digraphs, Edmond's theorem on matroid partitions, as well as an extension of Lubiw's extension of Györi's theorem on intervals.