Augmenting Edge-Connectivity between Vertex Subsets

Given a directed or undirected graph G=(V,E), a collection ${mathcal{R}}={(S_{i},T_{i}) mid i=1,2,ldots,|{mathcal{R}}|, S_{i},T_{i} subseteq V, S_{i} cap T_{i} =emptyset}$ of two disjoint subsets of V, and a requirement function $r: {mathcal{R}} tomathbb{R}_{+}$ , we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph $hat{G}$ satisfies $d_{hat{G}}(X)geq r(S,T)$ for all X?V, $(S,T) in{mathcal{R}}$ with S?X?V?T, where d _G (X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of $clog{|{mathcal{R}}|}$ , unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an ${mathrm{O}}(log{|{mathcal{R}}|})$ -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov’s algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662–670, 2008). This together with the negative result implies that the problem is ${varTheta}(log{|{mathcal{R}}|})$ -approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (Algorithmica, 56:413–436, 2010), Ishii and Hagiwara (Discrete Appl. Math., 154:2307–2329, 2006), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224–243, 2004). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions.