PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.30458v1cs.DMcs.DSmath.CO

TL;DR

The paper asks how covering a graph with a small number of shortest or approximately shortest routes constrains its width, and develops width bounds and XP recognition algorithms. It proves polynomial pathwidth bounds for exact shortest-path covers, a superlinear lower bound, and bounded treewidth for quasi-shortest covers. The resulting XP algorithms apply to quasi-shortest path and walk covers, while explicit exponents and FPT algorithms remain open.

  • Problem

    Whether vertex-covered graphs have polynomial pathwidth remained open, while the known edge-cover pathwidth bound was O(k^4).

    Source: §1 · p. 2

  • Method

    The paper bounds treewidth for shortest and quasi-shortest covers, then combines those bounds with pathwidth techniques and a Blocked-CMSO meta-theorem for XP algorithms.

    Source: §1 · pp. 2, 4, 5

  • Results

    Exact shortest-path covers have pathwidth O(k^3) for vertex coverage and O(k^2 log k) for edge coverage; infinitely many graphs also attain an Ω(k log k) lower bound.

    Source: §9 · p. 18

  • Takeaways & Limitations

    Quasi-shortest path and walk covers support XP recognition and construction algorithms, and can better model real-world applications.

    Source: §9 · p. 18

    The gaps between upper and lower bounds stem from the quadratic treewidth bound and additional costs in the pathwidth techniques.

    Source: §9 · p. 18

Abstract

from arXiv · show

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 $(\alpha,\beta)$-quasi-shortest for $\alpha\geq1$ and $\beta\geq 0$ if each contiguous segment has length at most $\alpha$ times the distance between its endpoints plus $\beta$. 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$ $(\alpha,\beta)$-quasi-shortest paths or walks, then its treewidth is $O_{\alpha,\beta}(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 $\Omega(k\log k)$, providing the first superlinear lower bound. For graphs covered by $k=2$ $(\alpha,0)$-quasi-shortest paths with $\alpha>1$, we show that, unlike treewidth and unlike the case $\alpha=1$ and $\beta=0$ of exact shortest paths, the pathwidth may be unbounded. Finally, for every fixed rationals $\alpha\geq1$ and $\beta\geq 0$, we give XP algorithms with a running time of $n^{f(k,\alpha,\beta)}$ for some function~$f$ that decide whether the vertices of a graph can be covered by at most $k$ $(\alpha,\beta)$-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]

1 Introduction

The paper studies how covering vertices or edges by shortest routes constrains graph width, extending recent work on shortest-path covers. It establishes polynomial pathwidth bounds, superlinear lower bounds, and XP algorithms for quasi-shortest route covers.

1 Introduction

  • Shortest-path covers have practical motivations in route planning and patrols, and geodesic convexity supports binary-search label recovery in active learning.The paper also motivates allowing small detours and walks for route applications.Source: §1 · pp. 2–3
  • Vertex covers by k (α, β)-quasi-shortest paths or walks yield treewidth O_{α,β}(k^2), via linear metric growth and a result of Campbell et al. [12].For graphs excluding a fixed minor H, the bound improves to O_{α,β,H}(k).Source: §1 · p. 4
  • Vertex-covered graphs admit pathwidth O(k^3), resolving the main open question after only an exponential bound was known.The result applies whether or not the paths also cover the edges.Source: §1 · pp. 2, 4
  • Edge-covered graphs admit pathwidth O(k^2 log k), improving the previous O(k^4) bound.For graphs excluding a fixed minor H, the bound is O_H(k log k).Source: §1 · p. 5
  • Some cubic expanders show that treewidth and pathwidth can be Ω(k log k) for edge-covered graphs, ruling out linear bounds.This is the first known superlinear lower bound and answers negatively a question of Baste et al. [4].Source: §1 · pp. 3, 5
  • For α > 1, two (α, 0)-quasi-shortest paths can cover graphs of arbitrarily large pathwidth.The paper contrasts this with exact shortest paths, while retaining bounded treewidth in the quasi-shortest setting.Source: §1 · pp. 2, 5
  • For fixed rational α ≥ 1 and β ≥ 0, Blocked CMSO supports XP algorithms for quasi-shortest path and walk covers.The exponent depends on k, α, and β; these algorithms generalize the exact-shortest-path XP result of Dumas et al. [26].Source: §1 · p. 5

2 Preliminaries

The preliminaries fix graph and route conventions and define the quasi-shortest cover problems. They also introduce metric growth and the standard treewidth and pathwidth parameters.

2 Preliminaries

  • Graphs are finite, simple, undirected, and unweighted; paths of length zero are allowed, and the route budget k is a positive integer.Distances count minimum edge lengths; walks count repeated edge occurrences, while paths have distinct vertices.Source: §2 · pp. 5–6
  • A walk is (α, β)-quasi-shortest when every contiguous subwalk has length at most α times its endpoint distance plus β.A quasi-shortest path is a simple path satisfying the same condition; α = 1 and β = 0 gives a shortest path.Source: §2 · p. 6
  • A vertex path cover covers all vertices, while an edge path cover covers all edges; paths may share vertices and edges.The corresponding walk cover uses the distinct vertices visited by each walk.Source: §2 · p. 6
  • Metric growth bounds the largest connected subgraph of radius at most r, while pathwidth restricts a tree decomposition's decomposition tree to a path.Treewidth and pathwidth are subgraph-monotone, and tw(G) ≤ pw(G).Source: §2 · p. 6

3 Treewidth upper bounds

The section bounds treewidth for graphs covered by quasi-shortest paths or walks by controlling how much each cover intersects a metric ball. Excluding a fixed minor improves the bound to linear in the number of covering paths or walks.

3 Treewidth upper bounds

  • Each (α, β)-quasi-shortest path intersects any radius-r ball in at most 2αr + β + 1 vertices, yielding linear metric growth for a k-path cover.The metric-growth treewidth theorem of Campbell et al. [12] converts that growth bound into the quadratic treewidth bound.Source: §3 · p. 7
  • Vertex-covered graphs have treewidth at most 49a^2k^2 + 30ak for (α, β)-quasi-shortest paths, where a = 2α + β + 1.For exact shortest paths, the section gives tw(G) ≤ 441k^2 + 90k.Source: §3 · p. 7
  • The same treewidth bound holds for graphs vertex-covered by k (α, β)-quasi-shortest walks.For walks, the proof bounds the segment between the first and last visits to a ball; its length is at most 2αr + β.Source: §3 · p. 7
  • For H-minor-free graphs, the treewidth bound improves to O_H(ak); planar graphs covered by k exact shortest paths satisfy tw(G) ≤ 36k + 1.This follows by applying the minor-free metric-growth theorem to the same linear-growth bounds.Source: §3 · pp. 7–8

4 Polynomial upper bound for pathwidth when covering the vertices

For vertex covers by exact shortest paths, the section proves the first polynomial pathwidth bound. It combines a path partition adapted to distance layers with a treewidth-based pathwidth construction; these results do not extend to quasi-shortest paths.

4 Polynomial upper bound for pathwidth when covering the vertices

  • These pathwidth results apply to shortest paths, not quasi-shortest paths.The section notes that the metric-growth treewidth theorem used earlier does not extend directly to pathwidth.Source: §4 · p. 8
  • From any root, O(3^k) well-colored paths cover every vertex, with each path at most 2k edges longer than the distance to its endpoint.The construction extends the branching-tree method of Dumas et al. [26].Source: §4 · p. 8
  • A partition into k shortest paths can be refined into O(k3^k) paths, each meeting every distance layer at most once.The construction cuts well-colored paths at color changes and whenever distance to the root fails to increase; the partition hypothesis is necessary for this lemma.Source: §4 · pp. 9–10
  • With treewidth at most w, a partition into N paths that meet each layer at most once gives pathwidth O(w log(N + 1)).The proof recursively splits along a weighted centroid of a tree decomposition.Source: §4 · pp. 10–11
  • For any graph G whose vertices are covered by k shortest paths, pw(G) = O(k^3); the proof bounds tw(H) = O(k^2) and derives pw(G) = O(k^3).Source: §4 · p. 11
  • The proof duplicates vertices into cliques so the covering paths partition the new graph, then applies the treewidth and distance-layer bounds.Choosing one copy of each original vertex gives an induced copy of the input graph, so its pathwidth is no larger.Source: §4 · p. 11

5 Improving the pathwidth upper bound when covering the edges

For edge covers by shortest paths, the section improves the pathwidth upper bound by combining a treewidth bound with a small pathwidth modulator and a logarithmic decomposition argument. It also gives a linear-logarithmic bound for graphs excluding a fixed minor.

5 Improving the pathwidth upper bound when covering the edges

  • The improved edge-covering pathwidth bounds in this section do not apply to quasi-shortest paths.The underlying result used for the modulator concerns covers by shortest paths.Source: §5 · p. 11
  • The proof uses vertex sets of size at most 720k^3 + 4k per covering path to leave components of pathwidth at most 6k.Combining these sets gives a modulator, after which the treewidth and modulator-size bounds yield the pathwidth estimate.Source: §5 · pp. 11, 13
  • A graph of treewidth at most w with a nonempty set X of size r and pw(G − X) ≤ p has pw(G) ≤ (w + p + 2)(⌊log2 r⌋ + 6) − 1.The argument replaces hanging subtrees of a tree decomposition with path decompositions and bounds the resulting decomposition tree's pathwidth.Source: §5 · pp. 12–13
  • If k shortest paths cover the edges and tw(G) ≤ w, then pw(G) ≤ (w + 6k + 2)(⌊4 log2 k⌋ + 16) − 1; consequently pw(G) = O(k^2 log k).For H-minor-free graphs, the bound improves to pw(G) = O_H(k log k).Source: §5 · p. 13

6 A superlinear lower bound for edge-covering by shortest paths

The section establishes a superlinear pathwidth lower bound for graphs whose edges are covered by shortest paths. Its construction uses cubic bipartite Ramanujan graphs and covers their edges with short paths forced to be shortest by girth.

6 A superlinear lower bound for edge-covering by shortest paths

  • For infinitely many k, cubic graphs with edges covered by at most k shortest paths have pathwidth Ω(k log k).The construction derives this bound from graphs with linear treewidth and k = Θ(n / log n) covering paths.Source: §6 · pp. 13–14
  • Cubic bipartite Ramanujan graphs have girth Θ(log n), and their expander property gives linear treewidth.The proof uses their high girth to cover cycles with paths shorter than half the girth.Source: §6 · p. 13
  • A 3-edge-coloring partitions the edges into three matchings; unions of two matchings form cycles that can be covered by Θ(n / log n) shortest paths.Paths shorter than half the girth are shortest, since any shortcut would create a cycle shorter than the girth.Source: §6 · pp. 13–14

7 Small quasi-shortest path covers can have unbounded pathwidth

With any fixed α > 1, two (α, 0)-quasi-shortest paths can cover graphs of arbitrarily large pathwidth. The construction achieves pathwidth w with graphs of order 2^Oα(w).

7 Small quasi-shortest path covers can have unbounded pathwidth

  • For every α > 1 and integer w ≥ 0, a graph of order 2^Oα(w) has edge-covering by two (α, 0)-quasi-shortest paths and pathwidth at least w.Thus no pathwidth bound depending only on the number of covering paths holds in this setting.Source: §7 · pp. 14–15
  • The recursive construction combines two copies of the previous graph with length-l and length-m connectors, producing two equal-length covering paths ending at a common vertex.At each level, the paths have length 2d + l + m when the previous paths have length d.Source: §7 · p. 14
  • The covering paths remain (α, 0)-quasi-shortest because subpaths between common vertices differ in length by at most a factor α, allowing excursions to be replaced.For endpoints in different copies, the relevant path lengths lie in [l, l + 2d]; for an endpoint at z, they lie in [m, m + l + 2d].Source: §7 · p. 14
  • Removing the length-l connectors leaves a subdivision of a complete binary tree, whose pathwidth yields the lower bound; the recursive graph size grows as 2^Oα(w).The proof uses the complete binary tree's pathwidth ⌈h/2⌉ and chooses h = 2w.Source: §7 · p. 15

8 XP recognition for quasi-shortest path/walk covers

The paper encodes quasi-shortest path covers as ∀CMSO2 feasibility queries and applies a treewidth-based meta-theorem to obtain XP recognition algorithms. A clique-expansion reduction extends the approach to walk covers.

8 XP recognition for quasi-shortest path/walk covers

  • The path formula checks quasi-shortness by universally considering subpaths and endpoint pairs, reformulating the distance condition so only one quantified-set-dependent weight term appears in a comparison.The reformulation uses the complement of a path's edge set to express its length relative to the fixed full edge set.Source: §8 · pp. 15–16
  • A size-O(k) ∀CMSO2 formula encodes covers by at most k quasi-shortest paths, with each label specifying a vertex set and an edge set.The formula requires the encoded vertex sets to cover all vertices; empty labels allow fewer than k paths.Source: §8 · p. 16
  • The XP meta-theorem evaluates ∀CMSO2 queries on graphs of bounded treewidth in parameter-dependent time, returning satisfying assignments when they exist.The paper's query size is O(k), and its treewidth-based algorithm aggregates parameter-only factors into the XP exponent.Source: §8 · pp. 16–17
  • For fixed rational α ≥ 1 and β ≥ 0, recognizing vertex covers by at most k (α, β)-quasi-shortest paths takes XP time n^fα,β(k).The algorithm uses the quadratic treewidth bound to obtain a bounded-width decomposition, then evaluates the cover query.Source: §8 · p. 17
  • The same XP-time guarantee holds for recognizing vertex covers by at most k (α, β)-quasi-shortest walks for fixed rational α ≥ 1 and β ≥ 0.The walk algorithm reduces to a constrained path-cover query on a graph whose vertices are replaced by cliques.Source: §8 · pp. 17–18
  • For β ≥ 1, replacing each vertex by a clique of size ⌊β⌋ + 1 represents repeated visits in walks as distinct vertices on simple paths, subject to three path constraints.The constraints prohibit colored clique edges, limit subpaths returning to the same clique, and require every replacement clique to be intersected.Source: §8 · pp. 17–18

9 Conclusion

The paper establishes polynomial upper bounds for treewidth and pathwidth under shortest-path covers, alongside superlinear lower bounds. It also identifies open questions about tight bounds and fixed-parameter algorithms for quasi-shortest path and walk covers.

9 Conclusion

  • For exact shortest-path covers, treewidth is O(k^2), vertex-cover pathwidth is O(k^3), and edge-cover pathwidth is O(k^2 log k); infinitely many graphs have an Ω(k log k) lower bound.The lower bound rules out linear upper bounds for these settings.Source: §9 · p. 18
  • The polynomial pathwidth upper bound for vertex-covered graphs answers a previously open question, while the paper's other bounds improve prior results.The earlier result cited in the paper provided only an exponential upper bound for vertex-covered graphs.Source: §9 · p. 18
  • The gaps between upper and lower bounds arise from the quadratic treewidth bound and additional costs of the pathwidth-modulator and well-colored path partition techniques.Source: §9 · p. 18
  • Open questions include tight treewidth and pathwidth bounds for shortest-path covers and whether quasi-shortest path and walk cover recognition is fixed-parameter tractable.The FPT question is posed both for treewidth and for the number of solution paths.Source: §9 · pp. 18–19
Loading 2610.30458v1…