On graphs coverable by chubby shortest paths
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913717806956544 |
|---|---|
| author | Hatzel, Meike Pilipczuk, Michał |
| author_facet | Hatzel, Meike Pilipczuk, Michał |
| contents | 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 $ρ$ from one of them, then $G$ is $(3,12ρ)$-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ρ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02160 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On graphs coverable by chubby shortest paths Hatzel, Meike Pilipczuk, Michał Combinatorics Discrete Mathematics 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 $ρ$ from one of them, then $G$ is $(3,12ρ)$-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ρ$ 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. |
| title | On graphs coverable by chubby shortest paths |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.02160 |