Everyone is welcome to attend the N&O seminar of Jesper Nederlof, with the title 'On the worst-case complexity of the Traveling Salesman Problem'.
Abstract:
In 1960 Bellman, and independently Held and Karp, proposed a dynamic programming algorithm that solves the Traveling Salesman Problem with n cities in O(2^n * n^2) time and O(2^n) space in the worst case.
Since then, many beautiful techniques have been invented that significantly improve the worst-case time and/or space usage of the Bellman-Held-Karp algorithm in special cases such as the (Directed) Hamiltonian Cycle problem. In the first part of the talk I discuss some of these techniques and results. In the second part of the talk I focus on one approach from [1] that detects Hamiltonian Cycles in O(1.888^n) time in n-vertex undirected graph. This approach is based on a low rank matrix factorization. In particular, for an even integer t \geq 2, the Matchings Connectivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is a Hamiltonian cycle and 0 otherwise. I will sketch a proof that the rank of H_t in GF(2) is 2^{t/2-1} and that it can be used to detect Hamiltonian cycles in the claimed time bound. In the last part of the talk I briefly discuss some rec!
ent extensions of the second part.
[1] Marek Cygan, Stefan Kratsch, Jesper Nederlof: Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM 65(3): 12:1-12:46 (2018)
