Connectivity in Hypergraphs.
2016
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.
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI