Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
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 α ≥ 1 and β ≥ 0 if each contiguous segment has length at most α times the distance between its endpoints plus β. This relaxation forms a reasonable model of approximate shortest paths permitting local detours, closer to applications. For graphs vertex-covered by k shortest paths, an exponential upper bound on pathwidth was known [Dumas et al., ISAAC 2022/SIDMA 2024]. 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 [Baste et al., STACS 2026] 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. The metric growth toolkit also implies improved upper bounds for H-minor-free graphs. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by at most k shortest paths and whose treewidth and pathwidth are in Ω(k log k), providing the first superlinear lower bound for the problem. 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 α ≥ 1 and β ≥ 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 and return such a family whenever one exists. The algorithms combine our treewidth upper bounds with exact evaluation of Blocked-CMSO queries using the algorithmic meta-theorem from [Dreier et al., LICS 2025]. These algorithms extend a similar result for exact shortest paths from [Dumas et al., ISAAC 2022/SIDMA 2024].
Related
- Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
- The Maximum Number of Shortest Paths in Graphs
- A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
- Shifted Pell–Lucas Polynomial-Based Algorithms for Fractional and Classical Rosenau–Hyman Models
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
BibTeX
@misc{chen2026polynomial,
title = {{Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers}},
author = {Li-Hsuan Chen and Florent Foucaud and Ling-Ju Hung and Ralf Klasing and Lucas Lorieau and Peter Rossmanith},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30458},
eprint = {2610.30458},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05799937v2},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
AU - Li-Hsuan Chen
AU - Florent Foucaud
AU - Ling-Ju Hung
AU - Ralf Klasing
AU - Lucas Lorieau
AU - Peter Rossmanith
PY - 2026
DA - 2026/10/21
PB - HAL
DO - 10.48550/arxiv.2610.30458
UR - https://hal.science/hal-05799937v2
AB - 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 α ≥ 1 and β ≥ 0 if each contiguous segment has length at most α times the distance between its endpoints plus β. This relaxation forms a reasonable model of approximate shortest paths permitting local detours, closer to applications. For graphs vertex-covered by k shortest paths, an exponential upper bound on pathwidth was known [Dumas et al., ISAAC 2022/SIDMA 2024]. 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 [Baste et al., STACS 2026] 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. The metric growth toolkit also implies improved upper bounds for H-minor-free graphs. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by at most k shortest paths and whose treewidth and pathwidth are in Ω(k log k), providing the first superlinear lower bound for the problem. 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 α ≥ 1 and β ≥ 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 and return such a family whenever one exists. The algorithms combine our treewidth upper bounds with exact evaluation of Blocked-CMSO queries using the algorithmic meta-theorem from [Dreier et al., LICS 2025]. These algorithms extend a similar result for exact shortest paths from [Dumas et al., ISAAC 2022/SIDMA 2024].
ER -