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.
It is proved that the problem of defining a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible, and that the problem is NP-hard, even in simple networks like complete graphs and trees.
Investigating the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover, presents randomized distributed algorithms that achieve nearly exponentially smaller energy complexity.
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). In this paper, we almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous results for a single failure [Bil\`o, Cohen, Friedrich, Schirneck, MFCS 2021; Bil\`o, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2021]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.
We give a new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein&Ravi [J. Algorithms'95] which are best possible unless P = NP, but have the advantage that they work in the online setting when the terminal pairs are revealed in random order. To obtain our results, we combine the LearnOrCover framework due to Gupta, Kehne, Levin [FOCS'21] with the Augmented Greedy algorithm of Berman&Coulston [STOC'97] for online edge-weighted Steiner Forest. Neither algorithm suffices on its own, but the analyses dovetail to imply our guarantee. Run offline, the algorithm reduces to a very simple randomized rounding scheme that (in spirit) reduces Node Weighted Steiner Forest to Edge Weighted Steiner Forest, and we hope this idea finds further applications.
This paper generalises the existing PTAS for complete graphs from a fixed to an arbitrary number of intervals and disprove an existing conjecture, which states that every instance of BIA admits a solution satisfying at least three quarters of all edges.