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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Graphs Coverable by Chubby Shortest Paths

  • Meike Hatzel,
  • Michał Pilipczuk

摘要

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.