Polynomial cases of hypergraph local edge-connectivity augmentation
Presented by Mr. roland GRAPPE
Type: Oral presentation
Track: Algorithmic Graph Theory
Cosh et al. proved that, given a hypergraph H and local edge-connectivy requirements, finding a minimum number of graph edges to be added to H in order to satisfy the requirements is NP-complete. We prove a minimax theorem and a polynomial algorithm solving two subcases of the above problem. Our proof relies on a slight generalization of Mader’s splitting off theorem to hypergraphs.