In this work, we study two special cases of the metric Travelling Salesman
Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of
TSP(1,2) and Graph TSP are essentially as hard to approximate as general
instances of TSP(1,2).

Next, we present an NC algorithm for TSP(1,2) that produces a tour
of length at most n plus the cardinality of the Maximum Independent Set
of the input graph. Thus, it always achieves a ratio of 3/2, while the
best known parallel algorithm achieves the same ratio in RNC. Moreover,
a variant of this algorithm achieves in NC a constant approximation ratio
for Maximum Independent Set, if the optimal value of TSP(1,2) is at least
(1+\beta)n, for some constant \beta > 0.

Then, we prove that, given a graph and a partition of the vertices
into k cliques, optimal solutions for both Graph TSP and TSP(1,2) can
be found in time n^{O(k^2)}. Additionally, we show that optimal
solutions can be computed in time n^{\O(k)} for a certain class of
instances, and we conjecture that the time complexity can be improved to
n^{\O(k)} for any partition of a graph into k cliques.

Also, we obtain a 22/15-approximation algorithm for TSP in graphs
of diameter 3, and a 17/12(7/5) approximation algorithm for TSP in graphs
that have diameter 4(3) and contain a perfect, triangle-free
2-matching.