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

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 𝑛 cities can be solved in 𝑂 (𝑛 2 2 𝑛 ) time. Since then it has been a notorious problem to improve the runtime to 𝑂 ((2 -𝜀) 𝑛 ) for some constant 𝜀 > 0. In this work we establish the following progress: If (𝑠 ×𝑠)-matrices can be multiplied in 𝑠 2+𝑜 (1) time, than all instances of TSP in bipartite graphs can be solved in 𝑂 (1.9999 𝑛 ) 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 Min-HamPair: 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].