The EATCSIPEC Nerode Prize 2016 for outstanding papers in the area of multivariate algorithmics is awarded to
Andreas Björklund, Lund University, Sweden
for his paper
Determinant Sums for Undirected Hamiltonicity. SIAM Journal of Computing 43(1): 280–299 (2014)
Appraisal Finding Hamiltonian cycles in graphs is among the most famous and notoriously hard combinatorial problems: formally, the task is to decide whether an nvertex graph contains a cycle that traverses each vertex exactly once. In 1962, Bellman, Held, and Karp used dynamic programming to solve the problem in time O(2^n n^2). It was a major surprise when Andreas Björklund showed what many thought was impossible: a significantly improved algorithm finding Hamiltonian cycles in time O^*(1.66^n).
The approach of Björklund is inspired both by the work of Lovász and Tutte on algebraic algorithms for matchings and Koutis' use of group algebra in randomized parameterized algorithms, and constitutes an ingenious algebraic formulation of the existence of paths and cycles. The tools and ideas developed by Björklund for finding Hamiltonian cycles have had a strong impact on the development of new parameterized algorithms including the Cut&Count framework for solving problems on graphs of bounded treewidth. Furthermore, Björklund’s sieving ideas underlie recent advances in practical pattern matching on massive graphs; here a fundamental advantage of Björklund’s framework is that it essentially evaluates the same polynomial over and over again with different inputs, making it ideal for vectorparallelization on modern parallel hardware.
In summary, the work of Björklund not only obtained a breakthrough advance on one of the truly classical hard problems where there had been no progress for half a century, it has given a roadmap for algebraizing combinatorial problems far beyond the original domain of finding Hamiltonian cycles.
The Award Committee: David Eppstein (University of California, Irvine) Daniel Marx (Hungarian Academy of Sciences) Jan Arne Telle (University of Bergen, Norway)
