Dumas, Foucaud, Perez, and Todinca SIAM J. Disc. Math. , 2024 proved that if the vertex set of a graph G can be covered by k shortest paths, then the pathwidth of G is bounded by O (k 3ᵏ). We prove a coarse variant of this theorem: if in a graph G one can find~k shortest paths such that every vertex is at distance at most from one of them, then G is (3, 12) -quasi-isometric to a graph of pathwidth k^O (k) and maximum degree O (k), and G admits a path-partition-decomposition whose bags are coverable by k^O (k) balls of radius at most 2 and vertices from non-adjacent bags are at distance larger than 2. We also discuss applications of such decompositions in the context of algorithms for finding maximum distance independent sets and minimum distance dominating sets in graphs.
Hatzel et al. (Mon,) studied this question.