DAG Projections: Reducing Distance and Flow Problems to DAGs

Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak

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/…