# Near-Optimal Fully Dynamic Densest Subgraph

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

## Key facts

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

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

- [Sketch-Based Anomaly Detection in Streaming Graphs](https://mlsanity.com/paper/2106.04486/) (2021)
- [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)
- [Fast and Simple Densest Subgraph with Predictions](https://mlsanity.com/paper/2505.12600/) (2025)

## Abstract (arXiv)

We give the first fully dynamic algorithm which maintains a (1-ε)-approximate densest subgraph in worst-case time poly(log n, ε-1) per update. Dense subgraph discovery is an important primitive for many real-world applications such as community detection, link spam detection, distance query indexing, and computational biology. We approach the densest subgraph problem by framing its dual as a graph orientation problem, which we solve using an augmenting path-like adjustment technique. Our result improves upon the previous best approximation factor of left(frac14 - εright) for fully dynamic densest subgraph [Bhattacharya et. al., STOC `15]. We also extend our techniques to solving the problem on vertex-weighted graphs with similar runtimes. Additionally, we reduce the (1-ε)-approximate densest subgraph problem on directed graphs to O(log n/ε) instances of (1-ε)-approximate densest subgraph on vertex-weighted graphs. This reduction, together with our algorithm for vertex-weighted graphs, gives the first fully-dynamic algorithm for directed densest subgraph in worst-case time poly(log n, ε-1) per update. Moreover, combined with a near-linear time algorithm for densest subgraph [Bahmani et. al., WAW `14], this gives the first near-linear time algorithm for directed densest subgraph.