# DAG Projections: Reducing Distance and Flow Problems to DAGs

Preprint · Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

- Archive id: arxiv:2604.04752
- Published: 2026-04-06
- arXiv: https://arxiv.org/abs/2604.04752
- Source URL: https://arxiv.org/abs/2604.04752
- PDF: https://arxiv.org/pdf/2604.04752
- Provenance: arxiv

## Abstract

We show that every directed graph $G$ with $n$ vertices and $m$ edges admits a directed acyclic graph (DAG) with $m^{1+o(1)}$ edges, called a DAG projection, that can either $(1+1/\\text{polylog} (n))$-approximate distances between all pairs of vertices $(s,t)$ in $G$, or $n^{o(1)}$-approximate maximum flow between all pairs of vertex subsets $(S,T)$ in $G$. Previous similar results suffer a $Ω(\\log n)$ approximation factor for distances \[Assadi, Hoppenworth, Wein, STOC'25\] \[Filtser, SODA'26\] and, for maximum flow, no prior result of this type is known. Our DAG projections admit $m^{1+o(1)}$-time constructions. Further, they admit almost-optimal parallel constructions, i.e., algorithms with $m^{1+o(1)}$ work and $m^{o(1)}$ depth, assuming the ones for approximate shortest path or maximum flow on DAGs, even when the input $G$ is not a DAG. DAG projections immediately transfer results on DAGs, usually simpler and more efficient, to directed graphs. As examples, we improve the state-of-the-art of $(1+ε)$-approximate distance preservers \[Hoppenworth, Xu, Xu, SODA'25\] and single-source minimum cut \[Cheung, Lau, Leung, SICOMP'13\], and obtain simpler construction of $(n^{1/3},ε)$-hop-set \[Kogan, Parter, SODA'22\] \[Bernstein, Wein, SODA'23\] and combinatorial max flow algorithms \[Bernstein, Blikstad, Saranurak, Tu, FOCS'24\] \[Bernstein, Blikstad, Li, Saranurak, Tu, FOCS'25\]. Finally, via DAG projections, we reduce major open problems on almost-optimal parallel algorithms for exact single-source shortest paths (SSSP) and maximum flow to easier settings: (1) From exact directed SSSP to exact undirected ones, (2) From exact directed SSSP to $(1+1/\\text{polylog}(n))$-approximation on DAGs, and (3) From exact directed maximum flow to $n^{o(1)}$-approximation on DAGs.

_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.