Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph

Attila Bernáth, Roland Grappe, Zoltán Szigeti


Given a hypergraph, a partition of its vertex set and an integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k-edge-connected. This problem is a common generalization of the following two problems: edge-connectivity augmentation of graphs with partition constraints (J. Bang-Jensen, H. Gabow, T. Jordán, Z. Szigeti, Edge-connectivity augmentation with partition constraints, SIAM J. Discrete Math. Vol. 12, No. 2 (1999) 160-207) and edge-connectivity augmentation of hypergraphs by adding graph edges (J. Bang-Jensen, B. Jackson, Augmenting hypergraphs by edges of size two, Math. Program. Vol. 84, No. 3 (1999) 467-481). We give a min-max theorem for this problem, that implies the corresponding results on the above mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila and Grappe, Roland and Szigeti, Zolt{\'a}n},
TITLE = {Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-03}

Last modification: 29.12.2020. Please email your comments to Tamás Király!