A randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions is given, which follows from a simple stability principle for partially dynamic graphs.
Abstract
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.
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.
A. Bukov, Shay Solomon· Embedded Systems and Applica...· 0 citations
For an explicitly represented finite empirical model, deciding whether the contextual fraction is strictly below one is NP-complete, while the standard exact linear program has one column for every global assignment. We identify a permutation-transport class in which this global problem collapses to a fixed-point calculation. Let a connected permutation gain graph act on a finite state set $O$, let $H \leq{ \rm Sym}(O)$ be its holonomy subgroup, let $F = {\rm Fix}(H)$, and let $p$ be an $H$-invariant root distribution. For the induced empirical model, \[ {\rm NCF}(e)=p(F),\qquad {\rm CF}(e)=1-p(F). \] Consequently, compatibility, $F$, and ${\rm CF}(e)$ are computable in $O(|O|(|V|+|E|))$ arithmetic and table operations. For every finite simple $2$-edge-connected graph, any deterministic exact algorithm in the explicit permutation-table query model requires at least $(|O|-1)|E|$ probes in the worst case, making the dependence on the input tables optimal up to constant factors. With a fixed spanning tree, chord insertions and deletions require $O(|O|)$ worst-case time, or time proportional to the moved-set representation, while compatibility and contextual-fraction queries take $O(1)$ time. Finally, for common-marginal realizable binary constraint languages, the support threshold ${\rm CF}<1$ is polynomial-time equivalent to the associated finite-domain constraint-satisfaction problem and therefore inherits the Bulatov--Zhuk dichotomy. The results identify a query-optimal and dynamically maintainable tractability island inside the general contextual-fraction problem.
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
This work proposes an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges and is based on the novel concept of $\ell_1$-regularized resistance.
This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds. We consider a graph $G = (V, E, \vec{w})$ where the vertex set $V$ and edges $E$ are public and the weights $\mathbf{w}:E\rightarrow \mathbb{R}$ must be kept differentially private under an $\ell_1$ neighboring relation. For the problems of releasing a minimum-weight spanning tree and a minimum-weight perfect matching, we show new, tight error bounds of $\Omega(n\cdot\log(m/n)/\epsilon)$ on worst-case graphs with $n$ vertices and $m>2n$ edges. The upper bounds are known pure DP algorithms while the new lower bound holds even under approximate $(\varepsilon,\delta)$-DP as long as $\delta \leq (n/m)^{\Omega(1)}$. Our lower bounds improve the $\Omega(n/\epsilon)$ lower bounds of Sealfon (PODS~'16). The fact that approximate DP does not reduce error for MST under the $\ell_1$ neighboring relation contrasts with the recent upper bound of Pagh et al. (PODS~'25) which shows that approximate DP allows much better error under the $\ell_\infty$ neighboring relation. Going beyond worst-case graphs, we give lower bounds for large families of sparse graphs with expansion properties. We show a lower bound of $\Omega(n / \epsilon)$ for the minimum spanning tree for any graph where the minimum cut is at least $\Omega(\log(n))$. Finally, we consider the problem of private hierarchical clustering under Dasgupta's cost function (STOC~'16) and show the first approximate DP lower bound parameterized by the minimum weight of a balanced cut. This extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.
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.· arXiv.org· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
