Title: On graphs coverable by chubby shortest paths Show Chinese title

Title: 关于可通过胖最短路径覆盖的图

Abstract: 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 $\mathcal{O}(k \cdot 3^k)$. 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 $\rho$ from one of them, then $G$ is $(3,12\rho)$-quasi-isometric to a graph of pathwidth $k^{\mathcal{O}(k)}$ and maximum degree $\mathcal{O}(k)$, and $G$ admits a path-partition-decomposition whose bags are coverable by $k^{\mathcal{O}(k)}$ balls of radius at most $2\rho$ and vertices from non-adjacent bags are at distance larger than $2\rho$. 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. Show Chinese abstract

Abstract: 杜马斯、福科、佩雷斯和托迪尼亚[SIAM J. Disc. Math., 2024]证明，如果图$G$的顶点集可以被$k$条最短路径覆盖，那么$G$的路径宽度被$\mathcal{O}(k \cdot 3^k)$所限制。 我们证明了这个定理的一个粗略变体：如果在一个图$G$中可以找到~$k$条最短路径，使得每个顶点到其中一条路径的距离不超过$\rho$，那么$G$是一个路径宽度为$(3,12\rho)$且最大度数为$\mathcal{O}(k)$的图的$k^{\mathcal{O}(k)}$-拟等距，并且$G$具有一个路径划分分解，其袋子可以被最多$k^{\mathcal{O}(k)}$个半径不超过$2\rho$的球覆盖，并且非相邻袋子中的顶点之间的距离大于$2\rho$。 我们还讨论了这种分解在图中寻找最大距离独立集和最小距离支配集的算法中的应用。