ALCOMFT-TR-02-26

Bela Csaba, Marek Karpinski and Piotr Krysta
Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems
MPI. Work packages 2 and 4. May 2002.

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. (STOC '95).

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 \not = 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 most of 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 (1995).

Postscript file: ALCOMFT-TR-02-26.ps.gz (131 kb).