Weighted k-Path and Other Problems in Almost O*(2k) Deterministic Time via Dynamic Representative Sets†

We present a data structure that we call a Dynamic Representative Set. In its most basic form, it is given two parameters $0\lt k\lt n$ and allows us to maintain a representation of a family $\mathcal{F}$ of subsets of $\{1, \ldots, n\}$. It supports basic update operations (unioning of two families, element convolution) and a query operation that determines for a set $B \subseteq\{1, \ldots, n\}$ whether there is a set $A \in \mathcal{F}$ of size at most $k-|B|$ such that A and B are disjoint. After $2^{k+O\left(\sqrt{k} \log ^{2} k\right)} n \log n$ preprocessing time, all operations use $2^{k+O\left(\sqrt{k} \log ^{2} k\right)} \log n$ 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 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\left(\sqrt{k} \log ^{2} k\right)}(n+m) \log n$ time (in the word RAM model where weights fit into a single word). Modulo the lower order term $2^{O\left(\sqrt{k} \log ^{2} k\right)}$, this answers a question that has been repeatedly posed as a major open problem in the field. Index Terms-Algorithms, Analysis of Algorithms and Problem Complexity