Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs

For a finite ground set VV, we call a set-function r:2V→Z+r:2V→Z+ monotone, if r(X′)≥r(X)r(X′)≥r(X) holds for each X′⊆X⊆VX′⊆X⊆V, where Z+Z+ is the set of nonnegative integers. Given an undirected multigraph G=(V,E)G=(V,E) and a monotone requirement function r:2V→Z+r:2V→Z+, we consider the problem of augmenting GG by a smallest number of new edges, so that the resulting graph G′G′ satisfies dG′(X)≥r(X)dG′(X)≥r(X) for each 0̸≠X⊂V0̸≠X⊂V, where dG(X)dG(X) denotes the degree of a vertex set XX in GG. This problem includes the edge-connectivity augmentation problem, and in general, it is NP-hard, even if a polynomial time oracle for rr is available. In this paper, we show that the problem can be solved in O(n4(m+nlogn+q))O(n4(m+nlogn+q)) time, under the assumption that each 0̸≠X⊂V0̸≠X⊂V satisfies r(X)≥2r(X)≥2 whenever r(X)>0r(X)>0, where n=|V|n=|V|, m=|{{u,v}∣(u,v)∈E}|m=|{{u,v}∣(u,v)∈E}|, and qq is the time required to compute r(X)r(X) for each X⊆VX⊆V.