Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs

This paper studies the dynamic single-source shortest paths (SSSP) in Erdös-Rényi random graphs generated by G(n, p) model. In 2014, Ding and Lin (AAIM 2014, LNCS 8546, 197–207) first considered the dynamic SSSP in general digraphs with arbitrary positive weights, and devised a nontrivial local search algorithm named DSPI which takes at most \(O(n\cdot \max \{1, n\log n / m\})\) expected update time to handle a single weight increase, where n is the number of nodes and m is the number of edges in the digraph. DSPI also works on undirected graphs. This paper analyzes the expected update time of DSPI dealing with edge weight increases or edge deletions in Erdös-Rényi (a.k.a., G(n, p)) random graphs. For weighted G(n, p) random graphs with arbitrary positive edge weights, DSPI takes at most \(O(h(T_s))\) expected update time to deal with a single edge weight increase as well as \(O(pn^2 h(T_s))\) total update time, where \(h(T_s)\) is the height of input SSSP tree \(T_s\). For G(n, p) random graphs, DSPI takes \(O(\ln n)\) expected update time to handle a single edge deletion as well as \(O(pn^2 \ln n)\) total update time when \(20\ln n / n \le p < \sqrt{2\ln n / n}\), and O(1) expected update time to handle a single edge deletion as well as \(O(pn^2)\) total update time when \(p > \sqrt{2\ln n / n}\). Specifically, DSPI takes the least total update time of \(O(n\ln n h(T_s))\) for weighted G(n, p) random graphs with \(p = c\ln n / n, c > 1\) as well as \(O(n^{3/2}(\ln n)^{1/2})\) for G(n, p) random graphs with \(p = c\sqrt{\ln n / n}, c > \sqrt{2}\).