Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E)G=(V,E), a family WW of sets W⊆VW⊆V of vertices (areas), and a requirement function r:Wr:W→Z+→Z+ (where Z+Z+ is the set of nonnegative integers), we consider the problem of augmenting G   by the smallest number of new edges so that the resulting graph has at least r(W)r(W) edge-disjoint paths between vv and W   for every pair of a vertex v∈Vv∈V and an area W∈WW∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1r(W)=1 for each W∈WW∈W, and polynomially solvable in the uniform case of r(W)=r⩾2r(W)=r⩾2 for each W∈WW∈W. In this paper, we show that the problem can be solved in O(m+pn4(r*+logn)) time, even if r(W)⩾2r(W)⩾2 holds for each W∈WW∈W, where n=|V|n=|V|, m=|{{u,v}|(u,v)∈E}|m=|{{u,v}|(u,v)∈E}|, p=|W|p=|W|, and r*=max{r(W)∣W∈W}r*=max{r(W)∣W∈W}.