Weighted $k$-Path and Other Problems in Almost $O^{\ast }(2^k)$ Deterministic Time via Dynamic Representative Sets

Abstract

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 $\mathcal{F}$ of subsets of $\{1,\dots ,n\}$. It supports basic update operations (unioning of two families, element convolution) and a query operation that determines for a set $B\subseteq \{1,\dots ,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(\sqrt{k}{\log }^{2}k)}n\log n$ preprocessing time, all operations use $2^{k+O(\sqrt{k}{\log }^{2}k)}\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(\sqrt{k}{\log }^{2}k)}(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 }^{2}k)}$, this answers a question that has been repeatedly posed as a major open problem in the field.

22 pages, to appear at FOCS 2025 (online video available at FOCS youtube channel)