Dynamic Detours
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917460771340288 |
|---|---|
| author | Dadush, Daniel Pilipczuk, Michał Reinald, Amadeus Sokołowski, Marek Włodarczyk, Michał |
| author_facet | Dadush, Daniel Pilipczuk, Michał Reinald, Amadeus Sokołowski, Marek Włodarczyk, Michał |
| contents | Fix a parameter $k\in \mathbf{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries:
- Long $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $k$?
- Long $(u,v)$-detour: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $\text{dist}_G(u,v)+k$?
- Even/odd $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of even/odd length?
The amortized time of executing an update or answering a query is $2^{O(k^3)} \log n + O(\log^2 n \log^2 \log n)$ in the first two cases, and $O(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$.
The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about $(u,v)$-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_03225 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dynamic Detours Dadush, Daniel Pilipczuk, Michał Reinald, Amadeus Sokołowski, Marek Włodarczyk, Michał Data Structures and Algorithms Fix a parameter $k\in \mathbf{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries: - Long $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $k$? - Long $(u,v)$-detour: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $\text{dist}_G(u,v)+k$? - Even/odd $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of even/odd length? The amortized time of executing an update or answering a query is $2^{O(k^3)} \log n + O(\log^2 n \log^2 \log n)$ in the first two cases, and $O(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about $(u,v)$-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components. |
| title | Dynamic Detours |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.03225 |