  In this paper we consider two natural notions of 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 in the 2-section of the hypergraph
in question, determining a minimum strong vertex cut is NP-hard for general
hypergraphs. Moreover, the problem of finding minimum strong vertex cuts
remains NP-hard when restricted to hypergraphs with maximum edge size at most
3. We also discuss the relationship between strong vertex connectivity and the
minimum transversal problem for hypergraphs, showing that there are classes of
hypergraphs for which one of the problems is NP-hard while the other can be
solved in polynomial time.

Combinatorics