Hypergraph connectivity augmentation (Q1300056)

The hypergraph augmentation problem consists in augmenting a hypergraph by (``small'') hyperedges to meet prescribed local connectivity requirements. In the paper a minimax theorem for this problem is given. The result is derived from the degree-constrained version of the problem and for this version the required hypergraph is constructed in a greedy type algorithm. A similar minimax result is given for the problem of augmenting a hypergraph by weighted edges. The results have applications in supermodular colourings.