|
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2009}, |
| NUMBER | = | {TR-2009-06} |