DAG Projections: Reducing Distance and Flow Problems to DAGs

We show that every directed graph G with n vertices and m edges admits a directed acyclic graph (DAG) with m1+o(1) edges, called a DAG projection, that can either (1+1/polylog (n))-approximate distances between all pairs of vertices (s,t) in G, or no(1)-approximate maximum flow between all pairs of vertex subsets (S,T) in G. Previous similar results suffer a Ω(logn) 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 m1+o(1)-time constructions. Further, they admit almost-optimal parallel constructions, i.e., algorithms with m1+o(1) work and mo(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 (n1/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/polylog(n))-approximation on DAGs, and (3) From exact directed maximum flow to no(1)-approximation on DAGs.