Abstract of Paper

Augmenting Local Edge-Connectivity between Vertices and Vertex Subsets in Undirected Graphs
by Toshimasa Ishii and Masayuki Hagiwara

Abstract:

Given an undirected multigraph $G=(V,E)$, a family ${\cal W}$
of sets $W \subseteq V$ of vertices (areas), and a requirement
function $r_{{\cal W}}: {\cal W} \rightarrow Z^+$ (where $Z^+$
is the set of positive integers), we consider the problem of augmenting
$G$ by the smallest number of new edges so that the resulting graph
has at least $r_{{\cal W}}(W)$ edge-disjoint paths between $v$ and $W$
for every pair of a vertex $v \in V$ and an area $W \in {\cal W}$.
So far this problem was shown to be NP-hard in the uniform
case of  $r_{{\cal W}}(W)=1$ for each $W \in {\cal W}$, and
polynomially solvable in the uniform case of  $r_{{\cal W}}(W)=r \geq 2$
for each $W \in {\cal W}$. In this paper, we show that
the problem can be solved in $O(m+$ $pr^* n5$ $\log{(n/r^*)})$
time, even in the general case of  $r_{{\cal W}}(W)\geq 3$
for each $W \in {\cal W}$, where $n=|V|$, $m=|\{\{u,v\}| (u,v)\in E\}|$,
$p=|{\cal W}|$, and $r^*=\max\{r_{{\cal W}}(W)\mid W \in {\cal W}\}$.
Moreover, we give an approximation algorithm which finds a solution
with at most one surplus edges over the optimal value in the same time
complexity in the general case of $r_{{\cal W}}(W)\geq 2$  for each
$W \in {\cal W}$.