Bipartite TSP in o(1.9999\8319) time, assuming quadratic time matrix multiplication

Abstract

The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n22n) time. Since then it has been a notorious problem to improve the runtime to O((2−є)n) for some constant є>0. In this work we establish the following progress: If (s× s)-matrices can be multiplied in s2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999n) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MinHamPair: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MinHamPair based on a new sparse cut-based factorization of the ‘matchings connectivity matrix’, introduced by Cygan et al. [JACM’18].