Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time

Our data structure has many algorithmic consequences that improve over previous works. One application is a deterministic algorithm for the Weighted Directed k-Path problem, one of the central problems in the field of parameterized complexity. Our algorithm takes as input an n-vertex directed graph G=(V,E) with edge lengths and an integer k, and it outputs the minimum edge length of a path on k vertices in 2^{k+O(sqrt{k}log^2k)}(n+m)log n time (in the word RAM model where weights fit into a single word). Modulo the lower order term 2^{O(sqrt{k}log^2k)}, this answers a question that has been repeatedly posed as a major open problem in the field.