Minimum Augmentation of Edge-Connectivity with Monotone Requirements in Undirected Graphs

Ishii, T.

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 .

Cite as: Ishii, T. (2007). Minimum Augmentation of Edge-Connectivity with Monotone Requirements in Undirected Graphs. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 91-100.

(from crpit.com) (local if available)