DAG Covers: The Steiner Point Effect
Sujoy Bhore Hsien-Chih Chang Jonathan Conroy Arnold Filtser Eunjin Oh Nicole Wein Da Wei Zheng · 2026
Read DAG Covers: The Steiner Point Effect by Sujoy Bhore Hsien-Chih Chang Jonathan Conroy Arnold Filtser Eunjin Oh Nicole Wein Da Wei Zheng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04186.txt.
Introduction
Sujoy Bhore and team opened the study of Steiner DAG covers, where cover DAGs may include extra Steiner points. Earlier work on general digraphs set the stage for this structured-graph study. The authors showed that any digraph of treewidth tw admits a Steiner cover with stretch 1 using just 2 DAGs, and planar digraphs admit a near-exact cover with 2 DAGs. They also proved a sharp gap: non-Steiner covers for treewidth-1 graphs with stretch below 2 and sub-quadratic extra edges need at least logarithmically many DAGs.
Catalog record
| CREATOR | Sujoy Bhore Hsien-Chih Chang Jonathan Conroy Arnold Filtser Eunjin Oh Nicole Wein Da Wei Zheng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49105 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.04186
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DAG Covers: The Steiner Point Effect Sujoy Bhore Hsien-Chih Chang Jonathan Conroy Arnold Filtser Eunjin Oh Nicole Wein Da Wei Zheng Abstract Given a weighted digraph G G , a ( t , g , μ ) (t,g,\mu) -DAG cover is a collection of g g dominating DAGs D 1 , … , D g D_{1},\dots,D_{g} such that all distances are approximately preserved: for every pair ( u , v ) (u,v) of vertices, min i d D i ( u , v ) ≤ t ⋅ d G ( u , v ) \min_{i}d_{D_{i}}(u,v)\leq t\cdot d_{G}(u,v) , and the total number of non- G G edges is bounded by | ( ∪ i D i ) ∖ G | ≤ μ |(\cup_{i}D_{i})\setminus G|\leq\mu . Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of 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 {\rm tw} admits a ( 1 , 2 , O ~ ( n ⋅ tw ) ) (1,2,\tilde{O}(n\cdot{\rm tw})) -Steiner DAG cover. For planar digraphs we provide a ( 1 + ε , 2 , O ~ ε ( n ) ) (1+\varepsilon,2,\tilde{O}_{\varepsilon}(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 1 with stretch t < 2 t<2 and sub-quadratic number of extra edges requires Ω ( log n ) \Omega(\log n) DAGs. 1 Introduction Tree covers are fundamental graph primitives with wide-ranging applications in network routing, approximate distance oracles, spanners, and related problems. They offer sparse and structurally simple representations of large graphs while retaining key distance relationships. Formally, a stretch- t tree cover of an edge-weighted undirected graph G is a collection of weighted trees \mathcal{T} on vertex set V such that for every pair u,v\in V , (1) for every tree T\in\mathcal{T} , we have d_{G}(u,v)\penalty\ \leq\penalty\ d_{T}(u,v) , and (2) there exists some T\in\mathcal{T} such that d_{T}(u,v)\;\leq\;t\cdot d_{G}(u,v) . Tree covers were introduced 30 years ago by Arya, Das, Mount, Salowe, and Smid [ 5 ] in the context of Euclidean spaces and have been extensively studied ever since. In \mathbb{R}^{d} , they established stretch- (1+\varepsilon) tree cover with O(\varepsilon^{-d}\log(1/\varepsilon)) trees, which was later improved to O(\varepsilon^{-d+1}\log(1/\varepsilon)) [ 30 ] . For general graphs, tree covers were studied implicitly in [ 7 , 8 ] , and then in their seminal work Thorup and Zwick [ 54 ] showed a tree cover with stretch 2k-1 and O\!\left(n^{1/k}\log n\right) trees, for any integer k\geq 1 . Tree covers have found many of their applications in graphs with geometric or topological structure. In particular, tree covers have been extensively studied and applied in the context of Euclidean metrics [ 5 , 24 , 30 ] , doubling metrics [ 9 , 21 , 32 , 34 ] , planar, bounded treewidth, and minor-free graphs [ 17 , 22 , 25 , 29 , 39 ] . In sharp contrast, directed graphs admit a far weaker repertoire of usable distance-preserving structures. Many sparsification primitives that play a central role in undirected graphs are either provably impossible to obtain in directed settings (e.g., sparse spanners [ 3 ] or efficient distance oracles [ 54 ] ) or remain substantially less understood (e.g., distance preservers and hopsets). For directed hopsets, recent work has made substantial progress, yet polynomial gaps between upper and lower bounds persist, in contrast to the near-tight landscape for undirected counterparts (see, e.g., [ 16 , 18 , 28 , 41 , 42 , 45 , 56 ] ). Directed acyclic graphs (DAGs) are natural analogs of trees in directed graphs and often distance problems become more tractable on DAGs than general directed graphs. For instance, computing single-source shortest paths with negative weights is somewhat trivial in DAGs and achievable in linear time, yet for general directed graphs the problem remains extremely difficult. Distance preservers also exhibit a gap: the best bounds known for DAGs are strictly stronger than those for general directed graphs [ 19 ] . Even for hopsets, where upper bounds for the simpler shortcut-set problem extend readily in DAGs, analogous results are more elusive for general directed graphs [ 16 , 45 ] . Motivated by this phenomenon, in a recent work [ 6 ] , Assadi, Hoppenworth, and Wein introduced the notion of DAG cover analogous to a tree cover: informally, given a weighted directed graph G , a DAG cover is a collection of DAGs such that no DAG underestimates any distance, and every distance d_{G}(u,v) is approximated by at least one of the DAGs (see Definition 1 ). They observe that a directed cycle constitutes a trivial lower bound if each DAG is required to be a subgraph of G . In this case n DAGs are needed even to preserve reachability. (From the upper bounds side, n DAGs can always trivially preserve distances exactly by taking a shortest paths tree from each vertex.) Thus, it is necessary to allow the addition of edges not from G . However, allowing quadratically many additional edges trivializes the problem: only two dense DAGs with opposite topological orders yield exact distances by adding all \Theta(n^{2}) edges consistent with the ordering (with appropriate edge weights). Thus, the goal becomes to trade-off between three parameters: the number of DAGs, the stretch, and the number of additional edges. Building upon [ 6 ] , Filtser [ 37 ] proved the best-known upper bound for general directed graphs: with O(\log n) DAGs, it is possible to achieve stretch \tilde{O}(\log n) , with the addition of \tilde{O}(m) edges. See Appendix 1.3 for additional related work. 1.1 Our Setting: Steiner DAG Covers Given that DAG covers necessarily require additional edges not from G , it is only natural to consider allowing additional vertices not from G . Indeed, this question of Steiner DAG cover was explicitly asked in both [ 6 ] and [ 37 ] . We initiate the study of Steiner DAG covers. We focus, in particular, on the important graph classes of planar digraphs and bounded treewidth digraphs (i.e., the underlying undirected graph has bounded treewidth). Our focus is motivated by the fact that some of the biggest success stories of tree covers are their applications to metrics with geometric or topological structure such as planar graphs and bounded treewidth graphs (in addition to e.g. minor-free graphs, Euclidean metrics, and doubling metrics). Applications in these settings include, for example, distance oracle, spanners/emulators, low-hop emulator, distance labeling schemes, routing schemes, additive metric embeddings (e.g. [ 5 , 22 , 23 , 25 , 29 , 34 , 39 , 43 ] ). For these special classes of graphs, one can achieve much better tree covers than in general graphs. This raises the question: Can we obtain DAG covers for important special classes of graphs that are much better than those for general graphs (possibly with