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

摘要

For a finite ground set V, we call a set-function r : 2^V → Z⁺ monotone, if r(X') ≥ r(X) holds for each X'⊆ X ⊆ V, where Z⁺ is the set of nonnegative integers. Given an undirected multigraph G = (V, E) and a monotone requirement function r: 2^V → Z⁺, we consider the problem of augmenting G by a smallest number of new edges so that the resulting graph G' satisfies dG'(X) ≥ r(X) for each O ≠ 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(n⁴(m + n log n + q)) time, under the assumption that each O ≠ X ⊂ V satisfies r(X) ≥ 2 whenever r(X) 0, where n |V|, m = |{{u, v}| (u, v) ε E}|, and q is the time required to compute r(X) for each X ⊆ V.