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