View PDF HTML (experimental)

Abstract:Given a graph $G=(V,E)$, a collection $\mathcal{T}$ of spanning trees of $G$ is called a spanning tree cover of stretch $\alpha$ if for every $u,v\in V$ there is a tree $T_{uv}\in\mathcal{T}$, such that \[d_{T_{uv}}(u,v)\leq\alpha\cdot d_G(u,v)~.\]
Spanning tree covers were introduced in the pioneering work of Gupta et al. [GKR04], that showed that $p$-path-separable graphs admit stretch-$3$ spanning tree covers with size $O(p\log n)$. Many subsequent papers focused on a relaxed notion of non-spanning tree covers, in which the trees are required to be dominating, but may use edges that do not belong to the graph. In particular, Bartal et al. [BFN22] devised a construction of non-spanning tree covers with stretch $1+\epsilon$ and size $O(p\cdot\frac{\log^2n}{\epsilon^2})$. Recently, for $K_r$-minor-free graphs, Chang et al. [CCL+23,CCL+24] devised a non-spanning tree cover with stretch $1+\epsilon$ and size $2^{\frac{1}{\epsilon}r^{O(r)}}$, and an exact spanning tree cover with size $r^{O(diam(G))}$. However, the problem of devising spanning tree covers with stretch smaller than $3$ and small size for general $p$-path-separable graphs remained open.
We show that $p$-path-separable graphs admit spanning tree covers with stretch $1+\epsilon$ and size $O(p\cdot\frac{\log^2n}{\epsilon})$. Moreover, we demonstrate that one can trade stretch for size, and devise spanning tree covers with stretch $O(k\log\log p)$ and size $O(kp^{\frac{1}{k}}\cdot\log^{2}n)$ for strongly $p$-path-separable graphs. We also provide a tradeoff for weakly path-separable graphs. For $K_r$-minor-free graphs, we devise spanning tree covers with stretch $O(k\log\log r)$ and size $O(kr^{2+\frac{1}{k}}\cdot\log^{2}n)$. For such graphs, it is only known that $p=r^{4602}$. Thus, for $r=\Omega(\log n)$ and $k\geq2$, this size is much smaller than that of our tree cover of stretch $1+\epsilon$.

Submission history

From: Idan Shabat [view email]
[v1] Sun, 9 Nov 2025 07:55:58 UTC (169 KB)
[v2] Tue, 28 Jul 2026 11:03:04 UTC (1,349 KB)