QP-2009-02

Node-to-area connectivity augmentation of hypergraphs without increasing the rank

Attila Bernáth



Abstract

The rank-respecting node-to-area connectivity augmentation problem of hypergraphs is the following: given a hypergraph $H=(V,\cE)$ of rank at most $\gamma$, a collection of subsets $\cW$ of $V$ and a requirement function $r:\cW \to \Zset_+$, find a hypergraph $H'$ of minimum total size such that $\lambda_{H+H'}(x,W)\ge r(W)$ for any $W\in \cW$ and $x\in V$ and the rank of $H'$ is at most $\gamma$. This problem was investigated by Ishii and Hagiwara for $\gamma=2$ (i.e. graphs). Though the problem is NP-complete (even if $H$ is the empty graph and $r(W)=1$ for every $W\in \cW$), they observed that the assumption $r\ge 2$ surprisingly makes the problem tractable and they gave a polynomial algorithm solving it in the $\gamma=2$ case. In this note we solve this problem for any $\gamma\ge 3$.


Bibtex entry:

@techreport{egresqp-09-02,
AUTHOR = {Bern{\'a}th, Attila},
TITLE = {Node-to-area connectivity augmentation of hypergraphs without increasing the rank},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {QP-2009-02}
}


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