DAG Covers: The Steiner Point Effect

Abstract

Given a weighted digraph $G$, a $(t,g,\hat{I}¼)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots ,D_g$ such that all distances are approximately preserved: for every pair $(u,v)$ of vertices, ${\min }_i{d}_{D_i}(u,v)\le t\cdot d_G(u,v)$, and the total number of non-$G$ edges is bounded by $|({\cup }_i{D}_i)\setminus G|\le \hat{I}¼$. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of \emph{Steiner} DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a $(1,2,\tilde{O}(n\cdot tw))$-Steiner DAG cover. For planar digraphs we provide a $(1+\epsilon ,2,{\tilde{O}}_{\epsilon }(n))$-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth $1$ with stretch $t<2$ and sub-quadratic number of extra edges requires $\hat{I}\text{c◯}(\log n)$ DAGs.