On graphs coverable by chubby shortest paths

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 kO(k) and maximum degree O(k), and G admits a path-partition-decomposition whose bags are coverable by kO(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.