Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs

AbstractGiven an undirected multigraph G = (V, E), a family W of areas W ⊆ V, and a target connectivity k ≥ 1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between μ and W for every pair of a vertex μ ∈ V and an area W ∈ W . So far this problem was shown to be NP-complete in the case of k = 1. and polynomially solvable in the case of k = 2. In this paper, we show that the problem for k ≥ 3 can be solved in O(m + n (k3 + n2)(p + kn + n logn) logk + pkn3 log(n/k)) time, where n = ∣V∣, m = ∣{{u,v}∣(u, v) ∈ E}∣, and p = ∣ W∣