On graphs coverable by k shortest paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916999970422784 |
|---|---|
| author | Dumas, Maël Foucaud, Florent Perez, Anthony Todinca, Ioan |
| author_facet | Dumas, Maël Foucaud, Florent Perez, Anthony Todinca, Ioan |
| contents | We show that if the edges or vertices of an undirected graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is upper-bounded by a single-exponential function of $k$. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph $G$ and a set of $k$ pairs of vertices called terminals, asks whether $G$ can be covered by $k$ shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph $G$ and a set of $k$ terminals, asks whether there exist $\binom{k}{2}$ shortest paths covering $G$, each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_15088 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On graphs coverable by k shortest paths Dumas, Maël Foucaud, Florent Perez, Anthony Todinca, Ioan Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics We show that if the edges or vertices of an undirected graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is upper-bounded by a single-exponential function of $k$. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph $G$ and a set of $k$ pairs of vertices called terminals, asks whether $G$ can be covered by $k$ shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph $G$ and a set of $k$ terminals, asks whether there exist $\binom{k}{2}$ shortest paths covering $G$, each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter $k$. |
| title | On graphs coverable by k shortest paths |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2206.15088 |