Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

1.1 Problem definition

• The problem asks for a small-factor approximation to maximum induced-edge density while supporting edge insertions and deletions in a one-pass dynamic stream.The desired algorithms use near-linear space and polylogarithmic update and query times, with preprocessing time ˜O(n) unless otherwise stated.Source: §1.1 · pp. 4–5

1.2 Our Results

• A randomized algorithm maintains a (4+ε)-approximation with high probability using ˜O(n) space and ˜O(1) amortized update and query time over polynomially many updates.The guarantee holds for an oblivious adversary and provides Opt(t)/(4+O(ε)) ≤ Output(t) ≤ Opt(t) throughout the processed stream.Source: §1.2 · p. 6
• The results include a (2+ε)-approximation with ˜O(n) query time, a deterministic (4+ε)-approximation using ˜O(m+n) space, and directed-graph and distributed-streaming extensions.The directed extension gives an (8+ε)-approximation, while the distributed algorithm gives a (2+ε)-approximation with ˜O(k+n) communication.Source: §1.2 · pp. 6–7

1.3 Previous work

• The work improves prior streaming results by supporting dynamic streams in one pass, whereas Bahmani, Kumar, and Vassilvitskii [6] required O(log_{1+ε} n) passes for insert-only streams.Its semi-streaming space matches the lower bound of [6, Lemma 7] up to a polylogarithmic factor, while prior time-efficient densest-subgraph support was not space-efficient.Source: §1.3 · p. 7

1.4 Overview of our techniques

• The paper combines streaming and dynamic techniques through an (α, d, L)-decomposition, an approximate repeated low-degree-removal process that yields a 2α(1+ε)^2 approximation when L=O(log_{1+ε} n).Dynamic levels move nodes only when necessary; choosing α ≥ 2+ε gives ˜O(1) amortized update time, analyzed with node- and edge-based potential functions.Source: §1.4 · p. 8

1.5 Roadmap

• The paper proceeds from preliminaries to semi-streaming, deterministic dynamic, combined main, directed, sublinear-time, and distributed-streaming algorithms.The combined main algorithm maintains a (4+ε)-approximation with high probability using ˜O(n) space and ˜O(1) update time.Source: §1.5 · p. 9

2 Notations and Preliminaries

• The densest subgraph problem maximizes ρ(S) = |E(S)|/|S| over node subsets, and a γ-approximate solution satisfies γ · ρ(S) ≥ maxS′⊆V ρ(S′).The notation also defines induced edges, neighbor sets, degrees, average degree, and ˜O(.) factors hiding poly(log n, 1/ǫ) terms.Source: §2 · pp. 9–10
• With high probability, the dynamic data structure uses ˜O(n) bits, ˜O(1) amortized update time, and O(1) query time for a (4 + ǫ)-approximation.The result yields a single-pass semi-streaming algorithm for dynamic streams with very fast update and query times.Source: §2 · p. 10

2.1 Three basic properties

• The basic properties show δ(S) = 2 · ρ(S), m/n ≤ d∗ < n, and every node in a maximum-density subgraph has induced degree at least d∗.These identities and bounds support later density and decomposition analyses.Source: §2.1 · p. 10

2.2 (α, d, L)-decomposition

• An (α, d, L)-decomposition retains nodes of degree above αd, removes nodes below d, and, over geometric d values, yields a 2α(1 + ǫ)^3 approximation with ˜Θ(1) decompositions and O(1) query time.For outputting an approximate subgraph rather than only its value, tracking all decomposition levels adds ˜Θ(1) update time.Source: §2.2 · pp. 11–12

2.3 Two results on ℓ0-sampling and uniform hashing

• Dynamic-stream ℓ0-sampling maintains a uniformly random edge sample with high probability in ˜O(1) space and update time, while w-wise independent hashing uses O(w poly(log w, log q, log n)) bits and O(1) evaluation time.These primitives support the paper’s streaming algorithms and later uniform-hashing construction.Source: §2.3 · p. 13

2.4 Concentration bounds

• The section records upper- and lower-tail Chernoff bounds and states that they remain valid for negatively associated random variables.These concentration results are used throughout the subsequent analysis.Source: §2.4 · p. 13

Guarantee

• (2+Θ(ε))-approximation to densest-subgraph value is achieved with high probability in one dynamic-stream pass using ˜O(n) space.The algorithm collects enough independent ℓ0-samples to construct decompositions across a discretized density range and invokes Corollary 2.7.Source: §3 · pp. 13, 15

Decomposition construction

• ˜O((n+m/d) poly log n) bits suffice to construct an (α,d,L)-decomposition from random edge samples with high probability.The method samples edges independently and repeatedly filters vertices whose sampled induced degree is below (1−ε)αc log n.Source: §3 · p. 14

Runtime

• ˜Θ(n) update time and ˜Θ(n) query time are required because every stream update touches all ℓ0-samplers and queries construct multiple decompositions.Thus, the algorithm’s space efficiency comes at the cost of linear-up-to-polylogarithmic processing time.Source: §3 · p. 15

4 A Dynamic Algorithm with Fast Update and Query Times

• The algorithm deterministically maintains a (4+O(ε))-approximation using ˜O(m+n) space, ˜O(1) amortized update time, and O(1) query time.It stores all graph edges and combines O(log n/ε) decompositions, obtaining the guarantee from 2α(1+ε)^2 = 4+O(ε).Source: §4 · pp. 15–16

4.1 Dynamically maintaining an (α, d, L)-decomposition

• An (α,d,L)-decomposition supports edge insertions and deletions deterministically in O(L/ε) amortized time and O(n+m) space.Over t updates, the total processing time is O(tL/ε), while linked lists and level counters maintain the decomposition.Source: §4.1 · p. 16

4.1.1 A high level overview of the potential function based analysis

• The potential analysis assigns node and edge potentials so insertions or deletions fund future level changes, requiring α = 2+Θ(ε) to cover cascading neighbor effects.Edge updates increase total potential by at most O(L/ε), while recovery computation decreases it sufficiently to imply O(L/ε) amortized update time.Source: §4.1.1 · pp. 17–18, §4.1 · p. 17

4.1.2 Analyzing the subroutine RECOVER().

• RECOVER() handles dirty nodes by moving them one level up or down, with each event costing O(1+D_y(Z_i)) and producing enough potential decrease to pay that cost.For demotions, α ≥ 2+3ε ensures the net potential drop is at least d ≥ D_y(Z_i)+1.Source: §4.1.2 · pp. 18–20

• The new algorithm maintains a (4+ε)-approximation of ρ∗(G) while processing edge insertions and deletions.It combines techniques from the earlier algorithms to capture their complementary advantages.Source: §5 · p. 20
• ˜O(1) update and query times improve on the prior (2+ε)-approximation algorithm’s ˜Θ(n) update and query costs.The earlier semi-streaming algorithm answered queries only at the end of the stream.Source: §5 · p. 20
• The algorithm uses ˜O(n) space, unlike the fast Section 4 algorithm, which requires ˜Θ(m + n) bits to store all edges.This preserves the low space complexity of the Section 3 approach while retaining fast operations.Source: §5 · p. 20
• Queries can be answered at any time during the stream, including between updates.This capability matches the fast Section 4 algorithm and contrasts with the Section 3 algorithm’s end-of-stream queries.Source: §5 · p. 20

5.1 An Overview of Our Result

• With high probability, the algorithm processes T updates using Õ(n) bits of space, Õ(1) amortized update time, and maintains a (4 + ε)-approximation with O(1) query time.For every t ∈ [1,T], Output(t) ≤ Opt(t) ≤ (4 + ε)·Opt(t), where T = Θ(n^λ) for constant λ.Source: §5.1 · p. 21
• The polynomial-update restriction enables a union bound ensuring that every intermediate sketch state gives a good approximation, rather than only the final stream state.The stronger all-time guarantee requires T = Θ(n^λ) for constant λ, unlike the semi-streaming algorithm, which typically queries only at the stream’s end.Source: §5.1 · p. 21

5.1.1 Main technical challenges

• The main technical design combines Õ(n) random edge samples for space efficiency with (α, d, L)-decompositions for Õ(1) update and query times.This natural combination requires overcoming several technical challenges before it yields the theorem.Source: §5.1.1 · pp. 21–22
• The algorithm accelerates dynamic sampling, supports decomposition thresholds d that change as edges are inserted or deleted, and extends potential-function analysis to independently sampled edges across levels.Maintaining samples directly would require Õ(n) update time; changing thresholds arise because d depends on the current edge count, while level-specific independence is needed for the sampling analysis.Source: §5.1.1 · p. 22
• The remainder of the section handles sparse and dense time-steps separately: it maintains the full edge set when m(t) = Õ(n), samples when m(t) = Õmega(n), and applies corresponding approximation algorithms.Time-steps are classified by edge count so Theorems 5.2 and 5.3 provide the appropriate maintained edge representation, while Theorems 5.4 and 5.5 maintain the (4 + ε)-approximation.Source: §5.1.1 · pp. 22–23

5.2 Maintaining the randomly sampled edges in ˜O(1) update time

• Hash-partitioning edges into buckets lets one ℓ0-sampler handle each update, maintaining ˜Θ(n) random samples in ˜O(n) space and ˜O(1) update time.An insertion or deletion affects exactly one bucket and sampler, yielding the claimed update bound.Source: §5.2 · p. 23, §5.2.2 · p. 25

5.2.1 Proof of Theorem 5.2

• Theorem 5.2 maintains a random edge subset using ˜O(n) space and ˜O(1) worst-case update time, recovering all current edges with high probability whenever m(t) ≤8αc2n log2 n.The construction uses hash buckets and multiple independent Streaming-Samplers, whose updates total ˜O(1) time and whose failure probabilities are union-bounded over edges and time-steps.Source: §5.2 · pp. 23–24, §5.2.1 · pp. 24–25

5.2.2 Proof of Theorem 5.3

• Theorem 5.3 maintains dense-stream samples with ˜O(n) space and ˜O(1) worst-case update time, while providing near-uniform inclusion, negative association, and at most two sample changes per update.These guarantees apply when m(t) ≥4αc2n log2 n, for s ≤2αcn log n.Source: §5.2 · p. 24

• P3 partitions the stream into maximal contiguous sparse and dense intervals, distinguishing time-steps online after each edge update.Sparse steps have at most 8αc2n log2 n edges, while dense steps have at least 4αc2n log2 n edges; intervals span at least 4αc2n log2 n steps unless ending at T.Source: §5.3 · p. 26
• P3 requires only a counter, using ˜Θ(1) space and Θ(1) update time to classify time-steps by the current graph edge count.The procedure also enforces the four stated sparse/dense interval properties.Source: §5.3 · p. 26
• At sparse time-steps, P4 uses edges maintained by P1 to maintain Output(t), a (4 + ǫ)-approximation of Opt(t).P1 implements the algorithm of Theorem 5.2.Source: §5.3 · pp. 26–27
• At dense time-steps, P5 uses subsets maintained by independent copies in P2 to maintain Output(t), a (4 + ǫ)-approximation of Opt(t).P2 implements ˜Θ(1) independent copies of the algorithm in Theorem 5.3.Source: §5.3 · pp. 26–27
• Theorem 5.1 follows by combining the guarantees of Theorems 5.4 and 5.5.Source: §5.3 · p. 27

5.4 Algorithm for sparse intervals

• With high probability, the algorithm maintains Output(t) at every sparse time-step using ˜O(n) space and processes T updates in ˜O(T) total time.Thus, the amortized update time is ˜O(1).Source: §5.4 · p. 27
• The method combines the Section 5.3 subroutine with Dynamic-algo, maintaining F(t) = E(t) at sparse time-steps with high probability.The first subroutine has worst-case ˜O(1) update time and ˜O(n) space, while Dynamic-algo runs on (V, F(t)).Source: §5.4 · pp. 27–28
• Dynamic-algo uses ˜O(n) space during sparse intervals because the input graph has ˜O(n) edges at every sparse time-step.This supports maintaining Output(t) throughout each sparse interval.Source: §5.4 · p. 28
• The amortized analysis bounds each sparse interval’s computation by ˜O(t1 − t0), using interval lengths of Ω(n) except possibly for an interval ending at T.For a shorter terminal interval, the computation is ˜O(n); summing disjoint intervals and using T = Θ(nλ), λ ≥ 1, yields amortized ˜O(1) update time.Source: §5.4 · p. 28

5.5 Algorithm for dense intervals

• ˜O(n) space and ˜O(1) amortized update time yield a high-probability (4 + ε)-approximation during dense time-intervals.The algorithm processes T updates in ˜O(T) time and maintains Output(t) at every dense time-step.Source: §5.5 · p. 28

5.5.1 Basic building block for proving Theorem 5.5

• For each discretized parameter k, the algorithm maintains an (α, d(t)_k, L)-decomposition using ˜O(n) bits and ˜O(1) amortized update time.The discretization uses a time-independent K = ˜O(1), and the decomposition implies a 2α(1 + ε)^3 = (4 + Θ(ε))-approximation.Source: §5.5.1 · p. 29

5.5.2 Overview of our algorithm for Theorem 5.6

• The construction combines L − 1 independent sampled-edge streams with iterative degree-based node-set construction to maintain the decomposition efficiently.Each sampled stream has ˜O(1) worst-case update time and ˜O(n) space; Dynamic-stream is invoked only during dense intervals.Source: §5.5.2 · pp. 29–30

5.5.3 The subroutine Dynamic-stream for a dense time-interval [t0, t1]

• Throughout a dense interval, Dynamic-stream updates sampled edges after each graph change and, with high probability, preserves a valid (α, d(t)_k, L)-decomposition.RECOVER-SAMPLE uses the old decomposition and new samples; Lemma 5.7 establishes the needed independence structure for the correctness proof.Source: §5.5.3 · pp. 30–31
• With high probability, event E(t) holds for every time-step t ∈ [t0, t1], regardless of earlier events.This follows by union bounds over nodes, indices, and all time-steps in the interval.Source: §5.5.3 · pp. 32–33
• The lemma follows by combining the per-time-step guarantees through a union bound over all t ∈ [t0, t1].The argument establishes simultaneous correctness rather than correctness at only an individual time-step.Source: §5.5.3 · p. 33
• At every t ∈ [t0, t1], the tuple (Z(t)1, …, Z(t)L) maintained by Dynamic-stream gives an (α, d(t)k, L)-decomposition of G(t).Thus, the subroutine’s decomposition guarantee holds throughout the entire interval with high probability.Source: §5.5.3 · p. 33

5.5.4 Data structures for implementing the procedure in Figure 4

• For each node v and index i, doubly linked Friends_i[v, j] lists represent sampled neighbors across the relevant level sets.When i is at most ℓ(v), lists are empty above i, use N_v(Z_j, S_i) at j = i, and N_v(V_j, S_i) below i; when i > ℓ(v), the analogous boundary is ℓ(v).Source: §5.5.4 · p. 33
• Degree_i[v] counts the nodes in Friends_i[v, i], while Dirty-Nodes[i] tracks nodes requiring level-related maintenance.If ℓ(v) < i, Degree_i[v] equals zero.Source: §5.5.4 · p. 33
• For any fixed i and time-step, an input edge appears at most once among the samples at level i, so across all samples it occurs at most L −1 times.This bounds the total sampled-edge occurrences used by the data structures.Source: §5.5.4 · p. 33

5.5.5 Implementing the procedure in Figure 4 during a dense time-interval [t0, t1]

• Each input update causes at most O(L) = ˜O(1) insertions or deletions across the sampled sets S_1, . . . , S_L−1.The relevant Friends and Dirty-Nodes lists can therefore be updated in ˜O(1) time.Source: §5.5.5 · pp. 33–34

5.5.4 Data structures for implementing the procedure in Figure 4

• An edge in S_i can occur only in Friends_i[x, j] lists for its two endpoints x and for j from 1 through L −1.This locality enables the stated constant-polylogarithmic update of the maintained lists after sampled-edge changes.Source: §5.5.5 · p. 33, §5.5.4 · p. 33

5.5.5 Implementing the procedure in Figure 4 during a dense time-interval [t0, t1]

• The ith loop iteration constructs Z_{i+1} by scanning Dirty-Nodes[i] and applying the level changes prescribed by Figure 4.Nodes at level i with sufficiently high sampled degree move to i + 1, while higher-level nodes with sufficiently low degree move down to i.Source: §5.5.5 · p. 34
• ˜O(n) space suffices to implement the procedure in Figure 4 during a dense time-interval.The space bound follows from maintaining at most s sampled edges for each of L −1 levels, giving (L −1) · s = ˜O(n).Source: §5.5.5 · p. 34
• Claim 5.10 bounds the relevant data-structure updates during the ith main-loop iteration: for u whose level increases from i to i + 1 or v whose level decreases to i.The proof updates only lists Friends_i′[x, j] with i′ > i and x ∈ {y} ∪ N_y(Z(t)), where y is u or v respectively.Source: §5.5.5 · p. 34

5.5.6 The amortized update time of Dynamic-Stream during a dense time-interval

• Event F ensures that node degrees across the distinct randomly sampled edge subsets are approximately equal with high probability.This allows the potential-function analysis from Section 4 to extend to the current decomposition.Source: §5.5.6 · p. 35
• Lemma 5.12 proves that event F holds with high probability, supplying the probabilistic condition required for the amortized-time analysis.The event is defined across level pairs i < i′ and time-steps t ∈[t0, t1].Source: §5.5.6 · p. 35
• Conditioned on event F, each constant computation step in Figure 4 decreases potential B by Ω(1), while an input edge update changes B by ˜O(1).Thus, the potential pays for the procedure’s computation while maintaining the decomposition.Source: §5.5.6 · pp. 35–36
• With high probability, Dynamic-Stream spends ˜O(n+(t1 −t0)) total time during [t0, t1], yielding ˜O(1) amortized update time.This extends to ˜O(T) total time over the first T stream updates when the dense interval lasts ˜Ω(n) steps or ends at T.Source: §5.5.6 · p. 36

5.5.7 Proof of Lemma 5.12

• For fixed level pairs and time t, sampled-edge degrees are concentrated using independence from conditioned node sets, inclusion probabilities (1±ǫ)·(s/m(t)), negative association, and Chernoff bounds.Union bounds are then applied over nodes in the relevant sets.Source: §5.5.7 · pp. 36–37
• With high probability, no node in W(t)_i belongs to A(t)_i, while nodes in Z(t)_i satisfy the required high-degree bounds relative to sampled sets S(t)_i and S(t)_i′.Analogous bounds are established for B(t)_i before combining the cases.Source: §5.5.7 · p. 37
• A final union bound over all level pairs and time-steps establishes event F with high probability.This completes the proof of Lemma 5.12.Source: §5.5.7 · p. 37

Proof of Lemma 5.13

• Parts (a) and (b) hold independently of event F, while part (c) requires conditioning on F.This distinction is stated explicitly before the three parts are proved.Source: §5.5.8 · p. 38
• For any time-step t, part (a) follows because node potentials Φ, edge potentials Ψ_i, and each random set S(t)_i are bounded by ˜O(1), ˜O(1), and ˜O(n), respectively.The proof derives these three bounds as the facts needed for part (a).Source: §5.5.8 · p. 38
• For part (b), one graph edge update causes at most two updates in each S(t)_i, and each such update changes the overall potential B by at most ˜O(1).The change is bounded by O(3L + 2L/ε) = ˜O(1), ignoring the procedure call in Figure 4.Source: §5.5.8 · p. 38
• For a promotion from level i to level i + 1, the decrease in B is sufficient to pay for the computation performed, as implied by Eqs. (38), (39), and (40).Source: §5.5.8 · pp. 38–39

6 Extension to Directed Graphs

• Directed density is defined for node pairs as ρ(X, Y) = |E(X, Y)|/(|X||Y|), maximizing over possibly overlapping subsets X and Y.The dynamic stream starts empty and consists of directed-edge insertions and deletions while the node set remains fixed.Source: §6 · p. 40
• The directed-graph algorithm deterministically maintains an (8 + ε)-approximation using ˜O(m + n) space, ˜O(1) amortized update time, and O(1) query time.Here, m and n denote the numbers of edges and nodes in the input graph, respectively.Source: §6 · p. 40

6.1 Notations and Preliminaries

• The derived graph replaces every original node v with source and target copies s_v and t_v, maps (u, v) to (s_u, t_v), and preserves pair densities.It can be maintained with O(m + n) space and O(1) update time, while the densest directed subgraph corresponds to the densest pair in the derived graph.Source: §6.1 · pp. 40–41

6.2 (α, d_S′, d_T′, L)-Decomposition and Its Properties

• The directed (α, dS′, dT′, L)-decomposition iteratively filters source and target nodes by degree thresholds, with either set shrinking by factor (1 + ε) per level until both are empty.For L = 2 · (2 + ⌈log(1+ε) n⌉), both sets are empty after L levels; the topmost level is empty if dS′dT′ > 4(1 + ε)λS′λT′ and nonempty if dS′ < λS′/α and dT′ < λT′/α.Source: §6.2 · pp. 42–43

6.3 The Algorithm for Maintaining an (α, d_S′, d_T′, L)-Decomposition

• For polynomially bounded α ≥ 2 + 3ε, the maintenance algorithm deterministically processes t updates in O(tL/ε) total time and uses O(n + m) space.It maintains separate level-indexed neighbor lists and marks nodes dirty when their source- or target-side degree violates the decomposition thresholds.Source: §6.3 · pp. 44–45

6.3 The Algorithm for Maintaining an (α, dS′, dT′, L)-Decomposition

• The recovery procedure processes directed edge updates by updating endpoint Friends lists, marking affected nodes dirty, and restoring cleanliness through RECOVER-DIRECTED().The procedure’s potential analysis shows total recovery time O(tL/ε) over t updates, giving amortized update time O(L/ε).Source: §6.3 · pp. 45, 47
• For each level change, recovery work is charged to a matching potential decrease of Ω(1 + D_s(T_i)) or Ω(1 + D_t(S_i)) when α ≥ 2 + 3ε.An edge update increases the potential by at most 3L/ε, while the potential remains nonnegative.Source: §6.3 · pp. 46–47

6.4 Wrapping Up: Proof of Theorem 6.2

• 8 · (1 + O(ε))-approximation to ρ(G) follows by maintaining O(K^2) decompositions, with ˜O(m + n) space and ˜O(1) total amortized update time.Each decomposition requires O(m + n) space and O(L/ε) amortized update time; the final approximation is 4α · (1 + ε)^(3/2) with α = 2 + 3ε.Source: §6.4 · p. 47

Oracle Model

• The oracle is the incident-list model, supporting degree queries and queries for the ith neighbor of a node.This model provides efficient access to graph input without requiring the algorithm to read the entire input.Source: §7 · p. 47

Upper Bound

• (2+ε)-approximation requires ˜O(n) oracle queries, time, and space in the incidence-list model.The algorithm samples ˜O(n) edges via neighbor queries and processes them using decompositions.Source: §7 · pp. 47–48

Lower Bound

• A sublinear-time algorithm making q oracle queries can be simulated with ˜O(q) communication bits for the lower-bound problem P1.Player p1 answers degree and neighbor queries by communicating with the player associated with the queried node.Source: §7 · p. 48
• Any (λ−ε)-approximation algorithm for λ≥3/2 requires ˜Ω(n/λ^2) oracle queries.The lower bound follows by reducing a communication-complexity problem whose instances distinguish clique density from star density.Source: §7 · p. 48

Distributed streaming

• The coordinator samples ˜O(n) edges without replacement as a sketch, enabling the approximate densest-subgraph computation while each site uses ˜O(1) space.The sampling algorithm of Cormode et al. uses ˜O(k + n) bits of communication and leaves the coordinator with ˜O(n) space.Source: §8 · p. 48
• (2 + ε)-approximation is computed using ˜O(k + n) bits of communication, with ˜O(n) coordinator space and ˜O(1) space per site.This guarantee applies to the distributed streaming setting with k sites receiving insertion-only edge streams.Source: §8 · p. 49

Approximation guarantees

• Can the (4 + ǫ) approximation be improved to (2 + ǫ), even with larger space, without assuming uniformly random deletions?This would match the approximation achievable when update time is not a concern; Epasto et al. nearly achieved it under a random-deletion assumption.Source: §9 · p. 49

Lower bounds

• Can hardness results be established for approximation algorithms, beyond the existing hardness result for maintaining the optimal solution [23]?Source: §9 · p. 49

Update-time guarantees

• Can similar algorithms achieve polylogarithmic worst-case update time rather than only amortized update time?Source: §9 · p. 49

Generalization

• Can space- and time-efficient fully dynamic algorithms be developed for other fundamental graph problems, such as maximum matching and single-source shortest paths?Source: §9 · p. 49