This work shows that one can maintain an O(\alpha)-approximate MDS with update time for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence, which replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs.
Abstract
In the dynamic {\em minimum dominating set (MDS)} problem, the goal is to efficiently maintain an approximate MDS in an $n$-vertex graph with vertex costs in $[1/C,1]$ undergoing edge insertions and deletions. In STACS'19 [HIPS19] it was shown that an $O(\log n)$-approximate MDS can be maintained in {\em unweighted graphs} with $O(\Delta \cdot \log n)$ update time, where $\Delta$ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [SU23] this was extended to weighted graphs and improves the approximation guarantee to $(1+\epsilon)\ln \Delta$. Is it possible to achieve $\mathrm{poly}(\log n)$ update time without any dependence on $\Delta$, for any nontrivial graph family? This basic question has remained open even in {\bf forests} and even for {\bf unweighted instances}. The {\em arboricity} $\alpha=\alpha(G)$ of a graph $G$ is the minimum number of edge-disjoint forests whose union is $G$, and is a standard measure of sparsity. While $\alpha$ is bounded by $\Delta$ in any graph, various real-world graph families exhibit a significant gap between $\alpha$ and $\Delta$. In this work, we show that one can maintain an $O(\alpha)$-approximate MDS with update time $O(\alpha \cdot \log (Cn))$, for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence. This replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, our algorithm gives an $O(1)$-approximation with $O(\log (Cn))$ update time. To achieve this result, our algorithm departs from prior {\em greedy-based} approaches, relying instead on the {\em primal-dual framework} and new structural insights specific to bounded arboricity graphs.
In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $\lambda_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\tilde{O}(n^{12/13})$, for all values of $\lambda_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $\lambda_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\tilde{O}(n^{3/2})$ worst-case update and query time.
Yotam Kenneth-Mordoch, Robert Krauthgamer· 0 citations
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm\epsilon)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_{\epsilon}(n^2)$ and worst-case query time $\widetilde{O}_{\epsilon}(1)$. Thus, for dense graphs where $m = \Omega(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/\epsilon)$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
Let $\mathscr{C}$ be a class of graphs of bounded expansion and $r,k\in \mathbb{N}$ be fixed. We give a dynamic data structure that for a given dynamic graph $G$, updated by edge insertions and deletions subject to the promise that $G\in \mathscr{C}$ at all times, maintains the answer to the following two queries: (a) Does $G$ contain a distance-$r$ dominating set of size $k$? (b) Does $G$ contain a distance-$r$ independent set of size $k$? The data structure is randomized with error probability bounded by $\varepsilon$, for a parameter $\varepsilon>0$ fixed upon the initialization. The amortized update time is $\log^c n\cdot \log \frac{1}{\varepsilon}$, where $n$ is the vertex count of $G$ and $c$ is a constant that depends only on $r$, $k$, and $\mathscr{C}$. In the case of the first query, the data structure can also output a distance-$r$ dominating set of size $k$, if existent. We also prove that when $r=1$, our data structure for the dominating set query can be implemented even if we only assume that the maintained graph $G$ has degeneracy bounded by a constant $d$, yielding a simpler data structure with an improved amortized update time of $2^{k^{{\cal O}(d)}}\cdot \log^3 n\cdot \log \frac{1}{\varepsilon}$. Finally, we prove that in graphs of degeneracy at most $d$, one can maintain an ${\cal O}(d^2)$-approximation of the minimum size of a (distance-$1$) dominating set with amortized expected update time $d^{{\cal O}(1)}\cdot \log n$.
B. Bosek, Wojciech Nadara, Michał Pilipczuk et al.· 0 citations
A suite of fast randomized distributed algorithms representing varying points on this tradeoff are presented, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique models.
We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is to maintain an orientation with small {\em maximum outdegree} (hereafter, outdegree) and small worst-case update time. The outdegree of any orientation is at least $\alpha-1$, where $\alpha$ is the graph's \emph{arboricity}, i.e., the minimum number of forests into which its edge set can be partitioned. When $\alpha = O(1)$, it is long known that both the outdegree and the worst-case update time can be bounded by $O(\log n)$. Despite numerous follow-ups, no $o(\log^3 n)$ worst-case update time is known for maintaining constant outdegree, even for very basic graph families---with a notable exception, \emph{forests}. For forests, a \emph{simple folklore} algorithm maintains outdegree 2 via \emph{random walks}: When an insertion creates a vertex of outdegree 3, the algorithm repeatedly chooses a uniformly random outgoing edge until reaching a vertex of outdegree at most 1, and then flips the resulting directed path. As the underlying graph is cycle-free, the path length is easily shown to be $O(\log n)$ in expectation, and also with high probability for polynomially long update sequences. We prove that this simple random walk paradigm extends to \emph{outerplanar graphs}. Our algorithm maintains constant outdegree with $O(\log n)$ worst-case update time, where the time bound holds in expectation, and also with high probability for polynomially long update sequences. We give a \emph{tight analysis}: outdegree 4 is achievable with $O(\log n)$-length paths, while outdegree 3 incurs $\mathtt{poly}(n)$-length paths. We also extend the argument to $K_{2,t}$-minor-free graphs, for any $t \ge 2$, with the outdegree bound depending only on $t$ and with the same update time guarantees. The locality of [...]
Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon· 0 citations