Single-source shortest paths and strong connectivity in dynamic planar graphs (Q2051854)

The paper deals with the fully dynamic (both edge insertions and deletions, or reset of the source \(s\) of interest are allowed) single-source shortest paths problem for planar weighted digraphs. It is an extension of the static single-source shortest paths problem maintaining after edge insertions and deletions a data structure which supports shortest path queries originating in a fixed distinguished vertex. All known algorithms for the fully dynamic single-source shortest paths problem on general graphs are limited by the APSP conjecture: There exists no algorithm for solving the all-pairs shortest paths problem in general weighted graphs in time \(O(n^{3-\epsilon})\) for any constant \(\epsilon > 0\). Hence, no exact fully dynamic single-source shortest paths algorithms with \(O(n^{3-\epsilon})\) initialization time, \(O(m^{1-\epsilon})\) amortized update time and \(O(n^{1-\epsilon})\) query time at the same time is known (yet). However, restricting the attention to more structured graph classes and/or undirected graphs can give substantially better results. The main contribution of the paper results from focusing on planar weighted digraphs. The authors give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with \(O(n^{4/5}\log^2 n)\) worst-case update time and \(O(\log^2 n)\) query time. The initialization time is \(O(n\log^2 n)\). This is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for the aforementioned class of digraphs.