Given a weighted digraph $G$, a $(t,g,\mu)$‑DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that for every vertex pair $(u,v)$ we have $\min_i d_{D_i}(u,v) \le t\cdot d_{G}(u,v)$, and the total number of edges not present in $G$ satisfies $| (\cup_i D_i) \setminus G | \le \mu$. Prior work by Assadi, Hoppenworth and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the concept of Steiner DAG cover, where the DAGs may contain Steiner points, and obtains much tighter bounds on important graph families such as planar digraphs and low‑treewidth digraphs. The main contributions are:
- Any digraph of treewidth $tw$ admits a $(1,2,\tilde{O}(n\cdot tw))$‑Steiner DAG cover.
- For planar digraphs we construct a $(1+\varepsilon,2,\tilde{O}_{\varepsilon}(n))$‑Steiner DAG cover for any constant $\varepsilon>0$.
- In stark contrast, without Steiner points even graphs of treewidth $1$ (i.e., trees) cannot achieve a non‑trivial cover with stretch $t<2$, establishing a matching lower bound.
These findings demonstrate that allowing Steiner points dramatically reduces both the number of added edges and the stretch factor, especially on structured graphs.
Blogger's Review: By leveraging Steiner points, the authors break through the limitations of traditional DAG covers, delivering a powerful tool for distance approximation on planar and low‑treewidth digraphs. The theoretical insights are solid and open up promising directions for practical algorithms.