ECCC-Report TR98-031https://eccc.weizmann.ac.il/report/1998/031Comments and Revisions published for TR98-031en-usTue, 09 Jun 1998 19:16:56 +0300
Paper TR98-031
| Graph Properties that Facilitate Travelling |
Dimitris Fotakis,
Paul Spirakis
https://eccc.weizmann.ac.il/report/1998/031In 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.
Tue, 09 Jun 1998 19:16:56 +0300https://eccc.weizmann.ac.il/report/1998/031