# Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers

Preprint · Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung, Ralf Klasing, Lucas Lorieau, Peter Rossmanith

- Archive id: arxiv:2610.30458
- Published: 2026-10-21
- arXiv: https://arxiv.org/abs/2610.30458
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.30458
- PDF: https://arxiv.org/pdf/2610.30458
- Provenance: arxiv

## Abstract

We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is $(α,β)$-quasi-shortest for $α\\geq1$ and $β\\geq 0$ if each contiguous segment has length at most $α$ times the distance between its endpoints plus $β$. For graphs vertex-covered by $k$ shortest paths, we establish the first known polynomial pathwidth bound of $O(k^3)$. For edge-coverage, we improve the previously known $O(k^4)$ upper bound to $O(k^2\\log k)$. As a main ingredient of the proofs, we first show that if the vertices of a graph can be covered by $k$ $(α,β)$-quasi-shortest paths or walks, then its treewidth is $O\_{α,β}(k^2)$; this is a consequence of the fact that such graphs have linear metric growth and the technique developed in \[Campbell et al., E-JC 2023\]. To obtain the above pathwidth upper bounds, we combine this result with techniques from the literature in a nontrivial way. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by $k$ shortest paths and whose pathwidth is $Ω(k\\log k)$, providing the first superlinear lower bound. For graphs covered by $k=2$ $(α,0)$-quasi-shortest paths with $α\>1$, we show that, unlike treewidth and unlike the case $α=1$ and $β=0$ of exact shortest paths, the pathwidth may be unbounded. Finally, for every fixed rationals $α\\geq1$ and $β\\geq 0$, we give XP algorithms with a running time of $n^{f(k,α,β)}$ for some function~$f$ that decide whether the vertices of a graph can be covered by at most $k$ $(α,β)$-quasi-shortest paths or walks. The algorithms combine our treewidth upper bounds with an algorithmic meta-theorem from \[Dreier et al., LICS 2025\]. \[abstract shortened to meet the arXiv requirements\]

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.