|
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:
| AUTHOR | = | {Bern{\'a}th, Attila}, |
| TITLE | = | {Node-to-area connectivity augmentation of hypergraphs without increasing the rank}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2009}, |
| NUMBER | = | {QP-2009-02} |