CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
  location:  PublicationsjournalsCMB
Publications        
Abstract view

Connectivity in Hypergraphs

  Published:2018-03-21
 Printed: Jun 2018
  • Megan Dewar,
    Tutte Institute for Mathematics and Computing , Ottawa, ON, Canada
  • David Pike,
    Department of Mathematics and Statistics , Memorial University of Newfoundland, St.~John's, NL, Canada
  • John Proos,
    Tutte Institute for Mathematics and Computing , Ottawa, ON, Canada
Format:   LaTeX   MathJax   PDF  

Abstract

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.
Keywords: hypergraph, connectivity, computational complexity, transversal hypergraph, connectivity, computational complexity, transversal
MSC Classifications: 05C65, 05C40, 68Q17 show english descriptions Hypergraphs
Connectivity
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
05C65 - Hypergraphs
05C40 - Connectivity
68Q17 - Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]
 

© Canadian Mathematical Society, 2018 : https://cms.math.ca/