论文标题
针对自适应对手的定向图中的次级动态路径报告
Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary
论文作者
论文摘要
我们研究动态定向图中的可达性和最短路径问题。虽然代数动态数据结构支持边缘更新和可及性/距离查询已有很长时间了，但通常不允许在同一时间范围内报告基础路径，尤其是针对自适应对手。 在本文中，我们开发了针对自适应对手的第一个已知的完全动态的可及性数据结构，并为两个自然变体提供了支撑边的更新和路径查询：（1）点对点路径报告，以及（2）单源可达性树报告。对于DAGS中的点对点查询，我们实现了$ O（n^{1.529}）$糟糕的更新和查询界限，而对于DAG中的树报告，最差的案例范围为$ O（n^{1.765}）$。更重要的是，我们展示了如何以将界限增加到$ n^{1+5/6+o（1）} $并使更新时间摊销的成本，以将这些算法提升到一般图表上工作。在实现这一目标的途中，我们获得了两个有趣的亚物种。我们为拓扑顺序（在DAG中）和强烈连接的组件提供了次级全动态算法。据我们所知，这种算法以前尚未描述。 此外，我们还提供确定性的增量数据结构，以达到可达性和最短路径，这些路径可以处理边缘插入，并报告次级最差的案例时间范围内的相应路径。为了达到可及性和$（1+ε）$ - 加权挖掘的最短路径，这些边界与最著名的动态矩阵逆随机界限符合完全动态的可及性[V.D.Brand，Nanongkai和Saranurak，focs'19]。对于未加权图中的确切最短路径，以增量设置中获得的界限在多个已知的随机更新/距离查询边界上在完全动态的设置中进行了多个评价。
We study reachability and shortest paths problems in dynamic directed graphs. Whereas algebraic dynamic data structures supporting edge updates and reachability/distance queries have been known for quite a long time, they do not, in general, allow reporting the underlying paths within the same time bounds, especially against an adaptive adversary. In this paper we develop the first known fully dynamic reachability data structures working against an adaptive adversary and supporting edge updates and path queries for two natural variants: (1) point-to-point path reporting, and (2) single-source reachability tree reporting. For point-to-point queries in DAGs, we achieve $O(n^{1.529})$ worst-case update and query bounds, whereas for tree reporting in DAGs, the worst-case bounds are $O(n^{1.765})$. More importantly, we show how to lift these algorithms to work on general graphs at the cost of increasing the bounds to $n^{1+5/6+o(1)}$ and making the update times amortized. On the way to accomplishing that, we obtain two interesting subresults. We give subquadratic fully dynamic algorithms for topological order (in a DAG), and strongly connected components. To the best of our knowledge, such algorithms have not been described before. Additionally, we provide deterministic incremental data structures for reachability and shortest paths that handle edge insertions and report the respective paths within subquadratic worst-case time bounds. For reachability and $(1+ε)$-approximate shortest paths in weighted digraphs, these bounds match the best known dynamic matrix inverse-based randomized bounds for fully dynamic reachability [v.d.Brand, Nanongkai and Saranurak, FOCS'19]. For exact shortest paths in unweighted graphs, the obtained bounds in the incremental setting polynomially improve upon the respective best known randomized update/distance query bounds in the fully dynamic setting.
