Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems

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 {\em et al.}~(1995). 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 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).

This is joint work with Bela Csaba and Marek Karpinski.