Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915663562407936 |
|---|---|
| author | Nederlof, Jesper |
| author_facet | Nederlof, Jesper |
| contents | 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,\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08583 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets Nederlof, Jesper Data Structures and Algorithms 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,\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. |
| title | Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.08583 |