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