A PTAS for $k$-hop MST on the Euclidean plane: Improving Dependency on $k$

Abstract

For any $\epsilon >0$, Laue and Matijević [CCCG'07, IPL'08] give a PTAS for finding a $(1+\epsilon )$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/\epsilon {)}^{O(k/\epsilon )}$. In this paper, we present an algorithm that runs in time $(n/\epsilon {)}^{O(\log k\cdot (1/\epsilon {)}^2\cdot {\log }^2(1/\epsilon ))}$. This gives an improvement on the dependency on $k$ on the exponent, while having a worse dependency on $\epsilon$. As in Laue and Matijević, we follow the framework introduced by Arora for Euclidean TSP. Our key ingredients include exponential distance scaling and compression of dynamic programming state tables.