For a finite ground set V , we call a set-function r : 2V ! Z+ monotone, if r(X0) ü r(X) holds for each X0 µ X µ V , where Z+ is the set of nonnegative integers. Given an undirected multigraph G = (V;E) and a monotone requirement function r : 2V ! Z+, we consider the problem of augmenting G by a smallest number of new edges so that the resulting graph G0 satisfies dG0 (X) ü r(X) for each ; 6= X ? V , where dG(X) denotes the degree of a vertex set X in G. This problem includes the edge-connectivity augmentation problem, and in general, it is NP-hard even if a polynomial time oracle for r is available. In this paper, we show that the problem can be solved in O(n4(m+n log n+q)) time, under the assumption that each ; 6= X ? V satisfies r(X) ü 2 whenever r(X) > 0, where n = jV j, m = jffu; vg j (u; v) 2 Egj, and q is the time required to compute r(X) for each X µ V . |
(from crpit.com)
