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 University Press

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

[1] [1] Bahmanian, M. A. and Sajna, M., Connection and Separation in hypergraphs. Theory Appl. Graphs 2 (2015), no. 2, Art. 5, 24. Google Scholar

[2] [2] Bäräsz, M., Becker, J., and Frank, A., An algorithm for source location in directed graphs. Oper. Res. Lett. 33 (2005), 221–230. http://dx.doi.Org/10.1016/j.orl.2004.07.005 Google Scholar

[3] [3] Bondy, J. A. and Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics, 244, Springer, New York, 2008. Google Scholar

[4] [4] Bretto, A., Hypergraph theory: An introduction. Mathematical Engineering, Springer, Cham, 2013. Google Scholar

[5] [5] Chekuri, C. and Xu, C., Computing minimum cuts in hypergraphs. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Barcelona, 2017), SIAM, Philadelphia, PA, 2017, pp. 1085–1100. Google Scholar

[6] [6] Cheng, E., Edge-augmentation of hypergraphs. Connectivity augmentation ofnetworks: structures and algorithms (Budapest, 1994). Math. Program. 84(1999), no. 3, Ser. B, 443–465. http://dx.doi.Org/10.1007/s101070050032 Google Scholar

[7] [7] Duchet, P., Hypergraphs. In: Handbook of combinatorics, Vol. 1, Elsevier Sei. B. V., Amsterdam, 1995, pp. 381–432. Google Scholar

[8] [8] Edmonds, J. and Karp, R. M., Theoretical improvements in algorithmic efficiencyfor networkflow Problems. In: Combinatorial Structure and their Applications, Proc. Calgary Internat. Conf., Calgarym Alta., Gordon and Breach, New York, 1970, pp. 93–96. Google Scholar

[9] [9] Frank, A., Edge-connection of graphs, digraphs, and hypergraphs. In: More sets, graphs and numbers, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006, pp. 93–141. Google Scholar

[10] [10] Karp, R. M., Reducibility among combinatorial problems. In: Complexity of Computer computations, Plenum Press, New York, 1972, pp. 85–103. Google Scholar

[11] [11] Nagamochi, H. and Ibaraki, T., Algorithmic aspects ofgraph Connectivity. Encyclopedia of Mathematics and its Applications, 123, Cambridge University Press, Cambridge, 2008. Google Scholar

[12] [12] Slater, P. J., A characterization ofsoft hypergraphs. Canad. Math. Bull. 21 (1978), 335–337. http://dx.doi.Org/10.4153/CMB-1978-058-5 Google Scholar

[13] [13] Voloshin, V. I.. Introduction to graph and hypergraph theory. Nova Science Publishers, Ine, New York, 2009. Google Scholar

[14] [14] Whitney, H., Congruent graphs and the Connectivity of graphs. Amer. J. Math. 54 (1932), 150–168. http://dx.doi.Org/10.2307/2371086 Google Scholar

Cité par Sources :