Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph

We consider the problem of edge-connectivity augmentation of a hypergraph by adding a multipartite graph. Given a hypergraph H, a partition P of the vertex set and an integer k, find a minimum number of graph edges between different members of P to be added to H in order to make it k-edge-connected. It is a common generalization of edge-connectivity augmentation of graphs with partition constraints [J. Bang-Jensen, H. Gabow, T. Jordán, Z. Szigeti, Edge-connectivity augmentation with partition constraints, SIAM J. Discrete Math. Vol. 12, No. 2 (1999) 160-207] and edge-connectivity augmentation of hypergraphs by adding graph edges [J. Bang-Jensen, B. Jackson, Augmenting hypergraphs by edges of size two, Math. Program. Vol. 84, No. 3 (1999) 467-481]. We give a min-max theorem for this problem, and our proof yields a polynomial algorithm to find the desired set of edges.