# Sparsification Framework for Directed Densest Subgraph

Preprint · Slobodan Mitrović, Theodore Pan

- Archive id: arxiv:2610.00846
- Published: 2026-10-01
- arXiv: https://arxiv.org/abs/2610.00846
- Source URL: https://arxiv.org/abs/2610.00846
- PDF: https://arxiv.org/pdf/2610.00846
- Provenance: arxiv

## Abstract

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ć 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).

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.