{"ID":2831200,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.08583","arxiv_id":"2512.08583","title":"Weighted $k$-Path and Other Problems in Almost $O^*(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\u003c k \u003c 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(\\sqrt{k}\\log^2k)}n \\log n$ preprocessing time, all operations use $2^{k+O(\\sqrt{k}\\log^2k)}\\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^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.","short_abstract":"We present a data structure that we call a Dynamic Representative Set. In its most basic form, it is given two parameters $0\u003c k \u003c 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) an...","url_abs":"https://arxiv.org/abs/2512.08583","url_pdf":"https://arxiv.org/pdf/2512.08583v1","authors":"[\"Jesper Nederlof\"]","published":"2025-12-09T13:22:56Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}