A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs
Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk · SIAM Journal on Computing · 2022
There are numerous examples of the so-called “square root phenomenon” in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter $k$, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in $\mathcal{O}(\sqrt{k})$ instead of $\mathcal{O}(k)$ (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals $T$ by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number $k=|T|$ of terminals is regarded as the parameter. We show that Subset TSP can be solved in time $2^{\mathcal{O}(\sqrt{k}\log k)}\cdot n^{\mathcal{O}(1)}$ even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [ SODA 2014, SIAM, Philadelphia, 2014, pp. 1812--1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.