Connectivity in hypergraphs

DOI10.4153/CMB-2018-005-9MaRDI QIDQ4569602zbMATH OpenOpenAlexFDO

Authors Megan Dewar, David A. Pike, John Proos

Publication date 26 June 2018

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

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

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)

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.

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

Cited in

(27)

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

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)