Approximation algorithm for k-node connected subgraphs via critical graphs

ABSTRACT

We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were O(min (k,n/√n-k)) for both directed and undirected graphs, and O(ln k) for undirected graphs with n ≥ 6k², where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O(k/n-kln ² k, which is O(ln² k) except for very large values of k, namely, k=n-o(n). This algorithm is based on a new result on l-connected p-critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio O(√n ln k) for all values of n,k. Combining these two gives an algorithm with approximation ratio O(ln k • min (√k, k/n-k ln k)), which asymptotically improves the best known approximation guarantee for directed graphs for all values of n,k, and for undirected graphs for k> √n⁄6. Moreover, this is the first algorithm that has an approximation guarantee better than Θ(k) for all values of n,k. Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation to the problem.As a byproduct, we also get the following result which is of independent interest. To get a faster implementation of our algorithms, we consider the problem of adding a minimum-cost edge set to increase the outconnectivity of a directed graph by Δ a graph is said to be l-outconnected from its node r if it contains l internally disjoint paths from r to any other node. The best known time complexity for the later problem is O(m³). For the particular case of Δ=1, we give a primal-dual algorithm with running time O(m²).

REFERENCES

• 1: V. Auletta, Y. Dinitz, Z. Nutov, and D. Parente, A 2-approximation algorithm for finding an optimum 3-vertex connected spanning subgraph, Journal of Algorithms 32, 1999, 21--30.
• 2: J. Cheriyan, T. Jordán, and Z. Nutov, On rooted node-connectivity problems, Algorithmica 30 (special issue on APPROX'98), 2001, 353--375.
• 3: Joseph Cheriyan , Ramakrishna Thurimella, Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching, SIAM Journal on Computing, v.30 n.2, p.528-560, 2000 [doi>10.1137/S009753979833920X]
• 4: Joseph Cheriyan , Santosh Vempala , Adrian Vetta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509955]
• 5: A. Frank, Connectivity augmentation problems in network design, Mathematical Programming, State of the Art, J. R. Birge and K. G. Murty eds., 1994, 34--63.
• 6: 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]
• 7: A. Frank and É. Tardos, An application of submodular flows, Linear Algebra and its Applications 114/115, 1989, 329--348.
• 8: Harold N. Gabow, A representation for crossing set families with applications to submodular flow problems, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.202-211, January 25-27, 1993, Austin, Texas, United States
• 9: Handbook of Combinatorics, Vol. 1 Ch. 7, L. Graham, M. Grötschel, and L. Lovász Eds., 1995.
• 10: Tibor Jordán, On the optimal vertex-connectivity augmentation, Journal of Combinatorial Theory Series B, v.63 n.1, p.8-20, Jan. 1995 [doi>10.1006/jctb.1995.1002]
• 11: Tibor Jordán, On the existence of (k,l)-critical graphs, Discrete Mathematics, v.179 n.1-3, p.273-275, Jan. 15, 1998 [doi>10.1016/S0012-365X(97)00100-3]
• 12: 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
• 13: G. Kortsarz and Z. Nutov, Approximating node connectivity problems via set covers, Algorithmica 37, 2003, 75--92.
• 14: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052]
• 15: M. Kriesell, Upper bounds to the number of vertices in a k-critically n-connected graph, Graphs and Combinatorics 18, 2002, no. 1, 133--146.
• 16: W. Mader, Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen, Archive der Mathematik 23, 1972, 219--224.
• 17: W. Mader, Minimal n-fach in minimalen n-fach zusammenhängenden Digraphen, J. Combinatorial Theory Series B, 38, 1985, 102--117.
• 18: W. Mader, Endlichkeitsätze für k-kritische Graphen (German), Math. Ann. 229, 1977, 143--153.
• 19: W. Mader, On k-con-critically n-connected graphs, Journal of Combinatorial Theory Series B, v.86 n.2, p.296-314, November 2002 [doi>10.1006/jctb.2002.2129]
• 20: W. Mader, High Connectivity Keeping Sets In n-Connected Graphs, Combinatorica, v.24 n.3, p.441-458, July 2004 [doi>10.1007/s00493-004-0027-6]
• 21: W. Mader, Connectivity and edge-connectivity in finite graphs, Surveys in Combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979), 66--95, London Math. Soc. Lecture Notes Ser., 38, Cambridge Univ. Press, 1979.
• 22: W. Mader, On k-critically n-connected graphs, Progress in Graph Theory (Waterloo, Ont., 1982), 389--398, Academic Press, Toronto, On, 1984.
• 23: B. Maurer and P. Slater, On k-critical, n-connected graphs, Discrete Mathematics 20, 1988, 255--262.
• 24: R. Ravi and D. P. Williamson, An approximation algorithm for minimum-cost vertex-connectivity problems, Algorithmica 18, 1997, 21--43.
• 25: R. Ravi and D. P. Williamson, Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems, Algorithmica 34(1), 2002, 98--107.
• 26: J. Su, Proof of Slater's conjecture on k-critical n-connected graphs, Kexue Tongbao (English Ed. ) 33, 1988, no. 20, 1675--1678.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms