[DMANET] Reminder: First Talk Today in Online Seminar on Frontiers of Parameterized Complexity

The first talk of the seminar will be held today.

https://uib.zoom.us/j/4231169675
Meeting ID: 423 116 9675
Password: name of the W[1]-complete problem, 6 letters, all capital.
Also known as a set of pairwise adjacent vertices.


April 23, 2020
Jesper Nederlof, Utrecht University
Title: Bipartite TSP in O(1.9999^n) 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(n^2*2^n) time. Since
then it has been a notorious problem to improve the runtime to
O((2-eps)^n) for some constant eps >0. In this work we establish the
following progress: If (s x 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.

On a high level, our approach is via a new problem called the
MINHAMPAIR problem: 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].
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************