pith. sign in

arxiv: 2604.04752 · v1 · submitted 2026-04-06 · 💻 cs.DS

DAG Projections: Reducing Distance and Flow Problems to DAGs

Bernhard Haeupler , Yonggang Jiang , Thatchaphol Saranurak This is my paper

Pith reviewed 2026-05-10 19:32 UTC · model grok-4.3

classification 💻 cs.DS
keywords directed graphsDAG projectionsdistance approximationmaximum flowgraph sparsificationparallel algorithmsshortest pathshopsets
0
0 comments X

The pith

Every directed graph admits a sparse DAG with m^{1+o(1)} edges that approximates all-pairs distances or subset max-flows.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any directed graph G with n vertices and m edges can be replaced by a directed acyclic graph having only m to the power 1 plus little-o of 1 edges. This DAG projection approximates distances between every pair of vertices to a factor of 1 plus 1 over polylog n, or approximates maximum flows between every pair of vertex subsets to a factor of n to the little-o of 1. The projections can be built in m to the power 1 plus little-o of 1 time and in parallel with almost linear work and subpolynomial depth. A sympathetic reader would care because the construction lets algorithms that work well on acyclic graphs be applied directly to general directed graphs, and it yields immediate improvements to several known results on distance preservers, hopsets, and flow algorithms.

Core claim

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/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. Our DAG projections admit m^{1+o(1)}-time constructions and almost-optimal parallel constructions even when the input G is not a DAG. DAG projections immediately transfer results on DAGs to directed graphs and reduce major open problems on almost-optimal parallel algorithms for exact single-source shortest paths and maximum flow to easier settings on DAGs or from a,

What carries the argument

The DAG projection: a directed acyclic graph with m^{1+o(1)} edges constructed from the input digraph that approximately preserves all-pairs distances or maximum flows between subsets.

Load-bearing premise

The result assumes the existence of efficient (1+1/polylog n)-approximate shortest-path or n^{o(1)}-approximate max-flow algorithms on DAGs together with efficient constructions for the projections themselves.

What would settle it

A concrete counterexample would be a family of directed graphs where every DAG on m^{1+δ} edges for arbitrarily small δ loses more than a 1+1/polylog(n) factor on some pair distance or more than an n^{o(1)} factor on some subset flow.

Figures

Figures reproduced from arXiv: 2604.04752 by Bernhard Haeupler, Thatchaphol Saranurak, Yonggang Jiang.

Figure 1
Figure 1. Figure 1: Old and new landscapes of parallel SSSP and maximum flow algorithms. The green area [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
read the original 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 $\Omega(\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+\epsilon)$-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},\epsilon)$-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces DAG projections: for any directed graph G with n vertices and m edges, there exists a DAG with m^{1+o(1)} edges that (1 + 1/polylog n)-approximates all-pairs distances or n^{o(1)}-approximates max-flow between all vertex-subset pairs (S,T). The projection is constructed in m^{1+o(1)} time and admits almost-optimal parallel algorithms (m^{1+o(1)} work, m^{o(1)} depth) assuming the corresponding primitives on DAGs. The technique is used to improve prior bounds on (1+ε)-distance preservers, single-source min-cut, (n^{1/3},ε)-hopsets, and combinatorial max-flow algorithms, while reducing three major open problems on exact parallel directed SSSP and max-flow to easier DAG or undirected settings.

Significance. If the central claims hold, the result supplies a near-optimal size reduction from general digraphs to DAGs that preserves strong approximation guarantees for two fundamental problems. This enables direct transfer of simpler, faster DAG algorithms to the directed case and yields concrete improvements to several recent results. The almost-optimal parallel bounds and the explicit reduction of long-standing open questions on exact parallel SSSP and max-flow are particularly valuable. The construction is non-circular, with o(1) terms arising from iterated-logarithmic parameter regimes that are explicitly bounded in the analysis.

minor comments (2)
  1. [Abstract] Abstract and Theorem 1.1: the precise dependence of the o(1) terms on iterated logarithms is stated in the body but could be summarized in the abstract and main theorem for immediate readability.
  2. [Section 5] Section 5 (applications): the improvement to the (n^{1/3},ε)-hopset construction is stated as simpler but the exact saving in work or depth relative to Bernstein-Wein is not quantified; a short comparison table would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, accurate summary of our contributions, and recommendation to accept the manuscript. We are pleased that the referee highlighted the significance of the DAG projection technique, its applications to improving prior bounds, and the reductions of open problems on parallel directed algorithms.

Circularity Check

0 steps flagged

No significant circularity; construction is self-contained reduction

full rationale

The core result is an explicit construction of a DAG projection via layering and sampling that produces a DAG of size m^{1+o(1)} while preserving the stated (1+1/polylog n) distance or n^{o(1)} flow approximations. This construction is described directly in the paper without defining the output in terms of itself or fitting parameters to the target quantities. Self-citations appear only in the applications section (e.g., for combinatorial max-flow) and are not invoked to justify the projection's existence or size bound. The reductions of open problems are one-way implications from general digraphs to DAGs and do not create circular dependence. No equation or step reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the existence of the DAG projections and on standard graph-theoretic definitions; no free parameters or invented physical entities are introduced.

axioms (1)
  • standard math Standard definitions of directed graphs, shortest-path distances, and maximum flows between vertex subsets.
    The paper relies on basic graph theory concepts that are not proved inside the work.
invented entities (1)
  • DAG projection no independent evidence
    purpose: A sparse acyclic graph that approximates distances or flows of the original directed graph.
    This is the main new object introduced by the paper; it is a constructed artifact rather than an independently evidenced physical entity.

pith-pipeline@v0.9.0 · 5772 in / 1427 out tokens · 78588 ms · 2026-05-10T19:32:11.964149+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    A general approach to online network optimization problems

    Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms (TALG) , 2(4):640--660, 2006

    work page 2006

  2. [2]

    Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights

    Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, and Hsin - Hao Su. Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights. In ESA , volume 308 of LIPIcs , pages 13:1--13:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    work page 2024

  3. [3]

    Faster approximation algorithms for restricted shortest paths in directed graphs

    Vikrant Ashvinkumar, Aaron Bernstein, and Adam Karczmarz. Faster approximation algorithms for restricted shortest paths in directed graphs. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 5263--5277. SIAM, 2025

    work page 2025

  4. [4]

    Covering approximate shortest paths with dags

    Sepehr Assadi, Gary Hoppenworth, and Nicole Wein. Covering approximate shortest paths with dags. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 2269--2280, 2025

    work page 2025

  5. [5]

    Parallel approximate maximum flows in near-linear work and polylogarithmic depth

    Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong. Parallel approximate maximum flows in near-linear work and polylogarithmic depth. In SODA , pages 3997--4061. SIAM , 2024

    work page 2024

  6. [6]

    Parallel approximate maximum flows in near-linear work and polylogarithmic depth

    Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong. Parallel approximate maximum flows in near-linear work and polylogarithmic depth. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3997--4061. SIAM, 2024

    work page 2024

  7. [7]

    Parallel approximate undirected shortest paths via low hop emulators

    Alexandr Andoni, Clifford Stein, and Peilin Zhong. Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 322--335, 2020

    work page 2020

  8. [8]

    Deterministic negative-weight shortest paths in nearly linear time via path covers

    Anonymous Authors. Deterministic negative-weight shortest paths in nearly linear time via path covers. 2025. Manuscript

    work page 2025

  9. [9]

    Probabilistic approximation of metric spaces and its algorithmic applications

    Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science , pages 184--193. IEEE, 1996

    work page 1996

  10. [10]

    Combinatorial maximum flow via weighted push-relabel on shortcut graphs

    Aaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak, and Ta-Wei Tu. Combinatorial maximum flow via weighted push-relabel on shortcut graphs. In FOCS . IEEE , 2025

    work page 2025

  11. [11]

    Maximum flow by augmenting paths in n^ 2+o(1) time

    Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak, and Ta-Wei Tu. Maximum flow by augmenting paths in n^ 2+o(1) time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2056--2077. IEEE, 2024

    work page 2024

  12. [12]

    Negative-weight single-source shortest paths in near-linear time: Now faster! In FOCS , pages 515--538

    Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-weight single-source shortest paths in near-linear time: Now faster! In FOCS , pages 515--538. IEEE , 2023

    work page 2023

  13. [13]

    Covering metric spaces by few trees

    Yair Bartal, Nova Fandina, and Ofer Neiman. Covering metric spaces by few trees. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , pages 20--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2019

    work page 2019

  14. [14]

    Multi-embedding and path approximation of metric spaces

    Yair Bartal and Manor Mendel. Multi-embedding and path approximation of metric spaces. In SODA , volume 3, pages 424--433, 2003

    work page 2003

  15. [15]

    Negative-weight single-source shortest paths in near-linear time

    Aaron Bernstein, Danupon Nanongkai, and Christian Wulff - Nilsen. Negative-weight single-source shortest paths in near-linear time. Commun. ACM , 68(2):87--94, 2025. First anounce at FOCS'22

    work page 2025

  16. [16]

    Linear size distance preservers

    Greg Bodwin. Linear size distance preservers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 600--615. SIAM, 2017

    work page 2017

  17. [17]

    Closing the gap between directed hopsets and shortcut sets

    Aaron Bernstein and Nicole Wein. Closing the gap between directed hopsets and shortcut sets. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 163--182. SIAM, 2023

    work page 2023

  18. [18]

    Sparse source-wise and pair-wise distance preservers

    Don Coppersmith and Michael Elkin. Sparse source-wise and pair-wise distance preservers. In SODA , pages 660--669. SIAM , 2005

    work page 2005

  19. [19]

    Parallel exact shortest paths in almost linear work and square root depth

    Nairen Cao and Jeremy T Fineman. Parallel exact shortest paths in almost linear work and square root depth. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 4354--4372. SIAM, 2023

    work page 2023

  20. [20]

    Fineman, and Katina Russell

    Nairen Cao, Jeremy T. Fineman, and Katina Russell. Efficient construction of directed hopsets and parallel approximate shortest paths. In STOC , pages 336--349. ACM , 2020

    work page 2020

  21. [21]

    Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

    Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In FOCS , pages 612--623. IEEE , 2022

    work page 2022

  22. [22]

    Graph connectivities, network coding, and expander graphs

    Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Graph connectivities, network coding, and expander graphs. SIAM Journal on Computing , 42(3):733--751, 2013

    work page 2013

  23. [23]

    Polylog-time and near-linear work approximation scheme for undirected shortest paths

    Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM , 47(1):132--166, 2000

    work page 2000

  24. [24]

    Constant approximation of min-distances in near-linear time

    Shiri Chechik and Tianyi Zhang. Constant approximation of min-distances in near-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 896--906. IEEE, 2022

    work page 2022

  25. [25]

    Approximation algorithms for min-distance problems in dags

    Mina Dalirrooyfard and Jenny Kaufmann. Approximation algorithms for min-distance problems in dags. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , pages 60--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021

    work page 2021

  26. [26]

    Stochastic embedding of digraphs into dags

    Arnold Filtser. Stochastic embedding of digraphs into dags. arXiv preprint arXiv:2509.23458 , 2025

    work page arXiv 2025

  27. [27]

    Clan embeddings into trees, and low treewidth graphs

    Arnold Filtser and Hung Le. Clan embeddings into trees, and low treewidth graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 342--355, 2021

    work page 2021

  28. [28]

    Fleischmann, George Z

    Henry L. Fleischmann, George Z. Li, and Jason Li. Improved directed expander decompositions. CoRR , abs/2507.09729, 2025

    work page arXiv 2025

  29. [29]

    A tight bound on approximating arbitrary metrics by tree metrics

    Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages 448--455, 2003

    work page 2003

  30. [30]

    A polynomial-time tree decomposition to minimize congestion

    Chris Harrelson, Kirsten Hildrum, and Satish Rao. A polynomial-time tree decomposition to minimize congestion. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures , pages 34--43, 2003

    work page 2003

  31. [31]

    Adaptive-adversary-robust algorithms via small copy tree embeddings

    Bernhard Haepler, D Ellis Hershkowitz, and Goran Zuzic. Adaptive-adversary-robust algorithms via small copy tree embeddings. In 30th Annual European Symposium on Algorithms (ESA 2022) , volume 244, page 63. Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

    work page 2022

  32. [32]

    Near-linear-time, optimal vertex cut sparsifiers in directed acyclic graphs

    Zhiyang He, Jason Li, and Magnus Wahlstr \"o m. Near-linear-time, optimal vertex cut sparsifiers in directed acyclic graphs. In 29th Annual European Symposium on Algorithms (ESA 2021) , pages 52--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2021

    work page 2021

  33. [33]

    New separations and reductions for directed hopsets and preservers

    Gary Hoppenworth, Yinzhan Xu, and Zixuan Xu. New separations and reductions for directed hopsets and preservers. In SODA , pages 4405--4443. SIAM , 2025

    work page 2025

  34. [34]

    New diameter-reducing shortcuts and directed hopsets: Breaking the barrier

    Shimon Kogan and Merav Parter. New diameter-reducing shortcuts and directed hopsets: Breaking the barrier. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1326--1341. SIAM, 2022

    work page 2022

  35. [35]

    Representative sets and irrelevant vertices: New tools for kernelization

    Stefan Kratsch and Magnus Wahlstr \"o m. Representative sets and irrelevant vertices: New tools for kernelization. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 450--459. IEEE, 2012

    work page 2012

  36. [36]

    Faster parallel algorithm for approximate shortest path

    Jason Li. Faster parallel algorithm for approximate shortest path. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 308--321, 2020

    work page 2020

  37. [37]

    From graphs to matrices, and back: new techniques for graph algorithms

    Aleksander Madry. From graphs to matrices, and back: new techniques for graph algorithms . PhD thesis, Massachusetts Institute of Technology, 2011

    work page 2011

  38. [38]

    Ramsey partitions and proximity data structures

    Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society , 9(2):253--275, 2007

    work page 2007

  39. [39]

    Minimizing congestion in general networks

    Harald Racke. Minimizing congestion in general networks. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages 43--52. IEEE, 2002

    work page 2002

  40. [40]

    Optimal hierarchical decompositions for congestion minimization in networks

    Harald R \"a cke. Optimal hierarchical decompositions for congestion minimization in networks. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 255--264, 2008

    work page 2008

  41. [41]

    The complexity of minimum cut and maximum flow problems in an acyclic network

    Vijaya Ramachandran. The complexity of minimum cut and maximum flow problems in an acyclic network. Networks , 17(4):387--392, 1987

    work page 1987

  42. [42]

    Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances

    V \' a clav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, and Goran Zuzic. Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances. In STOC , pages 321--334. ACM , 2023

    work page 2023

  43. [43]

    Improved guarantees for tree cut sparsifiers

    Harald R \"a cke and Chintan Shah. Improved guarantees for tree cut sparsifiers. In European Symposium on Algorithms , pages 774--785. Springer, 2014

    work page 2014

  44. [44]

    a cke, Chintan Shah, and Hanjo T \

    Harald R \"a cke, Chintan Shah, and Hanjo T \"a ubig. Computing cut-based hierarchical decompositions in almost linear time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 227--238. SIAM, 2014

    work page 2014

  45. [45]

    Expander decomposition and pruning: Faster, stronger, and simpler

    Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2616--2635. SIAM, 2019

    work page 2019

  46. [46]

    Approximate distance oracles

    Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM (JACM) , 52(1):1--24, 2005

    work page 2005

  47. [47]

    Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality

    Jan Van Den Brand, Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, Maximilian Probst Gutenberg, and Sushant Sachdeva. Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2010--2032. IEEE, 2024

    work page 2024