News

Hypergraph splitting-off

In a recent paper titled Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time, we consider hypergraph network design problems where the goal is to construct a hypergraph satisfying certain properties. The central theme of this work is to show that certain hypergraph network design problems admit solutions with polynomial number of hyperedges and moreover, can be solved in strongly polynomial time. The hypergraph network design problems that we focus upon are splitting-off operation in hypergraphs, connectivity augmentation using hyperedges, and covering skew-supermodular functions using hyperedges.