{"id":"arxiv/2610.30458","url":"https://arxiv.org/abs/2610.30458","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers","domain":"cs.DM","source":"arxiv","authors":["Li-Hsuan Chen","Florent Foucaud","Ling-Ju Hung","Ralf Klasing","Lucas Lorieau","Peter Rossmanith"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}