Geodesic
Connectivity in Hypergraphs
Canadian mathematical bulletin, Tome 61 (2018) no. 2, pp. 252-271

Voir la notice de l'article provenant de la source Cambridge

DOI

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.
DOI : 10.4153/CMB-2018-005-9
Mots-clés : 05C65, 05C40, 68Q17, hypergraph, connectivity, computational complexity, transversal 
Dewar, Megan; Pike, David; Proos, John. Connectivity in Hypergraphs. Canadian mathematical bulletin, Tome 61 (2018) no. 2, pp. 252-271. doi: 10.4153/CMB-2018-005-9
@article{10_4153_CMB_2018_005_9,
     author = {Dewar, Megan and Pike, David and Proos, John},
     title = {Connectivity in {Hypergraphs}},
     journal = {Canadian mathematical bulletin},
     pages = {252--271},
     year = {2018},
     volume = {61},
     number = {2},
     doi = {10.4153/CMB-2018-005-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-005-9/}
}
TY  - JOUR
AU  - Dewar, Megan
AU  - Pike, David
AU  - Proos, John
TI  - Connectivity in Hypergraphs
JO  - Canadian mathematical bulletin
PY  - 2018
SP  - 252
EP  - 271
VL  - 61
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-005-9/
DO  - 10.4153/CMB-2018-005-9
ID  - 10_4153_CMB_2018_005_9
ER  - 
%0 Journal Article
%A Dewar, Megan
%A Pike, David
%A Proos, John
%T Connectivity in Hypergraphs
%J Canadian mathematical bulletin
%D 2018
%P 252-271
%V 61
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-2018-005-9/
%R 10.4153/CMB-2018-005-9
%F 10_4153_CMB_2018_005_9

Cité par Sources :