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 (27)

• Investigating the connectivity of hypergraphs via their spectra
• Bridges in Highly Connected Graphs
• 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
• Connection and separation in hypergraphs
• Title not available (Why is that?)
• Finding the shortest path for a hypergraph
• 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
• The weak hyperedge tenacity of the hypercycles
• 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
• Minimally connected \(r\)-uniform hypergraphs
• 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)