arXiv · Oct 1, 2026
Sparsification Framework for Directed Densest Subgraph
By Slobodan Mitrović, Theodore Pan
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 · 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-ε)-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-ε 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-ε)-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-ε)-approximate DDS, improving over the O(√log n)-round (0.5-ε)-approximation algorithm of Mitrovi'c and Pan (2024). In the sublinear-time setting, we obtain an algorithm using O(n) time, space, and oracle queries to compute a (1-ε)-approximate DDS, improving over the O(n^(1.5)) time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).