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

arXiv: https://arxiv.org/abs/1504.02268 · HTML: https://mlsanity.com/paper/1504.02268/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2015.

## Built on by (most cited first, 5 of 5)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Fully-Dynamic Decision Trees](https://mlsanity.com/paper/2212.00778/) (2022)
- [Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees](https://mlsanity.com/paper/2302.03994/) (2023)
- [Simple yet Effective Node Property Prediction on Edge Streams under Distribution Shifts](https://mlsanity.com/paper/2504.00328/) (2025)
- [Fast and Simple Densest Subgraph with Predictions](https://mlsanity.com/paper/2505.12600/) (2025)

## Abstract (arXiv)

While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of em both time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called em densest subgraph problem. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. In a graph G = (V, E), the "density" of a subgraph induced by a subset of nodes S subseteq V is defined as |E(S)|/|S|, where E(S) is the set of edges in E with both endpoints in S. In the densest subgraph problem, the goal is to find a subset of nodes that maximizes the density of the corresponding induced subgraph. For any ε>0, we present a dynamic algorithm that, with high probability, maintains a (4+ε)-approximation to the densest subgraph problem under a sequence of edge insertions and deletions in a graph with n nodes. It uses tilde O(n) space, and has an amortized update time of tilde O(1) and a query time of tilde O(1). Here, tilde O hides a O(polylog1+ε n) term. The approximation ratio can be improved to (2+ε) at the cost of increasing the query time to tilde O(n). It can be extended to a (2+ε)-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in em one pass. The previously best algorithm in this setting required O(log n) passes [Bahmani, Kumar and Vassilvitskii, VLDB'12]. The space required by our algorithm is tight up to a polylogarithmic factor.