← 研踪 PaperTrailarXiv:2611.06387 · v1
Partially Dynamic Algorithms for Single-Source Temporal Paths
首次提交 2026-11-04 19:51
版本更新 2026-11-04 19:51
雷达观测 2026-11-05 11:10
摘要
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with $n$ vertices. For the incremental scenario where updates are arc insertions, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the total number of arcs added to the arc-less graph. For the decremental scenario where updates are arc removals, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the number of arcs in the graph upon its initialization. We also consider earliest-arrival queries with an arbitrary departure-time threshold and develop an incremental algorithm with $O(n+Δ_s m\log m)$ total update time, $O(\log m)$ query time, and $O(n+m)$ space, where $Δ_s$ is the number of distinct departure times of arcs leaving the source. All of our algorithms are also capable of reporting an earliest arrival path from the source to the queried vertex $v$ in constant time per edge once the earliest arrival time at $v$ is known. We complement our positive results with conditional lower bounds based on the Online Boolean Matrix-Vector Multiplication conjecture (a.k.a. OMv conjecture). For both the incremental and the decremental scenarios, we show the non-existence of an algorithm with $O(n^{1-\varepsilon})$ amortized update time and $O(n^{2-\varepsilon})$ amortized query time, even if the algorithm is randomized and latencies on the arcs are uniform. For arbitrary departure-time queries, we also establish an OMv-based conditional lower bound showing that our incremental algorithm is optimal up to logarithmic factors on dense temporal graphs. Thus, efficient total running time is essentially the best outcome we can get. Our conditional lower bounds hold also for the case of undirected temporal graphs.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-04 19:51 · 最新观测版本
Partially Dynamic Algorithms for Single-Source Temporal Paths
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with $n$ vertices. For the incremental scenario where updates are arc insertions, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the total number of arcs added to the arc-less graph. For the decremental scenario where updates are arc removals, our algorithm has a constant query time and requires a total update time of $O(n + m \log m)$, where $m$ is the number of arcs in the graph upon its initialization. We also consider earliest-arrival queries with an arbitrary departure-time threshold and develop an incremental algorithm with $O(n+Δ_s m\log m)$ total update time, $O(\log m)$ query time, and $O(n+m)$ space, where $Δ_s$ is the number of distinct departure times of arcs leaving the source. All of our algorithms are also capable of reporting an earliest arrival path from the source to the queried vertex $v$ in constant time per edge once the earliest arrival time at $v$ is known. We complement our positive results with conditional lower bounds based on the Online Boolean Matrix-Vector Multiplication conjecture (a.k.a. OMv conjecture). For both the incremental and the decremental scenarios, we show the non-existence of an algorithm with $O(n^{1-\varepsilon})$ amortized update time and $O(n^{2-\varepsilon})$ amortized query time, even if the algorithm is randomized and latencies on the arcs are uniform. For arbitrary departure-time queries, we also establish an OMv-based conditional lower bound showing that our incremental algorithm is optimal up to logarithmic factors on dense temporal graphs. Thus, efficient total running time is essentially the best outcome we can get. Our conditional lower bounds hold also for the case of undirected temporal graphs.
查看此版本解读 →查看此版本原文 ↗