Approximating connectivity augmentation problems

ABSTRACT

Let G = (V, E) be a graph and let S ⊆ V. The S-connectivity λs(u, v; G) of u and 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 Problem (CAP) is: given a graph G = (V, E), a node subset S ⊆ V, and a nonnegative integer requirement function r(u, v) on the set of pairs of nodes, add a minimum size set F of new edges to G so that λs(u, v; G + F) ≥ r(u, v) holds for all u, v ∈ V. Three extensively studied particular cases are: the edge- (S = θ), the node- (S = V), and the element- (r(u, v) = 0 whenever u ∈ S or v ∈ S) CAP. A polynomial algorithm for edge- CAP was developed by A. Frank [8]. In this paper we consider the element-CAP and the node-CAP, that are NP- hard even for r(u, v) ∈ {0, 2}. Our main result is a 7/4- approximation algorithm for the element-CAP, improving the previously best known 2-approximation. For the {0, k}- element-CAP (with r(u, v) ∈ {0, k}) and for the {0, 1, 2}-element-CAP we give a 3/2-approximation algorithm. The approximation ratios are based on a new lower bound on the number of edges needed to cover a skew-supermodular set function. For the node-CAP we establish the following approximation threshold: the {0, k}-node-CAP cannot be approximated within O(2^log-1-∈n) for any fixed ∈ > 0, unless NP ⊆ DTIME(n^Polylog(n)); thus the node-CAP is unlikely to have a polylogarithmic approximation.

REFERENCES

• 1: J. Bang-Jensen and B. Jackson, Augmenting hypergraphs with edges of size two, Math. Programming84 (1999), 467--481.
• 2: A. Benczúr and A. Frank, Covering symmetric supermodular functions by graphs, Math. Program.84 (1999), 483--503.
• 3: B. Cosh, B. Jackson, Z. Kiraly, Local connectivity augmentation in hypergraphs is NP-complete, manuscript.
• 4: G. R. Cai and R. G. Sun, The minimum augmentation of any graph to k-edge connected graph, Networks 19, 1988, 151--172.
• 5: J. Cheriyan, S. Vempala, and A. Vetta, Network design via iterative rounding of setpair relaxations, manuscript.
• 6: Yefim Dinitz , Zeev Nutov, A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.509-518, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225268]
• 7: K. P. Eswaran and R. E. Tarjan, Augmentation problems, SIAM J. Comput.5 (1976), 653--665.
• 8: András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
• 9: A. Frank, Connectivity augmentation problems in network design, in Mathematical Programming:State of the Art (1994), eds. J. R. Birge and K. G. Murty, 34--63.
• 10: A. Frank, Applications of relaxed submodularity, in: Proc. International Congress of Mathematicians, Berlin 1998, Vol. III: Invited Lectures, Documenta Mathematica, Extra Volume ICM 1998, eds. G. Fischer and U. Rehmann, 343--354.
• 11: A. Frank, Edge-connection of graphs, digraphs, and hypergraphs, Chapter 6, EGRES TR No 2001-11, July 2001.
• 12: András Frank, On a theorem of Mader, Discrete Mathematics, v.101 n.1-3, p.49-57, May 29, 1992 [doi>10.1016/0012-365X(92)90589-8]
• 13: András Frank , Tibor Jordán, Minimal edge-coverings of pairs of sets, Journal of Combinatorial Theory Series B, v.65 n.1, p.73-110, Sept. 1995 [doi>10.1006/jctb.1995.1044]
• 14: T. Fleiner and T. Jordán, Covering and structures of crossing families, in: Connectivity Augmentation of Networks: Structures and algorithms, Math. Programming (ed. A. Frank), Ser. B, Vol. 84, No. 3, 1999, 505--518.
• 15: K. Jain, An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.339, October 14-17, 2001
• 16: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: Tsan-sheng Hsu, Undirected Vertex-Connectivity Structure and Smallest Four-Vertex-Connectivity Augmentation, Proceedings of the 6th International Symposium on Algorithms and Computation, p.274-283, December 04-06, 1995
• 18: K. Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Combinatorica21 (1), 2001, 39--60.
• 19: B. Jackson and T. Jordán, Connectivity Augmentation of Graphs, Electronic Notes in Discrete Mathematics, Vol. 5 (July 2000).
• 20: Bill Jackson , Tibor Jordán, A Near Optimal Algorithm for Vertex Connectivity Augmentation, Proceedings of the 11th International Conference on Algorithms and Computation, p.312-325, December 18-20, 2000
• 21: Bill Jackson , Tibor Jordán, Independence Free Graphs and Vertex Connectivity Augmentation, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.264-279, June 13-15, 2001
• 22: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 23: G. Kortsarz, R. Krauthgamer, and J. R. Lee, Hardness of approximation for vertex-connectivity network design problems, manuscript.
• 24: W. Mader, A reduction method for edge-connectivity in graphs, Ann. discrete Math 3, 1978, 145--164.
• 25: Hiroshi Nagamochi , Toshimasa Ishii, On the minimum local-vertex-connectivity augmentation in graphs, Discrete Applied Mathematics, v.129 n.2-3, p.475-486, 01 August 2003 [doi>10.1016/S0166-218X(02)00580-2]
• 26: H. Nagamochi, Recent development of graph connectivity augmentation algorithms, IEICE Trans. Inf. and Syst. volE83-D3, March 2000.
• 27: Z. Nutov, Approximating rooted connectivity augmentation problems, manuscript.
• 28: David Peleg, Approximation Algorithms for the Label-CoverMAX and Red-Blue Set Cover Problems, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.220-230, July 05-07, 2000
• 29: J. Plesnik, Minimum block containing a given graph, Archiv der Mathematik, Vol. XXVII (1976), Fasc. 6, 668--672.
• 30: Z. Szigeti, Hypergraph connectivity augmentation, Math. Program.84 (1999), 519--527.
• 31: Toshimasa Watanabe , Akira Nakamura, Edge-connectivity augmentation problems, Journal of Computer and System Sciences, v.35 n.1, p.96-144, Aug. 1987 [doi>10.1016/0022-0000(87)90038-9]