Augmenting hypergraphs by edges of size two (Q1300052)

Using a vertex splitting technique developed by \textit{A. Frank} [SIAM J. Discrete Math. 5, No. 1, 22-53 (1992; Zbl 0782.05054)], the authors prove an edge augmentation theorem that generalizes a result obtained by \textit{E. Cheng} [Math. Program. 84B, No. 3, 443-465 (1999; Zbl 0932.05067)] through different means. Also, it is shown that there exists a strongly polynomial algorithm which takes as input a hypergraph \(H\) and a natural number \(k\) and outputs a minimum set of edges of size two whose addition to \(H\) results in a \(k\)-edge-connected hypergraph. Here `strongly polynomial' means the complexity of the algorithm depends only on the order and size of \(H\).