Approximating Connectivity Augmentation Problems

作者：Nutov Zeev^*

来源：ACM Transactions on Algorithms, 2009, 6(1): 5.

DOI：10.1145/1644015.1644020

• Approximation algorithms
• hardness of approximation
• connectivity augmentation
• element-connectivity
• node-connectivity

Let G = (V, E) be an undirected graph and let S subset of V. The S-connectivity lambda(S)(G)(u, v) of a node pair (u, v) in G is the maximum number of uv-paths that no two of them have an edge or a node in S-{u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G = (V, E), a node subset S subset of V, and a nonnegative integer requirement function r (u, v) on V x V, add a minimum size set F of new edges to G so that lambda(S)(G+F)(u, v) >= r (u, v) for all (u, v) is an element of V x V. Three extensively studied particular cases are: the Edge-CA (S = empty set), the Node-CA (S = V), and the Element-CA (r(u, v) = 0 whenever u is an element of S or v is an element of S). A polynomialtime algorithm for Edge-CA was developed by Frank. In this article we consider the Element-CA and the Node-CA, that are NP-hard even for r (u, v) is an element of {0, 2}. The best known ratios for these problems were: 2 for Element-CA and O(r(max) . ln n) for Node-CA, where r(max) = max(u,v is an element of V) r (u, v) and n = vertical bar V vertical bar. Our main result is a 7/4-approximation algorithm for the Element-CA, improving the previously best known 2-approximation. For Element-CA with r (u, v) is an element of {0, 1, 2} we give a 3/2-approximation algorithm. These approximation ratios are based on a new splitting-off theorem, which implies an improved lower bound on the number of edges needed to cover a skew-supermodular set function. For Node-CA we establish the following approximation threshold: Node-CA with r (u, v) is an element of {0, k} cannot be approximated within O(2(log1-epsilon) n) for any fixed epsilon > 0, unless NP subset of DTIME(n(polylog(n))).

• 出版日期2009-12