Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs
Given an undirected multigraph G = (V, E), a familyW of areas W subset of 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 v and W for every pair of a vertex v is an element of V and an area W is an element of 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(k(3) + n(2))(p + kn + n log n)log k + pkn(3) log (n/k)) time, where n = vertical bar V vertical bar, m = vertical bar{{u, v}vertical bar(u, v) is an element of E}vertical bar, and p = vertical bar W vertical bar.
edge-connectivity undirected graph connectivity augmentation problem node-to-area connectivity polynomial time deterministic algorithm edge-splitting