Local Edge-Connectivity Augmentation in Hypergraphs is NP-complete

Zoltán Király, Ben Cosh, Bill Jackson


We consider a local edge-connectivity hypergraph augmentation problem. Specifically, we are given a hypergraph $G=(V,E)$ and a subpartition of $V$. We are asked to find the smallest possible integer $\ga$, for which there exists a set of size-two edges $F$, with $|F|=\ga$, such that in $G'=(V,E \cup F)$, the local edge-connectivity between any pair of vertices lying in the same set in the subpartition is at least a given value $k$. Using a transformation from the bin-packing problem, we show that the associated decision problem is NP-complete, even when $k=2$.

Bibtex entry:

AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Cosh, Ben and Jackson, Bill},
TITLE = {Local Edge-Connectivity Augmentation in Hypergraphs is NP-complete},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-06}

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