A subexponential parameterized algorithm for Subset TSP on planar graphs

Given a graph G and a subset S of vertices, the Subset TSP problem asks for a shortest closed walk in G visiting all vertices of S. The problem can be solved in time 2 k · n O (1) using the classical dynamic programming algorithms of Bellman and of Held and Karp, where k = | S | and n = | V ( G )|. Our main result is showing that the problem can be solved in time if G is a planar graph with weights that are integers no greater than W. While similar speedups have been observed for various paramterized problems on planar graphs, our result cannot be simply obtained as a consequence of bounding the treewidth of G or invoking bidimensionality theory. Our algorithm consists of two steps: (1) find a locally optimal solution, and (2) use it to guide a dynamic program. The proof of correctness of the algorithm depends on a treewidth bound on a graph obtained by combining an optimal solution with a locally optimal solution.

Authors

• Philip N. Klein
• Dániel Marx

Keywords

No keywords are indexed for this paper.