Connectivity in hypergraphs

DOI10.4153/CMB-2018-005-9zbMATH Open1390.05150arXiv1611.07087OpenAlexW3099865855MaRDI QIDQ4569602FDOQ4569602

Authors: Megan Dewar, David A. Pike, John Proos 

Publication date: 26 June 2018

Published in: Canadian Mathematical Bulletin (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1611.07087

Recommendations

• The connectivity of hypergraphs
• Edge-connectivity in hypergraphs
• Maximally edge-connected hypergraphs
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Computing minimum cuts in hypergraphs

zbMATH Keywords

computational complexitytransversal

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Hypergraphs (05C65) Transversal (matching) theory (05D15)

Cited In (26)

• Investigating the connectivity of hypergraphs via their spectra
• Bridges in Highly Connected Graphs
• Finding the shortest path for a Hypergraph
• Cut vertex transit functions of hypergraphs
• Edge-connectivity in hypergraphs
• The edge‐connectivity of vertex‐transitive hypergraphs
• On the sizes of \((k, l)\)-edge-maximal \(r\)-uniform hypergraphs
• On the sizes of \(k\)-edge-maximal \(r\)-uniform hypergraphs
• Title not available (Why is that?)
• Connection and separation in hypergraphs
• Title not available (Why is that?)
• On \(c\)-spaces and hypergraphs
• Sufficient conditions for maximally edge-connected hypergraphs
• The cutwidth and the vertex separation number of hypergraphs and their König’s representations
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Connectivity of Cartesian product of hypergraphs
• On the sizes of vertex-\(k\)-maximal \(r\)-uniform hypergraphs
• Finding a minimal spanning hypertree of a weighted hypergraph
• Relating hypergraph parameters of generalized power graphs
• Whitney's connectivity inequalities for directed hypergraphs
• The geometry connectivity of hypergraphs
• High connectivity keeping sets in graphs and digraphs
• Vector connectivity in graphs
• Extending simplicial complexes: topological and combinatorial properties
• Degree sequence conditions for maximally edge-connected and super edge-connected hypergraphs
• Maximally connected \(p\)-partite uniform hypergraphs

This page was built for publication: Connectivity in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569602)