PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparsification Framework for Directed Densest Subgraph

Slobodan Mitrović, Theodore Pan

arXiv:2610.00846v1cs.DS

TL;DR

Directed densest-subgraph algorithms face high sampling costs and peeling that can require logarithmically many iterations. This paper combines refined sampling with one peeling step to sparsify the graph and recover approximate DDS solutions. Its algorithms achieve near-linear resources in sublinear time and a single-pass semi-streaming approximation.

  • Problem

    Uniform sampling can require superlinear sample size, while degree-based peeling can take Θ(log n) iterations to reach an approximate DDS.

    Source: §1 · p. 3, §1.3.1 · p. 8

  • Method

    Peel-Sample combines refined uniform sampling with one low-degree peeling step, using the size ratio of the DDS vertex sets to guide the approach.

    Source: §1.1 · p. 4, §1.3.2 · p. 8, §1.3.3 · p. 9

  • Results

    ~O(n) time, space, and queries yield a (1−12ε)-approximate DDS, while single-pass semi-streaming achieves (1−4ε) using ~O(n/ε³) memory.

    Source: §4.2 · p. 19, §6.2 · p. 22

  • Takeaways & Limitations

    The framework reduces the graph to ~O(n/ε²) edges while preserving a (1−ε)-approximate directed densest subgraph.

    Source: §1.1 · p. 4

    Single-pass semi-streaming still uses an extra factor of ε in memory compared with undirected DS.

    Source: §1.4 · p. 9

Abstract

from arXiv · show

We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrovi\'c and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).

1 Introduction

Directed densest subgraph (DDS) maximizes the density of arcs from one vertex set to another. Existing approaches face limits in sampling size and peeling iterations, leaving open whether a directed graph can be sparsified to ~O(n) edges while preserving a (1−ε)-approximate DDS.

1 Introduction

  • DDS maximizes |E(S,T)|/(|S|·|T|), where E(S,T) contains arcs from S to T.The measure captures local structure in web graphs and has applications in fraud detection, community and data mining, and computational biology.Source: §1 · p. 3
  • Peeling can produce a 0.5-approximate DDS, but degree-based peeling may require Θ(log n) iterations.The illustrated construction takes Θ(log n) iterations because only the bottom layer can be removed while preserving the densest subgraph.Source: §1 · p. 3, Figure 1 · p. 4
  • Bahmani, Kumar, and Vassilvitskii [BKV12] reduce peeling to O(log n) iterations and obtain a (0.5−ε)-approximation, including in semi-streaming with O(log n) passes.Their method removes vertices below the average degree times (1+ε).Source: §1 · p. 3
  • Uniform sampling retains a (1−ε)-approximate DDS with ~O(n√n/ε²) edges, and worst-case constructions require Ω(n^(1.5−β)) sampled edges for constant approximation.This is tight to within an n^o(1) factor.Source: §1 · p. 3, Figure 2 · p. 4
  • Unlike undirected DS, where ~O(n/ε²) sampled edges suffice, whether directed DS admits ~O(n)-size sparsification preserving a (1−ε)-approximation remained open.The directed uniform-sampling bound creates a substantial gap with the known undirected result.Source: §1 · p. 3

1.1 Our results

Peel-Sample combines refined uniform sampling with one peeling step to preserve a near-optimal directed densest subgraph in a sparse graph. Its instantiations give approximation algorithms in semi-streaming, MPC, and sublinear-time settings.

1.1 Our results

  • A refined uniform sample plus one peeling step yields a graph with ~O(n/ε²) edges that preserves a (1−ε)-approximate DDS.The framework is called Peel-Sample.Source: §1.1 · p. 4

Applications

  • Two-pass semi-streaming achieves a (1−ε)-approximate DDS with ~O(n/ε²) memory.The algorithm succeeds with probability at least 1−1/poly(n).Source: Applications · p. 5
  • A single-pass semi-streaming algorithm achieves a (1−ε)-approximate DDS using ~O(n/ε³) memory.This matches the state of the art for undirected DS and improves on the previous single-pass O(log n)-approximation [MPQR25].Source: Applications · p. 5
  • O(1) MPC rounds yield a (1−ε)-approximate DDS in the near-linear-memory regime, improving on the O(√log n)-round (0.5−ε) result [MP24].The algorithm uses ~O(n) memory per machine and ~O(m) total memory.Source: Applications · p. 5
  • ~O(n) time, space, and incident-list queries suffice for a sublinear-time (1−ε)-approximate DDS algorithm.This improves all three complexities by a factor of √n over the previous ~O(n√n) algorithm.Source: Applications · p. 5

1.2 Related work

Related work develops LP, peeling, and sampling approaches for directed and undirected densest subgraph, then adapts them to constrained computation models and related graph problems.

LP-based works

  • Charikar introduced LP formulations for DS, and multiplicative weights approximates the dual LP to obtain a (1−ε)-approximation in near-linear time.LP and sparsification techniques also support MPC algorithms for undirected DS.Source: §1.2 · p. 5
  • For undirected DS, obtains a (1 − ϵ)-approximation with high probability in ˜O(√log n) sublinear MPC rounds, using uniform graph sparsification to reduce density to O(log n); this is difficult for directed DS.Source: §1.2 · p. 5

Related approaches

  • Dynamic DS work [SW20] maintains approximate directed or undirected solutions with polylogarithmic update and query time, while [BHNT15] could not extend its sublinear-memory guarantee to directed DS.The directed limitation was attributed to sampling issues.Source: §1.2 · pp. 6–7

Peeling-based works

  • Peeling methods for DDS use a guessed size ratio z, while later work removes that parameter and obtains a linear-time 2-approximation.Fixed-threshold peeling [MPQR25] supports distributed adaptations, including sublinear MPC and single-pass semi-streaming algorithms.Source: §1.2 · pp. 6–7

Related problems

  • DS-inspired peeling and LP methods also support edge orientation and k-core decomposition algorithms across distributed and streaming models.Examples include (1+ε)-orientation in CONGEST [SV20] and approximate core-labeling in semi-streaming [ELM18].Source: §1.2 · pp. 5, 7

1.3 An outline of our approach

The approach combines ratio-aware sampling with one low-degree peeling step to sparsify directed densest-subgraph instances, then adapts the framework to a single streaming pass. The first peel either substantially reduces a vertex set or leaves a dense subgraph, while the streaming version removes edges as they arrive.

1.3.1 Refined sampling

  • O(n log n · max(z, 1/z)/ϵ^2) sampled edges suffice for a (1 −ϵ)-approximate DDS, improving on uniform sampling when max(z, 1/z) = o(√n).Here z is the ratio of the optimal DDS vertex-set sizes; algorithms recovering a DDS from the sample should account for the chosen z.Source: §1.3.1 · p. 8

1.3.2 Adding low-degree peeling

  • The first peeling step either reduces one vertex set by a factor proportional to max(z2, 1/z2), or leaves a subgraph that is already a good DDS approximation.If the remaining subgraph is not dense, the vertex-set reduction implies a corresponding large decrease in edge count; combining peeling with sampling cancels the ratio factor, yielding a ˜O(n)-edge sparsifier that preserves a (1−ϵ)-approximate DDS.Source: §1.3.2 · p. 8

1.3.3 Single-pass semi-streaming

  • The streaming adaptation addresses the difficulty that a vertex’s degree may rise above the peeling threshold late in the stream, after oversampling has already occurred.The cited construction places complete-graph edges before star edges, forcing a constant sampling probability to preserve the star and potentially requiring Ω(n^1.5−β) sampled edges.Source: §1.3.3 · pp. 8–9
  • Figure 3 contrasts ordinary peeling’s size-reduction-or-density outcome with streaming’s removal of τ −1 edges from each surviving vertex.The first peeling iteration starts with |S0|/|T0| = 1, and panel (a) assumes z2 < 1.Source: Figure 3 · p. 9
  • In one streaming pass, the algorithm removes each vertex’s first τ −1 incident edges, immediately discarding edges of vertices that should be peeled.It also removes τ −1 edges from vertices that remain, but suitable D, z, and τ parameters keep the DDS density from changing too much.Source: §1.3.3 · p. 9

1.4 Open problems

The single-pass semi-streaming algorithm uses slightly more memory than the cited undirected DS algorithm.

1.4 Open problems

  • ˜O(n/ϵ^3) memory is used for single-pass semi-streaming DDS, versus ˜O(n/ϵ^2) for undirected DS.The paper identifies a remaining factor-ϵ gap in memory usage.Source: §1.4 · p. 9

2 Preliminaries

The preliminaries represent directed graphs as bipartite graphs and define the DDS and computation settings used in the paper. They also state degree bounds for an optimal DDS and the Chernoff bounds used in sampling arguments.

2.1 Definitions

  • Each directed arc u→v is represented by an edge from u in one vertex copy to v in the other, and all directed graphs use this bipartite representation.The graph notation defines n as the total vertices across the two sides and dG(v) as a vertex’s degree.Source: §2.1 · p. 10
  • A DDS is a pair (S*, T*) maximizing the density ρG(S, T), defined as the edges between S and T divided by |S| · |T|.The passages define the edge set between A and B as EG(A, B).Source: §2.1 · p. 10
  • In near-linear-memory MPC, machines compute and exchange bounded messages in synchronous rounds, with the objective of minimizing rounds; the paper focuses on S = n poly log n memory per machine.The stated regimes also include sub-linear S = n^δ and super-linear S = n^(1+δ) memory.Source: §2.1 · p. 10
  • Semi-streaming processes edges one at a time with O(n poly log n) internal memory, while sublinear-time algorithms use an incident-list oracle and aim for sublinear queries, time, and memory.The oracle supports degree queries and indexed in- or out-neighbor queries.Source: §2.1 · p. 10

2.2 Folklore lemmas

  • For an optimal DDS of density D and size ratio z = |S*|/|T*|, every vertex on S* has degree at least D/(2z), and every vertex on T* has degree at least Dz/2.The preliminaries also state Chernoff bounds for sums of independent [0,1]-valued random variables, including a relative-deviation bound for δ in [0,1] and an upper-tail bound for δ ≥ 1.Source: §2.2 · pp. 10–11

3 Sparsification framework for directed DS

This section presents a sparsification framework for directed densest subgraph (DDS) that combines low-degree peeling and edge sampling, then shows how a fixed-threshold peeling algorithm recovers an approximate DDS from the resulting sparse graph.

3.1 Refined uniform sampling

  • O(αm log n · max(z, 1/z)/(ϵ2D)) edges suffice for refined uniform sampling with probability at least 1−n−6.For D = ρG(S∗, T ∗) and z = |S∗|/|T ∗|, the sample contains a subgraph satisfying edge-threshold with density at least (1−ϵ)D/α in G, with probability at least 1−n−5.Source: §3.1 · pp. 12–13

3.2 Combining low-degree peeling with sampling

  • O(αn log n/(cϵ2)) edges suffice after peeling, unless Peel-Sample instead returns a subgraph of density at least D; this holds with probability at least 1−n−6.Here α ≥ 1, c ∈ (0, 1/2], and D ≥ m/n.Source: §3.2 · p. 14
  • O(n log n/ϵ2) edges suffice for Peel-Sample to preserve a (1−ϵ)-approximate DDS, with probability at least 1−n−5.The guarantee uses D = ρG(S∗, T ∗), z = |S∗|/|T ∗|, α ≥ 1/(1−ϵ), and c ∈ (0, 1/2]; peeling removes vertices from one side according to z.Source: §3.2 · pp. 13–14

3.3 Peeling-based algorithms satisfy edge-threshold

  • Peeling-based algorithms from [Cha00, BKV12, MPQR25] satisfy edge-threshold and can extract approximate DDS solutions from Peel-Sample’s sparsified graph.Edge-threshold is a condition on an algorithm’s returned subgraph that enables recovery of an approximate DDS from the sample.Source: §3.1 · p. 11, §3.3 · p. 14

3.3.1 Greedy peeling algorithm

  • The greedy peeling variants from [Cha00] and [BKV12] satisfy edge-threshold and compute a (0.5−ϵ)-approximate DDS from Peel-Sample’s graph with high probability.The [Cha00] variant satisfies the condition with α = 2; [BKV12] satisfies it with α = 2/(1−ϵ).Source: §3.3.1 · p. 15

3.3.2 Fixed threshold peeling algorithm

  • The fixed-threshold peeling algorithm from [MPQR25] returns a nonempty subgraph satisfying edge-threshold when it terminates.It peels vertices below degree thresholds D/(2z) on S and Dz/2 on T.Source: §3.3.2 · pp. 15–16
  • Algorithm 4 never returns an empty subgraph because vertices of an optimal DDS survive peeling.The optimal subgraph’s vertices meet the peeling degree thresholds, so they are not removed.Source: §3.3.2 · p. 16
  • Algorithm 4 computes a (0.5 − ϵ)-approximate DDS whp from the sparsified graph returned by Peel-Sample [MPQR25].Source: §3.3.2 · p. 16
  • The peeling algorithm from [MPQR25] satisfies edge-threshold with α = 2/(1 − ϵ).Source: §3.3.2 · p. 16

4 Semi-streaming algorithms

Peel-Sample combines low-degree peeling and edge sampling to preserve an approximate directed densest subgraph in a sparse graph. The section develops a two-pass warm-up and then a single-pass semi-streaming algorithm that achieves the approximation guarantee with polylogarithmic memory overhead.

4 Semi-streaming algorithms

  • Direct simulation of Peel-Sample takes two passes, so the single-pass method requires modifying peeling to run concurrently with sampling.The difficulty is that peeling decisions may not be known until most of the stream has been read, risking a sample larger than ω(n poly log n) edges.Source: §4 · p. 16, §4.2 · p. 17

4.1 Warm-up: Two-pass algorithm

  • For ϵ ∈(0, 1/4), the two-pass semi-streaming algorithm uses ˜O(n/ϵ2) memory and computes a (1 −4ϵ)-approximate DDS with probability at least 1 −n−4.Its first pass simulates low-degree peeling and its second pass simulates sampling.Source: §4.1 · p. 16
  • The two-pass algorithm runs instances over discretized D and z values in parallel, then selects the nonempty output with the largest D.The same parameter search and selection strategy is used by the single-pass algorithm.Source: §4.1 · p. 17, §4.2 · p. 19

4.2 Single-pass algorithm

  • The single-pass algorithm removes the first kT −1 or kS −1 edges per vertex while sampling, allowing peeling and sampling to be simulated together in one pass.Because this can remove edges from the densest subgraph, the thresholds are set to kS = ϵD/z and kT = ϵDz to limit the approximation loss.Source: §4.2 · p. 18
  • For ϵ ∈(0, 1/4), the single-pass semi-streaming algorithm computes a (1 −4ϵ)-approximate DDS with probability at least 1 −n−4.It uses ˜O(n/ϵ3) memory; the paper states this closes the approximation gap with undirected DS in semi-streaming.Source: §4.2 · p. 19

5 Near-linear MPC algorithm

The near-linear MPC algorithm simulates Peel-Sample by computing degrees, sampling the remaining edges, and processing the sample locally. It runs in O(1) rounds and returns a (1−4ϵ)-approximate DDS with high probability.

5 Near-linear MPC algorithm

  • The algorithm computes vertex degrees, removes low-degree vertices, samples remaining edges, then moves the sample to one machine for local densest-subgraph computation.The sample has O(n log n) edges with probability at least 1 −n−6, and degree computation, sampling, and moving edges each take O(1) rounds.Source: §5 · pp. 19–20
  • For ϵ ∈(0, 1/4), the near-linear-memory MPC algorithm computes a (1−4ϵ)-approximate DDS in O(1) rounds with probability at least 1−n−4.It uses ˜O(n) memory per machine and ˜O(m) total memory.Source: §5 · p. 20

6 Sublinear-time algorithm

The sublinear-time algorithm simulates Peel-Sample with incident-list queries and uses an LP algorithm to find an approximate DDS. Its guarantee combines near-linear time, space, and query complexity with a (1−12ε)-approximation.

6 Sublinear-time algorithm

  • For z≥1, edges are sampled through in-neighbors of surviving T vertices; for z<1, sampling uses out-neighbors of surviving S vertices.This one-sided peeling choice lets the algorithm sample remaining edges using the incident-list oracle.Source: §6 · p. 20, §6.2 · p. 22

6.1 LP algorithm satisfies edge-threshold

  • With probability at least 1−2n^-4, the sampled graph H preserves feasibility of DualH((1+ε)pD*, z*) for D* equal to the original DDS density.The guarantee applies to z* associated with an optimal densest subgraph.Source: §6.1 · pp. 21–22
  • The LP algorithm uses MWU on DualG(D, z), then rounds its weights to recover an approximate DDS; a nonempty output satisfies edge-threshold with α≥1/(1−9ε).The paper uses this LP approach because it returns an approximate subgraph satisfying edge-threshold in near-linear time in the input graph size.Source: §6 · p. 20, §6.1 · pp. 21–22

6.2 Full sublinear-time algorithm

  • ˜O(n) time, space, and incident-list queries yield a (1−12ε)-approximate DDS with probability at least 1−n^-3.The algorithm runs instances over candidate D and z values and returns the nonempty result corresponding to the largest D.Source: §6.2 · pp. 22–23
  • For each D and z, the algorithm peels low-degree vertices from T when z≥1, or from S otherwise, and returns the remaining subgraph if its density is at least D.It runs instances over D and z values in parallel, using powers of (1+ε).Source: §6.2 · p. 22
Loading 2610.00846v1…