Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #98008 (March, 1998)

Multigraph augmentation under biconnectivity and general edge-connectivity requirements
by Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki

Given an undirected multigraph $G=(V,E)$ and requirement functions $r_\lambda:$ $ {V}\choose{2} $ $ \rightarrow Z^+$ and $r_\kappa:$ ${V}\choose{2}$ $ \rightarrow Z^+$ (where $ {V}\choose{2} $ is the set of all pairs of vertices and $Z^+$ is the set of nonnegative integers), we consider the problem of augmenting $G$ by the smallest number of new edges so that the local edge-connectivity and vertex-connectivity between every pair $x,y \in V$ become at least $r_\lambda(x,y)$ and $r_\kappa(x,y)$, respectively. In this paper, we show that the problem can be solved in $O(n^3(m+n) \log{(n^2/(m+n))})$ time in the special case of $r_\kappa(x,y)=2$ for all $x,y \in V$ (but $r_\lambda$ remains general), where $n$ and $m$ are the numbers of vertices and pairs of adjacent vertices in $G$, respectively. This time complexity can be improved to $O((nm+n^2\log{n})\log{n})$, in case of the uniform requirement $r_\lambda(x,y)=k$ for all $x,y \in V$. Furthermore, for the general $r_\lambda$, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed $k^*=\max\{r_\lambda(x,y) \mid x,y \in V\}$.