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\}$.