Augmenting Edge-Connectivity between Vertex Subsets

Ishii, T. and Makino, K.

Given a graph G = (V,E) and a requirement function r : W1 x W2 -> R+ for two families W1, W2 \subseteq 2V - {0}, we consider the problem (called area-toarea edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph �G satisfies \delta �G(X) � r(W1;W2) for all X \subseteq V , W1 in W1, and W2 in W2 with W1 \subseteq X \subseteq V - W2, where \delta 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 c log \alpha(W1,W2), unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation, where \alpha(W1,W2) denotes the number of pairs W1 in W1 and W2 in W2 with r(W1;W2) > 0. We also provide an O(log \alpha(W1,W2))-approximation algorithm for the area-to-area edge-connectivity augmentation problem. This together with the negative result implies that the problem is \Theta(log \alpha(W1,W2))-approximable, unless P=NP, which solves open problems for nodeto- area edge-connectivity augmentation. Furthermore, we characterize the node-toarea and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and extended modulotone functions.