TR98-031 Authors: Dimitris Fotakis, Paul Spirakis

Publication: 9th June 1998 19:16

Downloads: 1843

Keywords:

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.