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
