Augmenting Edge-Connectivity between Vertex Subsets

作者：Ishii Toshimasa^*; Makino Kazuhisa

来源：Algorithmica, 2014, 69(1): 130-147.

DOI：10.1007/s00453-012-9724-5

• Graph algorithm
• Approximation algorithm
• Edge-connectivity
• Modulotone function

Given a directed or undirected graph G=(V,E), a collection of two disjoint subsets of V, and a requirement function , 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 satisfies for all XaS dagger V, with SaS dagger XaS dagger 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. %26lt;br%26gt;In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of , 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 -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov%26apos;s algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662-670, 2008). This together with the negative result implies that the problem is -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). %26lt;br%26gt;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.

• 出版日期2014-5