Spanning Tree Covers for Path-Separable Graphs: Trading Stretch for Size

Abstract

Given a graph $G=(V,E)$, a collection $\mathcal{T}$ of spanning trees of $G$ is called a spanning tree cover of stretch $\hat{I}\pm$ if for every $u,v\in V$ there is a tree $T_{uv}\in \mathcal{T}$, such that \[d_{T_{uv}}(u,v)\leqα\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+\hat{I}\mu$ and size $O(p\cdot \frac{{\log }^{2}n}{\hat{I}{\mu }^2})$. Recently, for $K_r$-minor-free graphs, Chang et al. [CCL+23,CCL+24] devised a non-spanning tree cover with stretch $1+\hat{I}\mu$ and size $2^{\frac{1}{\hat{I}}\mu 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+\hat{I}\mu$ and size $O(p\cdot \frac{{\log }^{2}n}{\hat{I}}\mu )$. 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(k{p}^{\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(k{r}^{2+\frac{1}{k}}\cdot {\log }^{2}n)$. For such graphs, it is only known that $p=r^{4602}$. Thus, for $r=\hat{I}\text{c◯}(\log n)$ and $k\ge 2$, this size is much smaller than that of our tree cover of stretch $1+\hat{I}\mu$.

71 pages, 4 figure