A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911471068250112 |
|---|---|
| author | Baste, Julien De Meyer, Lucas Giocanti, Ugo Objois, Etienne Picavet, Timothé |
| author_facet | Baste, Julien De Meyer, Lucas Giocanti, Ugo Objois, Etienne Picavet, Timothé |
| contents | Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve this upper bound on the pathwidth to a polynomial one; namely, we show that every graph whose edge set can be covered by $k$ shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. Moreover, we prove that when $k\leq 3$, every such graph has pathwidth at most $k$ (and this bound is tight). Finally, we show that even though there exist graphs with arbitrarily large treewidth whose vertex set can be covered by $2$ isometric trees, every graph whose set of edges can be covered by $2$ isometric trees has treewidth at most $2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02901 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths Baste, Julien De Meyer, Lucas Giocanti, Ugo Objois, Etienne Picavet, Timothé Combinatorics Discrete Mathematics Dumas, Foucaud, Perez and Todinca (2024) recently proved that every graph whose edges can be covered by $k$ shortest paths has pathwidth at most $O(3^k)$. In this paper, we improve this upper bound on the pathwidth to a polynomial one; namely, we show that every graph whose edge set can be covered by $k$ shortest paths has pathwidth $O(k^4)$, answering a question from the same paper. Moreover, we prove that when $k\leq 3$, every such graph has pathwidth at most $k$ (and this bound is tight). Finally, we show that even though there exist graphs with arbitrarily large treewidth whose vertex set can be covered by $2$ isometric trees, every graph whose set of edges can be covered by $2$ isometric trees has treewidth at most $2$. |
| title | A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2510.02901 |