2026-07-22T04:09:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25499 2026-03-19T13:34:12Z ddc:004 open_access

A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths Baste, Julien De Meyer, Lucas Giocanti, Ugo Objois, Etienne Picavet, Timothé Structural Graph Theory Coverings Metrics Pathwidth Treewdidth Parameterized Algorithms Layerings Dumas, Foucaud, Perez and Todinca [SIAM J. Disc. Math., 2024] recently proved that every graph whose edge set can be covered by k shortest paths has pathwidth at most 3^k. In this paper, we improve this upper bound on the pathwidth to a polynomial bound; namely, we show that every graph whose edge set can be covered by k shortest paths has pathwidth O(k⁴), answering a question from the same paper. Moreover, we also prove that when k ≤ 3, every such graph has pathwidth at most k (and this bound is tight). Eventually, we show that even though there exist graphs with arbitrary large treewidth whose vertex set can be covered by 2 isometric trees, every graph whose set of edges can be covered by 2 isometric trees has treewidth at most 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julien Baste and Lucas De Meyer and Ugo Giocanti and Etienne Objois and Timothé Picavet 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.10 urn:nbn:de:0030-drops-254999 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode