Sublinear Algorithms for TSP via Path Covers

We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related maximum path cover problem, which asks for a collection of vertex disjoint paths that include the maximum number of edges. We show that for any fixed $\epsilon > 0$, there is an algorithm that $(1/2 - \epsilon)$-approximates the maximum path cover size of an $n$-vertex graph in $\widetilde{O}(n)$ time. This improves upon a $(3/8-\epsilon)$-approximate $\widetilde{O}(n \sqrt{n})$-time algorithm of Chen, Kannan, and Khanna [ICALP'20]. Equipped with our path cover algorithm, we give $\widetilde{O}(n)$ time algorithms that estimate the cost of graphic TSP and $(1, 2)$-TSP up to factors of $1.83$ and $(1.5+\epsilon)$, respectively. Our algorithm for graphic TSP improves over a $1.92$-approximate $\widetilde{O}(n)$ time algorithm due to [CHK ICALP'20, Behnezhad FOCS'21]. Our algorithm for $(1,2)$-TSP improves over a folklore $(1.75 + \epsilon)$-approximate $\widetilde{O}(n)$-time algorithm, as well as a $(1.625+\epsilon)$-approximate $\widetilde{O}(n\sqrt{n})$-time algorithm of [CHK ICALP'20]. Our analysis of the running time uses connections to parallel algorithms and is information-theoretically optimal up to poly log $n$ factors. Additionally, we show that our approximation guarantees for path cover and $(1,2)$-TSP hit a natural barrier: We show better approximations require better sublinear time algorithms for the well-studied maximum matching problem.