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 TSPconjecture, due to Goemans [17].
展开▼
