Connectivity in Hypergraphs

Megan Dewar, David Pike, John Proos

Published 2016-11-21Version 1

In this paper we introduce two natural notions of vertex connectivity for hypergraphs: weak and strong. We prove that the strong vertex connectivity of a connected hypergraph is bounded by its weak edge connectivity, thereby extending a theorem of Whitney from graphs to hypergraphs. We find that while determining a minimum weak vertex cut can be done in polynomial time and is equivalent to finding a minimum vertex cut set in the 2-section of the hypergraph in question, determining a minimum strong vertex cut for general hypergraphs is NP-hard. We also consider some classes of hypergraphs and show that over some of these classes the problem of finding minimum strong vertex cuts remains NP-hard, while for others the problem is in P.