News

Hypergraph connectivity augmentation

In our paper titled Hypergraph connectivity augmentation in strongly polynomial time, we consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. The central theme of our work is to show that certain hypergraph network design problems admit solutions in which the number of hyperedges is polynomial in the number of vertices and moreover, can be solved in strongly polynomial time. As applications of our results, we derive the first strongly polynomial time algorithms for degree-specified hypergraph connectivity augmentation using hyperedges, degree-specified hypergraph node-to-area connectivity augmentation using hyperedges, and degree-constrained mixed-hypergraph connectivity augmentation using hyperedges.