Summary
This paper looks at how having just a few shortest paths can cover a graph limits how complicated it can be, measured by pathwidth and treewidth. The authors found a way to show that if a few shortest or nearly shortest paths cover all the points of a graph, the complexity grows only polynomially with the number of paths. They also found better and new bounds for cases where edges, instead of points, are covered by paths. Additionally, they present algorithms to decide if such coverings exist, although some examples show that complexity can still get quite large in certain tricky cases.
What this means in practice
- •For network designers: Determine efficiently if network nodes can be covered by a limited number of nearly shortest routing paths to simplify network analysis.
- •For software engineers: Use polynomial bounds on pathwidth to optimize algorithms that rely on graph decompositions for data structures close to shortest paths.
A theory result. No direct application yet.
Authors
Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung, Ralf Klasing, Lucas Lorieau, Peter Rossmanith
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]