{
  "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].",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.30458",
  "author_total": 6,
  "authors": [
    {
      "name": "Li-Hsuan Chen"
    },
    {
      "name": "Florent Foucaud"
    },
    {
      "name": "Ling-Ju Hung"
    },
    {
      "name": "Ralf Klasing"
    },
    {
      "name": "Lucas Lorieau"
    },
    {
      "name": "Peter Rossmanith"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/4tnk4sgm32vxs.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.30458",
  "fulltext_url": null,
  "id": "4tnk4sgm32vxs",
  "issns": [],
  "landing_url": "https://hal.science/hal-05799937v2",
  "language": "en",
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DM"
    ],
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "hal",
      "0.info"
    ],
    [
      "hal",
      "0.math"
    ],
    [
      "hal",
      "1.info.info-dm"
    ],
    [
      "hal",
      "1.info.info-ds"
    ],
    [
      "hal",
      "1.math.math-co"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7223072971",
  "pdf_url": "https://hal.science/hal-05799937/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-21",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/4tnk4sgm32vxs.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:01Z",
      "native_id": "hal-05799937",
      "source": "hal",
      "url": "https://hal.science/hal-05799937v2"
    },
    {
      "first_seen": "2026-10-30T12:34:38Z",
      "native_id": "2610.30458",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.30458"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers",
  "title_text": "Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers",
  "type": "preprint",
  "updated_at": "2026-10-30T12:34:38Z",
  "url": "https://research.draconitic.com/paper/4tnk4sgm32vxs",
  "venue": "HAL",
  "versions": []
}