# Local edge-connectivity augmentation of a hypergraph with fixed rank

We are given a hypergraph [math]G_0=(V,\mathcal{E}_0)[/math] of rank at most [math]k[/math] (where [math]k[/math] is fixed, not part of the input) and a symmetric function [math]r:V\times V\to \mathbb{Z}_+[/math]. Can we find in polynomial time a graph [math]G=(V,{E})[/math] with a minimum number of edges such that [math]\lambda_{G_0+G}(x,y)\ge r(x,y)[/math] for every [math]x,y\in V[/math]?

## Remarks

The *rank* of a hypergraph is the size of its largest hyperedge. The problem is solved for *k=2* (i.e. when [math]G_0[/math] is a graph) by Frank ^{[1]}, and this implies a solution for *k=3* because a 3-hypergraph can be transformed into a graph with the same local edge-connectivities and vice versa ^{[2]}. The first open case is *k=4*. If *k* is not fixed, then the problem is NP-complete ^{[3]}.

## References

- ↑ A. Frank,
*Augmenting graphs to meet edge-connectivity requirements*,*SIAM J. Discrete Math.*, 5 (1992), 25-53, DOI link, author link - ↑ T. Jordán, Z. Szigeti,
*Detachments preserving local edge-connectivity of graphs*, DOI link, technical report link - ↑ B. Cosh, B. Jackson, Z. Király,
*Local connectivity augmentation in hypergraphs is NP-complete*, Discrete Applied Mathematics, DOI link