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

We present a data structure that we call a Dynamic Representative Set. In its most basic form, it is given two parameters 0<k<n and allows us to maintain a representation of a family F of subsets of {1,...,n}. It supports basic update operations (unioning of two families, element convolution) and a query operation that determines for a subset B of {1,...,n} whether there is a set A in F of size at most k-|B| such that A and B are disjoint.

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.