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

摘要

Given an undirected multigraph G = (V, E), a family W of areas W is contained in 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 ∈ 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(k~3 + n~2)(p + kn + n log n) log k + pkn~3 log(n/k)) time, where n = |V|, m = |{{u, v}|(u, v) ∈ E}|, and p = |W|.