Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems

ABSTRACT

We study the approximability of dense and sparse instances of the following problems: the minimum 2-edge-connected (2-EC) and 2-vertex-connected (2-VC) spanning subgraph, metric TSP with distances 1 and 2 (TSP (1,2)), maximum path packing, and the longest path (cycle) problems. The approximability of dense instances of these problems was left open in Arora et al. [3]. We characterize the approximability of all these problems by proving tight upper (approximation algorithms) and lower bounds (inapproximability). We prove that 2-EC, 2-VC and TSP (1,2) are Max SNP-hard even on 3-regular graphs, and provide explicit hardness constants, under P ≠ NP. We also improve the approximation ratio for 2-EC and 2-VC on graphs with maximum degree 3. These are the first explicit hardness results on sparse and dense graphs for these problems. We apply our results to prove bounds on the integrality gaps of LP relaxations for dense and sparse 2-EC and TSP (1,2) problems, related to the famous metric TSP conjecture, due to Goemans [17].

REFERENCES

• 1: N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
• 2: Noga Alon , Raphy Yuster , Uri Zwick, Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.326-335, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195179]
• 3: Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
• 4: Cristina Bazgan , Miklos Santha , Zsolt Tuza, On the Approximation of Finding A(nother) Hamilton Cycle in Cubic Hamilton Graphs (Extended Abstract), Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.276-286, February 25-27, 1998
• 5: Robert Carr , R. Ravi, A New Bound for the 2-Edge Connected Subgraph Problem, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.112-125, June 22-24, 1998
• 6: Joseph Cheriyan , András Sebö , Zoltán Szigeti, An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.126-136, June 22-24, 1998
• 7: Artur Czumaj , Andrzej Lingas, On approximability of the minimum-cost k-connected spanning subgraph problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.281-290, January 17-19, 1999, Baltimore, Maryland, United States
• 8: Elias Dahlhaus , Péter Hajnal , Marek Karpinski, On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs, Journal of Algorithms, v.15 n.3, p.367-384, Nov. 1993 [doi>10.1006/jagm.1993.1046]
• 9: R. Diestel. Graph Theory. Springer, N.Y., 1997.
• 10: L. Engebretsen. An explicit lower bound for TSP with distances one and two. In Proc. 16th STACS, LNCS, 1563, 373-382, 1999.
• 11: Lars Engebretsen , Marek Karpinski, Approximation Hardness of TSP with Bounded Metrics, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.201-212, July 08-12, 2001
• 12: Cristina G. Fernandes, A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem, Journal of Algorithms, v.28 n.1, p.105-124, July 1, 1998 [doi>10.1006/jagm.1998.0931]
• 13: W. Fernandez de la Vega , M. Karpinski, On the approximation hardness of dense TSP and other path problems, Information Processing Letters, v.70 n.2, p.53-55, April 30, 1999 [doi>10.1016/S0020-0190(99)00048-4]
• 14: A. Frank. Conservative weightings and ear decompositions of graphs. Combinatorica,13, 65-81, 1993.
• 15: A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
• 16: Naveen Garg , Vempala S. Santosh , Aman Singla, Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.103-111, January 25-27, 1993, Austin, Texas, United States
• 17: Michel X. Goemans, Worst-case comparison of valid inequalities for the TSP, Mathematical Programming: Series A and B, v.69 n.2, p.335-349, Aug. 25, 1995
• 18: Michel X. Goemans , Dimitris J. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Mathematical Programming: Series A and B, v.60 n.2, p.145-166, June 24, 1993 [doi>10.1007/BF01580607]
• 19: R. L. Graham , M. Grötschel , L. Lovász, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
• 20: D. Karger, R. Motwani and G. Ramkumar. On Approximating the Longest Path in a Graph. Algorithmica,18, 82-98, 1997.
• 21: R. M. Karp. Reducibility among Combinatorial Problems. In Complexity of Computer Computations, R. E. Miller & J. W. Thatcher (Eds.), Plenum, New York, 1972.
• 22: M. Karpinski. Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems. Algorithmica,30, 386-397, 2001.
• 23: Marek Karpinski, Approximating Bounded Degree Instances of NP-Hard Problems, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, p.24-34, August 22-24, 2001
• 24: Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994 [doi>10.1145/174652.174654]
• 25: J. Komlós, G. N. Sárközy and E. Szemerédi. Blow-up Lemma. Combinatorica,17(1), 109-123, 1997.
• 26: János Komlós , Gabor N. Sarkozy , Endre Szemerédi, An algorithmic version of the blow-up lemma, Random Structures & Algorithms, v.12 n.3, p.297-310, May 1998 [doi>10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q]
• 27: J. Komlós and M. Simonovits. Szemerédi's Regularity Lemma and its applications in graph theory. DIMACS Tech. Rep. 96-10, 1996.
• 28: Piotr Krysta , V. S. Anil Kumar, Approximation Algorithms for Minimum Size 2-Connectivity Problems, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.431-442, February 15-17, 2001
• 29: C. L. Monma , B. S. Munson , W. R. Pulleyblank, Minimum-weight two-connected spanning networks, Mathematical Programming: Series A and B, v.46 n.2, p.153-171, Feb. 1990 [doi>10.1007/BF01585735]
• 30: Christos H. Papadimitriou , Mihalis Yannakakis, The traveling salesman problem with distances one and two, Mathematics of Operations Research, v.18 n.1, p.1-11, Feb. 1993 [doi>10.1287/moor.18.1.1]
• 31: E. Szemerédi. Regular partitions of graphs. In Colloques Internationauz C.N.R.S. No. 260. Problémes Combinatoires et Théorie des Graphes, Orsay, 399-401, 1976.
• 32: Santosh Vempala , Adrian Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.262-273, September 05-08, 2000
• 33: Sundar Vishwanathan, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two, Information Processing Letters, v.44 n.6, p.297-302, Dec. 28, 1992 [doi>10.1016/0020-0190(92)90103-3]
• 34: Sundar Vishwanathan, An approximation algorithm for finding a long path in Hamiltonian graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.680-685, January 09-11, 2000, San Francisco, California, United States