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 n cities can be solved in O(n 22 n ) 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 s 2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999 n ) 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.