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

2012 ACM Subject Classification Theory of computation → Graph algorithms analysis; Theory of computation → Parameterized complexity and exact algorithms; Mathematics of computing →

Graph theory

Keywords and phrases shortest paths, quasi-shortest paths, geodesics, quasi-geodesics, isometric path cover, walks, treewidth, pathwidth, parameterized complexity, Blocked CMSO

Funding This research was partially supported by the NSTC–CNRS International Emerging Action (IEA) 2024–2025 “Quasi-Polynomial Time Approximation Algorithms for Some Network Design Optimization Problems” under grants 113–2927–I–141–501 and 114–2927–I–141–501. Florent Foucaud: ANR project GRALMECO (ANR-21-CE48-0004), French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), International Research Center “Innovation Transportation and Production Systems” of the I-SITE CAP 20-25. Ralf Klasing: ANR project TEMPOGRAL (ANR-22-CE48-0001). Lucas Lorieau: This author has received financial support from the CNRS through the MITI interdisciplinary programs.

Acknowledgements We thank Philip Whittington for bringing the metric-growth theorem of Campbell et al. [12] to our attention.

Introduction

Shortest paths in graphs (also called geodesics or isometric paths) are a fundamental concept in graph theory and computer science. We are interested in the problem of covering the vertices or the edges of a given graph by a small number of shortest paths, a natural optimization problem that recently attracted a lot of attention [4, 13, 14, 15, 16, 26]. Such covers provide a simplified model for network design problems of planning small collections of transportation routes that collectively visit the network while limiting detours, such as bus lines [6] or patrolling rounds [18]. Shortest-path covers also arise in active learning on graphs, where geodesic convexity allows labels along each covering path to be recovered through binary search [44]. It was recently shown that a graph whose vertices can be covered by few shortest paths has bounded (exponential) pathwidth [26]. Subsequently, a polynomial bound when also the edges are covered was proved [4]. Whether polynomial bounds also hold for vertex-coverage remained open.

We generalize this line of work by providing the first polynomial upper bound on the pathwidth of a graph when the vertices are covered (and no restriction on also covering the edges). This settles the main open problem in the area [4, 26]. We also give several improved upper bounds for the edge-covering case, for graphs excluding a fixed minor, or when the treewidth is considered, as well as a nontrivial lower bound. Motivated by real-world scenarios, we then relax the requirement of considering shortest paths only, and consider settings where the paths are “almost shortest” paths or walks (allowing a fixed multiplicative and additive distortion for every segment of the path/walk). We show that treewidth is bounded in this setting as well, however pathwidth is not. We use this to generalize the existing algorithmic results for covering graphs by shortest paths [26], providing XP algorithms for covering a graph in this more realistic scenario. (We use the standard terminology that an FPT running time has the form $f(k)n^{O(1)}$, while an XP running time has the form $n^{f(k)}$, up to parameter-dependent factors [23]; $n$ is the input size, $k$ the parameter, and $f$ a computable function.)

Quasi-shortest paths for traffic connections and patrol rounds. Requiring shortest paths can be unnecessarily rigid in applications: suppose for example that the paths represent bus or patrol routes: it is unrealistic that every itinerary is precisely a shortest path, and small detours can be allowed in order to reduce the total number of routes [6]. Similarly, it may be useful to allow crossing the same location several times, and to consider walks instead of paths [18]: consider a long path with an additional leaf $x$ adjacent to an internal vertex $v$. The resulting tree has three leaves, so no single simple path covers all its vertices. However, one patrol officer can instead follow the long path and, on reaching $v$, make the short excursion to $x$, before continuing along the path. We therefore consider a relaxation of the problem, similar to the definition of quasi-geodesics from coarse geometry and geometric group theory (and related to the quasi-isometries from these fields, also transposed to graphs in coarse graph theory), as follows.

For fixed reals $\alpha\ge1$ and $\beta\ge0$, a path or walk in a graph $G$ with vertex occurrences $v_1 \ldots v_t$ is $(\alpha,\beta)$-quasi-shortest if for any $i,j$ with $i < j$,

If $\alpha= 1$ and $\beta= 0$, the above definition simply describes shortest paths. Unlike a guarantee that applies only to the route’s endpoints, the above condition imposes a distortion for every segment of the path/walk. This definition is inspired by classic works in coarse geometry and geometric group theory on quasi-geodesics and quasi-isometries [10, 32]. The notion of a quasi-isometry was recently extended to coarse graph theory [31, 40], following earlier works on the similar notion of distance-approximating embeddings [19]. The definition of quasi-shortest paths we use is also similar to the notion of $(\alpha,\beta)$-spanners; such a spanner is a spanning subgraph $H$ of a host graph $G$ such that, for every pair $x,y$ of vertices, $\operatorname{dist}_{H}(x,y) \le\alpha\cdot\operatorname{dist}_{G}(x,y) + \beta$. The main difference is that in a spanner, the distortion condition may not apply to all $x$–$y$ paths, but only to the shortest ones. Less constrained distortion conditions, allowing a multiplicative distortion factor for the whole path, have been used in the context of approximate all-pairs-shortest paths [43]. Local geodesics (where every small subpath must be a shortest path, but without a global condition) are also considered in discrete geometry [17]. These two conditions (global distortion together with local optimality) have been combined in works considering alternative routes [1].

Further related work. Covering a graph by a minimum number of (unrestricted) paths is a fundamental and extensively studied problem, called Path Cover [11, 21, 36]; think of Hamiltonian Path as a prominent special case. The shortest path requirement that we consider is substantially stronger than an ordinary path cover: a Hamiltonian graph is covered by one path but may require arbitrarily many shortest paths to be fully covered (consider for example a square grid or a complete graph).

The problem of covering a graph by a minimum number of shortest paths arose in the context of the Cops and Robber pursuit-evasion game [3]. Covering by shortest paths still plays an important role in more modern techniques in the area, see for example the concept of cop-decompositions, which are special tree decompositions whose definition involves shortest path covers [2]. The problem was also studied for its own sake from a graph-theoretic perspective, see for example [29, 30, 42], and refer to the survey [36] on various types of path covering problems.

Dumas, Foucaud, Perez, and Todinca [26] proved that a graph vertex-covered by $k$ shortest paths has BFS-width (the maximum size of a BFS distance-layer [27]), and thus pathwidth, $O(k \cdot3^k)$, while the more constrained setting of also covering the edges gives $O(3^k)$ [26].

Baste, De Meyer, Giocanti, Objois, and Picavet [4] subsequently proved that a graph edge-covered by $k$ shortest paths has pathwidth $O(k^4)$. More precisely, their proof constructs a polynomial-size vertex set whose deletion leaves pathwidth $O(k)$. They asked whether the pathwidth might in fact be linear in $k$.

The (non-)existence of similar bounds when the graph is covered by isometric trees was also investigated, see [4, 5].

Hatzel and Pilipczuk [33] study a relaxation of the question in the realm of coarse graph theory: the $k$ routes remain shortest paths, but it is enough for every vertex to lie within distance $\rho$ of one of them. They proved that such graphs are $(3,12\rho)$-quasi-isometric to graphs of pathwidth $k^{O(k)}$.

The problem of covering a graph with a minimum possible number of exact shortest paths (often called Isometric Path Cover [13, 36] or Shortest Path Cover [28, 44]) is NP-hard, even for chordal graphs of diameter 2 [14] and 5-degenerate bipartite graphs of diameter 4 [28]. On the other hand, it is polynomial-time solvable on block graphs [41], chain graphs [16] and cographs [16]. FPT algorithms for the neighborhood diversity and the dual parameter $n-k$ were designed in [28].

In the fixed-terminal version of Shortest Path Cover, the $k$ endpoint pairs are part of the input, and the authors in [26] give an FPT algorithm in $k$ for deciding whether the input graph is coverable by $k$ shortest paths. When the algorithm must also choose the endpoints, enumerating the $2k$ endpoints and invoking the fixed-terminal algorithm gives time $f(k)n^{2k+O(1)}$, hence XP [26].

On chordal graphs (and more generally graphs of bounded treelength [14] or hyperbolicity [13]), on outerstring graphs [13] and on (theta,prism,pyramid)-free graphs [13], Shortest Path Cover was shown to admit a constant-factor approximation algorithm based on Dilworth’s theorem on poset chain coverings. For a connected graph, write $\operatorname{diam}(G)$ for the maximum distance between two vertices. Thiessen and Gärtner [44, Theorem 11] proved that Shortest Path Cover can be approximated within a factor of $1+\ln(\operatorname{diam}(G)+1)$ in $O(|V(G)|^4)$ time.

The version where the paths must be vertex-disjoint, which is used in the recent definition of geodesic treewidth [39] (which minimizes the treewidth of the graph obtained by contracting each path of a shortest path partition), has also been studied [15, 28, 37]. Notably, this variant is W[1]-hard when parameterized by pathwidth, but open for solution size [15]. The edge-disjoint variant is W[1]-hard on oriented graphs (in fact, DAGs) when parameterized by solution size [28].

Our results. Our main results concern improved upper and lower bounds on treewidth and pathwidth for graphs coverable by $k$ (quasi-)shortest paths, which answer open problems from [4, 26]. We first prove a quadratic $O(k^2)$ bound on the treewidth, which we then use to obtain our upper bounds on pathwidth.

To this end, we observe that the concept of metric growth (see § 2 for the definition) can be applied to such graphs: roughly speaking, the maximum intersection of any quasi-shortest path with any $r$-ball grows only linearly with the radius $r$. Hence, graphs whose vertices are coverable by $k$ $(\alpha,\beta)$-quasi-shortest paths have metric growth $O_{\alpha,\beta}(k)$, which directly implies $O_{\alpha,\beta}(k^2)$ using a result from Campbell et al. [12]. This bound is reduced to $O_{\alpha,\beta,H}(k)$ for graphs excluding a graph $H$ as a minor.

Then, we focus on pathwidth and on exact shortest paths. We use the above treewidth upper bound in conjunction with the technique of Dumas et al. [26] to obtain an $O(k^3)$ upper bound on pathwidth when the vertices (and not necessarily the edges) of the graph are covered by $k$ exact shortest paths. This shows that also pathwidth is polynomially bounded in this case, and solves the main open problem in the area.

We next improve the upper bound in the case where the $k$ shortest paths cover the edges. To this end, we prove a general conversion lemma: if $\operatorname{tw}(G)\le w$ and deleting $r$ vertices leaves a graph with pathwidth at most $p$, then $\operatorname{pw}(G)=O((w+p)\log r)$. We apply this lemma to the pathwidth-modulator of Baste et al. [4] and our treewidth upper bound, to yield the quadratic-logarithmic bound $O(k^2 \log k)$ on pathwidth. This improves the previous $O(k^4)$ bound from Baste et al. [4]. For graphs excluding a graph $H$ as a minor, we obtain $O_H(k \log k)$.

Regarding lower bounds, we prove that both the vertex-cover and the edge-cover pathwidth and treewidth upper bounds cannot be linear. Indeed, we show that certain cubic expanders of order $n$ with large girth have treewidth $\Omega(n)$ and can be edge-covered by $O(n/\log n)$ shortest paths. This implies an $\Omega(k \log k)$ treewidth (and pathwidth) lower bound, which is the first known superlinear lower bound. This answers negatively a question from Baste et al. [4].

When $\alpha> 1$, we also provide a construction of graphs covered by two $(\alpha,0)$-quasi-shortest paths but with arbitrarily large pathwidth, showing that the quasi-shortest setting behaves differently than the exact shortest setting.

A summary of the bounds we obtain can be found in Table 1.

coverage	covering objects	lower bound^1	upper bound^2
vertices/edges	$(\alpha,\beta)$-quasi-shortest paths/walks	$\Omega(k \log k)$	$O_{\alpha,\beta}(k^2)$	unbounded in $k$ when $\alpha> 1$
vertices	exact shortest paths	$\Omega(k \log k)$	$O(k^2)$	$O(k^3)$
edges	exact shortest paths	$\Omega(k \log k)$	$O(k^2)$	$O(k^2 \log k)$

Then, we apply the treewidth upper bound for quasi-shortest paths to obtain XP algorithms for $(\alpha,\beta)$-Quasi-Shortest Path Cover and $(\alpha,\beta)$-Quasi-Shortest Walk Cover (formally defined in § 2) parameterized by the number $k$ of paths. The main algorithmic ingredient is the logic introduced by Dreier, Ganian, and Hamm [24]. Their Blocked CMSO permits restricted cardinality comparisons under universal quantification and admits both approximate and exact evaluation theorems on bounded-treewidth graphs. We use their theorem as a black-box. The exponent of the running time depends on the formula and the width. The former depends on $k$, $\alpha$ and $\beta$, and the latter is in $O_{\alpha,\beta}(k^2)$; hence, we obtain a running time that is XP in $k$ for fixed rationals $\alpha$ and $\beta$. These algorithms generalize the XP algorithm for exact shortest paths obtained by Dumas et al. [26], to the setting of quasi-shortest paths and walks.

Outline. After the preliminaries, Section 3 contains the treewidth upper bounds, Section 4 the pathwidth upper bound for the vertex-covering case, Section 5 proves the pathwidth upper bound for the edge-covering case, Section 6 contains the pathwidth lower bound for exact shortest paths, Section 7 contains the unbounded pathwidth construction for quasi-shortest paths, and Section 8 gives the XP algorithms. We conclude in Section 9.

Preliminaries

All graphs are finite, simple, undirected, and unweighted. We allow paths of length zero, consisting of one vertex. Every route budget $k$ is a positive integer. For vertices $x,y$ of a graph $G$, let $\operatorname{dist}_G(x,y)$ denote the minimum number of edges in an $x$–$y$ path. A path is shortest if its length equals the distance between its endpoints; every subpath of a shortest path is shortest.

A walk is a sequence $W = w_0e_1w_1 \cdots e_tw_t$, where $e_j = w_{j-1}w_j$. Its length is $t$, counting edge occurrences, so repeated uses of an edge are counted separately. A subwalk $W[a,b]$ is the contiguous sequence from the occurrence $w_a$ to $w_b$. A path is a walk with pairwise distinct vertices.

A path is shortest precisely when it is $(1,0)$-quasi-shortest. A $(1,0)$-quasi-shortest walk cannot repeat a vertex, because the subwalk between two consecutive occurrences would have positive length and endpoint distance zero. Thus, it is also a shortest path.

A family $\mathcal{P}$ of paths is called a vertex path cover if $V(G) = \bigcup_{P\in\mathcal{P}} V(P)$, and an edge path cover if $E(G) = \bigcup_{P\in\mathcal{P}} E(P)$. Different paths may share vertices and edges. A vertex walk cover is defined analogously using the distinct vertices visited by each walk. For fixed $\alpha\ge1$ and $\beta\ge0$ ($\alpha,\beta$ may be real, or rational for practical purposes), we define the two following problems.

$(\alpha,\beta)$-Quasi-Shortest Path Cover

Input: A graph $G$ and an integer $k$.

Task: Determine whether at most $k$ $(\alpha,\beta)$-quasi-shortest paths cover $V(G)$. For positive instances, return the path cover.

$(\alpha,\beta)$-Quasi-Shortest Walk Cover

Input: A graph $G$ and an integer $k$.

Task: Determine whether at most $k$ $(\alpha,\beta)$-quasi-shortest walks cover $V(G)$. For positive instances, return the walk cover.

For a connected graph $H$, let $\operatorname{rad}(H) = \min_{z\in V(H)} \max_{v\in V(H)} \operatorname{dist}_H(z,v)$ be the radius of $H$. The metric growth of a graph $G$ is the following function $\operatorname{mg}_G : \mathbb{N} \to\mathbb{N}$: $\operatorname{mg}_G(r) = \sup\{ |V(H)| \mid H \subseteq G,\ H\text{ connected},\operatorname{rad}(H) \le r \}$. For $v \in V(G)$ and $r \ge0$, we denote the ball of radius $r$ centered at $v$ by $B_G(v,r) = \{u \mid\operatorname{dist}_G(u,v) \le r\}$.

A tree decomposition of $G$ is a tree $T$ with bags $(B_t)_{t\in V(T)}$ such that every graph vertex is in a bag, the endpoints of every graph edge occur together in a bag, and the bags containing any fixed graph vertex induce a connected subtree of $T$. Its width is $\max_t |B_t| - 1$, and the treewidth $\operatorname{tw}(G)$ is the minimum width. A path decomposition is a tree decomposition whose decomposition tree is a path; its minimum width is the pathwidth $\operatorname{pw}(G)$. Both parameters are subgraph-monotone, and $\operatorname{tw}(G) \le\operatorname{pw}(G)$. These are the standard width parameters; see, for example, Cygan et al. [23]. For the sake of clarity, we will sometimes consider that a path decomposition is an ordered sequence of bags. In this case, the concatenation of two path decompositions is simply the concatenation of the two sequences of bags. Note that in general, the concatenation of two path decompositions does not yield a path decomposition.

A graph $H$ is a minor of $G$ if it can be obtained from $G$ by vertex- and edge-deletions and edge-contractions.

Treewidth upper bounds

We show next how Theorem 2 yields a polynomial treewidth upper bound for our problem, when few paths cover the vertices of a graph $G$. (Notice that when the paths cover $E(G)$, except isolated vertices, they also cover $V(G)$ and all results from this section apply as well.) We will use the following theorems relating metric growth and treewidth.

The same authors also used grid minors to prove the following.

The key element to apply these results to our setting is the following lemma.

Proof. If the intersection between $V(P)$ and $B_G(z,r)$ is nonempty, let $x$ and $y$ be its first and last vertices in the order along $P$, and let $s = |E(P[x,y])|$. Quasi-shortness and the triangle inequality give $s \le\alpha\cdot\operatorname{dist}_G(x,y) + \beta\le\alpha(\operatorname{dist}_G(x,z) + \operatorname{dist}_G(z,y)) + \beta\le2\alpha r + \beta$. Every vertex of $P$ in $B_G(z,r)$ lies on $P[x,y]$, which has $s + 1 \le2\alpha r + \beta+ 1$ vertices, and the bound follows.

We now prove the main result of this section, which is a direct corollary of Lemma 4 and Theorem 2 by Campbell, Distel, Gollin, Harvey, Hendrey, Hickingbotham, Mohar, and Wood [12 Theorem 1].

Proof. Let $H \subseteq G$ be connected with radius at most $r \ge1$, and choose a center $z$ of $H$. Distances in $G$ can only be shorter than in $H$, so $V(H) \subseteq B_G(z,r)$. If $P_1,\ldots,P_k$ cover $V(G)$, then Lemma 4 and $r \ge1$ give $|V(H)| \le\sum_{i=1}^{k}|V(P_i) \cap B_G(z,r)| \le akr$. Thus, the metric growth of $G$ satisfies $\operatorname{mg}_G(r) \le akr$, and Theorem 2 with $c = ak$ proves the claim.

Proof. A shortest path is $(1,0)$-quasi-shortest, so we can apply Theorem 5 with $a = 3$.

We next show how to apply the same proof idea to walks.

Proof. We extend the proof of Lemma 4 and Theorem 5. Let $z \in V(G)$ and $r \ge0$ and consider one of the $k$ covering walks $W$. Take the first and last occurrences of vertices of $W$ in $B_G(z,r)$ and let $s$ be the length of the subwalk between them. Every distinct vertex of $V(W) \cap B_G(z,r)$ occurs in this interval. If $x,y$ are the endpoint vertices, then as in Lemma 4, $s \le\alpha\cdot\operatorname{dist}_G(x,y) + \beta\le2\alpha r + \beta$. Thus, the bound of Lemma 4 holds for the distinct vertices of every covering walk. Repeating the proof of Theorem 5 gives $\operatorname{mg}_G(r) \le akr$ and hence the claimed bound by Theorem 2.

We can also use Theorem 3 to obtain a linear upper bound for graphs excluding a fixed minor, in particular planar graphs.

Proof. The proofs of Theorems 5 and 7 give $\operatorname{mg}_G(r) \le akr$ and $\operatorname{mg}_G(r) \le3kr$ for exact shortest paths. Thus, the bounds follow immediately from Theorem 3. ◀

Polynomial upper bound for pathwidth when covering the vertices

In this section, we improve the existing upper bound for pathwidth when shortest paths cover the vertex set of the input graph $G$, deriving the first polynomial upper bound. Note that Theorem 2 cannot extend to pathwidth [12 Section 5], so the method used for proving Theorem 5 cannot be used to directly obtain a similar bound for pathwidth. We combine Corollary 6 with an extension of the construction of Dumas et al. [26 Section 4]. The results in this section apply only to shortest paths and not to quasi-shortest ones.

A layering of a graph $G$ is a function $\lambda: V(G) \to\mathbb{Z}$ such that $|\lambda(u) - \lambda(v)| \le1$ for every edge $uv$, and its layers are the sets $\lambda^{-1}(i)$. For example, the distances to a fixed root vertex of $G$ forms a layering of $G$.

We will also need the notion of well-colored paths from [26]. Given a graph $G$ whose vertices are covered by $k$ shortest paths, these covering paths are called the base paths of $G$ in [26]. We orient these base paths from one arbitrary endpoint to the other, and assign color $i$ to the vertices of the $i$-th base path. Let $\operatorname{Colors}(v)$ be the set of colors assigned in this way to vertex $v$.¹ A coloring of an arbitrary path $P$ of $G$ is the coloring of the vertices of $P$ obtained by choosing, for every vertex $v$ of $P$, any color in $\operatorname{Colors}(v)$. A colored path $P$ is well-colored if for each color that occurs in $P$, the vertices of $P$ of this color form a connected monochromatic subpath of $P$. The well-coloring lemma [26 Lemma 4.1] ensures the existence of a well-colored, shortest $a$–$b$ path for every $a,b \in V(G)$.

As one of the basic tools of this section, we argue that a slight extension of a construction used to prove [26 Lemma 4.2] also yields the following lemma.

Proof. We first give an outline of Dumas et al.’s construction [26 Section 4], and at the end, we explain how we modify their approach. The authors provide a recursive encoding of a set of well-colored paths. The goal of this recursive encoding is to upper-bound the size of the final set by a single-exponential function in $k$ (a simpler counting argument yields an upper bound that is factorial in $k$; [25 Section 4]). The set of paths initially contains, for each vertex $b$ of the layer $\lambda_a^{-1}(i)$ (with $\lambda_a = \operatorname{dist}_G(a,\cdot)$), a well-colored shortest $a$–$b$ path. At the end of the construction, the set will contain a well-colored $a$–$b$ path, that is not necessarily shortest, but $(1,2k)$-quasi-shortest.

Informally, they define a tree structure, called $k$-labeled branching tree [26 Definition 3.5], whose nodes represent sets of paths. The following invariant is preserved throughout the construction: each node $x$ is associated to a well-colored representative path $P_x$, defined as the longest path associated to $x$, and such that any other path associated to $x$ is either included in $P_x$, or admits $P_x$ as a prefix. This representative path is defined before Step 2.1 of [26 Lemma 4.2].

For any internal node $x$, every path is copied to a child, either unchanged or after undergoing a canonization operation that preserves its endpoints (Step 2.3 in [26 Lemma 4.2]). All paths that share the same color $c$ and orientation after their current representative path prefix are grouped together in a child node $x'$ of $x$, and the representative path of $x'$ is obtained by appending to $P_x$ a subpath of the base path whose color is $c$. An additional operation is carried out on the root node, in order to define the representative path of its child nodes (see Steps 1.1 to 1.3 in [26 Lemma 4.2]). Since all representative paths are well-colored, and each split fixes a new color segment in the representative path, the height of the $k$-labeled branching tree is at most $k$ [26 Claim 4.4]. This splitting stops when all paths of a node are included in its representative path. In this case, the considered node is a leaf of the $k$-labeled branching tree.

Furthermore, at depth $d$, the construction maintains the invariant

for every current $a$–$b$ path $P$ [26 Claim 4.3].² In other words, any $a$–$b$ path associated to a node of depth $d$ is a well-colored $(1,2d)$-quasi-shortest $a$–$b$ path. The authors finally prove that the number of leaves of a $k$-labeled branching tree is $O(3^k)$ in [26 Lemma 3.9 and Claim 4.5]. Note that this whole construction can be started with any set of well-colored shortest paths, all starting at a common vertex $a$.

We next prove the lemma statement by applying the same construction to a different starting set of paths. Consider the set $\mathcal{Q}$ containing, for any vertex $b \in V(G)-a$, a well-colored shortest $a$–$b$ path. (In [26], only paths to vertices of a fixed distance layer were considered.) Recall that the existence of such paths is justified in [26 Lemma 4.1]. We create a root node, to which we associate $\mathcal{Q}$, and we apply the previous construction. By construction, a path towards each vertex $b \in V(G)-a$ is included in one of the representative paths of a leaf of the obtained $k$-labeled branching tree, as the construction preserves path endpoints. Thus, by defining $\mathcal{P}$ as the set of all representative paths of leaves of the $k$-labeled branching tree, the (endpoints of) paths of $\mathcal{P}$ cover the vertices of $G$. The bound on the number of leaves yields $|\mathcal{P}| = O(3^k)$, and the maintained invariant (1) ensures that $|E(P)| \le\operatorname{dist}_G(a,b) + 2k$ for all $a$–$b$ paths of $\mathcal{P}$.

We next show how to apply Lemma 9 to a partition into $k$ shortest paths, to obtain another path partition with desirable properties.³

Proof. By Lemma 9, there is a set $\mathcal{P}$ of $O(3^k)$ well-colored paths starting at $a$ that cover $V(G)$, each having length at most the distance between its endpoints plus $2k$.

For each path $P \in\mathcal{P}$, consider the edges of $P$ sequentially, from $a$ towards the other endpoint of $P$. Let $xy$ be an edge of $P$ such that $x$ is closer to $a$ than $y$ on $P$. Cut $P$ at edge $xy$ if one of the following two cases occur: (i) if $x$ and $y$ have different colors in the coloring of $P$, and (ii) if $\operatorname{dist}(a,y) \le\operatorname{dist}(a,x)$, that is, the distance to $a$ fails to increase along $xy$. There are at most $k-1$ color changes in $P$, since it is well-colored. Moreover, the distance from $a$ changes by at most 1 along each edge. An edge on which this distance stays constant contributes 1 to the length excess, and an edge on which it decreases contributes 2, thus there are at most $2k$ such edges. Hence, $P$ is cut at most $3k-1$ times, producing at most $3k$ subpaths. Each subpath is monochromatic, as we have cut it along all edges whose endpoints have different colors. The distance from $a$ strictly increases along each subpath, so each piece meets every distance layer at most once. Repeating this procedure for every path in $\mathcal{P}$, let $\mathcal{S}$ be the family of all obtained subpaths. We have $|\mathcal{S}| = O(k3^k)$, and $\mathcal{S}$ covers $V(G)$ (but may not be a partition). Since each base path is shortest and hence induced, a monochromatic subpath is necessarily a shortest path.

It remains to remove overlaps between the members of $\mathcal{S}$. Since all paths in $\mathcal{S}$ are monochromatic and the base paths are pairwise vertex-disjoint, only subpaths of the same base path may overlap. Fix such a base path $B$. The members of $\mathcal{S}$ contained in $B$ are subpaths of $B$ that together cover $V(B)$, but may overlap because they come from different paths supplied by Lemma 9. Consider two such overlapping subpaths $P$ and $Q$. If one of them is included in the other, say $V(P) \subseteq V(Q)$, remove $P$ from $\mathcal{S}$. Otherwise, remove $V(P) \cap V(Q)$ from, say, $P$: this simply shortens $P$. Repeat this until no overlapping paths remain; at the end, we obtain the desired partition of size $O(k3^k)$.

The next lemma shows how to use a path partition as the one from Lemma 10 and a tree decomposition to obtain a path decomposition.

Proof. Let $\mathcal{P}$ be the given path partition of $V(G)$ and call $f(N)$ the maximum possible pathwidth of a graph partitioned into $N$ paths satisfying the hypotheses of the lemma (treewidth at most $w$ and layering condition). We proceed by induction on $N$.

Suppose first that $N \le4w+5$. This means that each layer of the considered layering $\lambda$ is of size at most $4w+5$. Let $\alpha$ be the maximum integer such that $\lambda^{-1}(\alpha) \ne\varnothing$, and define for $i \le\alpha-1$ the bag $B_i = \lambda^{-1}(i) \cup\lambda^{-1}(i+1)$. The decomposition $B_0,B_1,\ldots,B_{\alpha-1}$ is a path decomposition of $G$, since any edge of $G$ has its endpoints in the same layer of $\lambda$, or in two consecutive ones. Thus, $f(N) \le8w+9$.

Suppose now that $N > 4w+5$, and let $(T,\mathcal{B})$ be a tree decomposition of $G$ of width at most $w$. For each path $P_i$ of $\mathcal{P}$, we define $T_i$ as the subgraph of $T$ containing all nodes whose bags contain vertices of $P_i$. Let $\mathcal{T} = \{T_i \mid1 \le i \le N\}$. Since $P_i$ is connected, $T_i$ is connected as well. Select, for each $P_i$, a node $x_i$ in $T_i$. Assign to any node $y$ the weight $w(y) = |\{i \mid x_i = y\}|$. The total weight of $T$ is $N$. Consider a weighted centroid $c_T$ of $T$, that is, a node of $T$ such that each component of $T-c_T$ has weight at most $\frac{N}{2}$. Call one of these components $C$. If some subtree $T_i$ intersects $C$, since $T_i$ is connected, it is either entirely included in $C$, or $c_T$ is a node of $T_i$. Call $G_C$ the subgraph of $G$ induced by the vertex set $\left(\bigcup_{x\in V(C)} B_x\right) \setminus B_{c_T}$. Since $\mathcal{P}$ is a partition, at most $w+1$ of the subtrees of $T$ contain $c_T$ (thus, at most $w+1$ paths of $\mathcal{P}$ can intersect $B_{c_T}$). Moreover, since the weight of $C$ is at most $\frac{N}{2}$, at most $\frac{N}{2}$ subtrees of $T$ are entirely contained in $C$ (they correspond to at most $\frac{N}{2}$ paths of $\mathcal{P}$). Thus, there are at most $\frac{N}{2}+w+1$ paths of $\mathcal{P}$ that intersect $G_C$. We consider the collection $\mathcal{P}'$ of paths obtained from the intersection of the paths of $\mathcal{P}$ with $V(G_C)$. Note that a path of $\mathcal{P}$, if it intersects $B_{c_T}$, may correspond to several paths in $\mathcal{P}'$. However, each vertex of $B_{c_T}$ may only increase the number of paths in $\mathcal{P}'$ by 1. Thus, $|\mathcal{P}'|=N'\leq\frac{N}{2}+2w+2$. The paths in $\mathcal{P}'$ also meet each layer of $\lambda$ (when restricted to $G_C$) at most once, and $\lambda$ is still a layering of $G_C$. Because $N>4w+4$, $N'<N$, and we can consider by induction a path decomposition of $G_C$ of width at most $f(N')\leq f\left(\frac{N}{2}+2w+2\right)$.

We do this for each component of $T-c_T$. We order these components arbitrarily and concatenate the path decompositions following this ordering. Then, we add to each bag, the vertices of $B_{c_T}$. It is clear that this forms a valid path decomposition of $G$, of width at most

Apply this recursive identity $d=\lceil\log_2(N+1)\rceil$ times to get

which gives $f(N)=O(w\log(N+1))$, by using that $f(N)\leq8w+9$ when $N\leq4w+5$.

Proof. Without loss of generality, consider $G$ to be connected. Let $P_1,\ldots,P_k$ be the shortest paths covering the vertices of $G$. Replace each vertex $v$ by a clique $F_v=\{(v,i):v\in V(P_i)\}$ and each edge $uv$ by all edges between $F_u$ and $F_v$. Call the obtained graph $H$. Notice that the paths $P_1,\ldots,P_k$ now partition $V(H)$ and remain shortest paths in $H$. Furthermore, choosing one vertex in each of the created cliques gives an induced copy of $G$ in $H$, so $\operatorname{pw}(G)\leq\operatorname{pw}(H)$.

By Corollary 6, $\operatorname{tw}(H)=O(k^2)$. Lemma 10 applied to $\mathcal{P}=\{P_1,\ldots,P_k\}$ gives a partition into $N=O(k^3)$ paths containing at most one vertex of each distance layer from a fixed root. The distance from that root is a layering of $H$. Since $\log(N+1)=O(k)$, Lemma 11 yields $\operatorname{pw}(G)\leq\operatorname{pw}(H)=O(k^3)$.

:::

Improving the pathwidth upper bound when covering the edges

We will use the polynomial pathwidth-modulator of Baste et al. [4] together with the results in § 3 to improve the $O(k^4)$ upper bound for pathwidth from Baste et al. [4] when the graph is edge-covered by $k$ shortest paths. The results of this section do not apply to quasi-shortest paths. We restate the structural result at the core of the work in [4].

To prove the results in this section, we start from a tree decomposition $(T,\mathcal{B})$ of our input graph $G$ given by Corollary 6 or Corollary 8, and transform it using Theorem 13 and Lemmas 15 and 17 so that the obtained tree $T$ has bounded pathwidth. Then, we use Lemma 14 below that gives a bound on the pathwidth of $G$ with respect to the pathwidth of $T$. Note that this lemma applies to semi-tree decompositions, a generalization of tree decompositions defined in [9]. In particular, any tree decomposition is a semi-tree decomposition.

A complete binary tree of height $h$ is a rooted tree in which every non-leaf vertex has two children and every leaf is at distance $h$ from the root.

Proof. A tree $T$ with $q$ leaves cannot contain a binary tree of height $\lfloor\log_2 q\rfloor+1$ as a minor. By contraposition of Lemma 15, the pathwidth of $T$ is then at most $\lfloor\log_2 q\rfloor+1$.

Proof. Each path $P$ in $T-T_0$, is connected to $T_0$ by an edge, which can originate from an internal vertex of $P$ or from an endpoint of $P$. Since $T$ is subcubic, at most two such paths are connected to each leaf of $T_0$. Denote by $T'$ the subtree of $T$ obtained from $T_0$ by adding all paths of $T-T_0$ connected by an edge to a leaf of $T_0$. Notice that $T'$ has at most $4q$ leaves. By Corollary 16, $\operatorname{pw}(T') \le\lfloor\log_2(4q)\rfloor+1=\lfloor\log_2 q\rfloor+3$.

Consider a path decomposition $(T^*,\mathcal{B}^*)$ of $T'$ of width at most $\lfloor\log_2 q\rfloor+3$. We show how to transform it into one for $T$ by increasing the bag size by at most 2. To do so, consider the paths of $T-T_0$ connected to internal vertices of $T_0/T'$. Since $T$ is subcubic, at most one path $P_v$ of $T-T_0$ is connected to each internal vertex $v$ of $T_0/T'$. Consider the natural path decomposition of width at most 1 of $P_v$. Consider any bag $B$ of $(T^*,\mathcal{B}^*)$ containing $v$. Make a copy of $B$ and insert, between the two copies of $B$, the sequence of bags of the path decomposition of $P_v$, where we add to each bag, the vertices of $B$. Repeating this for every internal vertex of $T_0$ that has an edge to some path in $T-T_0$, we obtain a path decomposition of $T$ of width at most $\lfloor\log_2 q\rfloor+5$, as claimed.

Proof. Take a subcubic tree decomposition $\mathcal{T}=(T,\mathcal{B})$ of $G$ (for instance a classic nice tree decomposition, see [8]) of width $w$, that is, where $T$ is subcubic. For each vertex $x\in X$, fix a bag $B_x$ of $\mathcal{B}$ containing $x$. Define $T_0$ as the inclusion-wise minimal subtree of $T$ containing $B_x$ for all $x\in X$. By minimality, $T_0$ has at most $r$ leaves. Notice that $T-T_0$ is a forest. We call a connected component of $T-T_0$ a hanging subtree. $T$ can thus be decomposed into a set of hanging subtrees attached to $T_0$. Let $T'$ be one of those hanging subtrees, call $\alpha$ the node of $T_0$ connected to $T'$, and call $B_\alpha$ its corresponding bag. Denote by $V'$ the set of vertices of $G$ that are present in bags corresponding to nodes of $T'$ except vertices of $X$. Since $\operatorname{pw}(G-X)=p$, we have that $\operatorname{pw}(G[V'])\le p$. By considering a path decomposition of $G[V']$ and adding vertices of $B_\alpha$ to all bags of this decomposition, we get a path decomposition of $G[V' \cup B_\alpha]$ of width at most $p+w+1$. Replace $T'$ by the path underlying this path decomposition, and attach its first node to $\alpha$. Since $B_\alpha$ is contained in every bag of the path decomposition, tree decomposition properties are preserved across the attachment. Repeat this for each component of $T-T_0$, and call the resulting tree $\overline{T}$. This tree decomposition has now width at most $w+p+1$ with $\overline{T}$ being subcubic, and $\overline{T}-T_0$ is a forest of paths. Thus, we have that $\operatorname{pw}(\overline{T}) \le\lfloor\log_2 r\rfloor+5$ by Lemma 17. We finally use Lemma 14 to get that $\operatorname{pw}(G) \le(w+p+2)(\operatorname{pw}(\overline{T})+1)-1$, which yields the claim. ◀

Proof. We may assume without loss of generality that $G$ is connected and has at least one edge. Let $P_1,\ldots,P_k$ be the covering paths. By Theorem 13, for each $i$ with $1 \le i \le k$, there is a set $X_i$ of at most $720k^3+4k$ vertices such that every component of $G-X_i$ meeting $P_i$ has pathwidth at most $6k$.

Let $X=\bigcup_i X_i$. Then $|X|\le720k^4+4k^2\le724k^4$. Every component $K$ of $G-X$ contains a vertex of some $P_i$, because the paths cover all edges and there are no isolated vertices. Since $X_i\subseteq X$, the component $K$ lies in a component of $G-X_i$ meeting $P_i$. Hence, we have $\operatorname{pw}(G-X)\le6k$.

We apply Lemma 18: the bound on $|X|$ gives $\lfloor\log_2|X|\rfloor\le\lfloor4\log_2 k\rfloor+10$ and proves the sought inequality. Note that if the paths cover the edges, they also cover the vertices (we disregard isolated vertices as $G$ was assumed to be connected with at least one edge). We may therefore apply the above upper bound with $w=\operatorname{tw}(G)$. By Corollary 6, $\operatorname{tw}(G)\le441k^2+90k$, and we obtain $\operatorname{pw}(G)=O(k^2\log k)$. For $H$-minor-free graphs, we have $\operatorname{tw}(G)=O_H(k)$ by Corollary 8 and thus, $\operatorname{pw}(G)=O_H(k\log k)$. ◀

A superlinear lower bound for edge-covering by shortest paths

We now show that existing constructions provide a new superlinear lower bound for the treewidth of graphs coverable with $k$ shortest paths, answering a question of Baste et al. [4]. Our construction is inspired by the one in [12 Theorem 8].

Proof. There exist arbitrarily large cubic bipartite Ramanujan graphs (a Ramanujan graph is a regular graph with specific spectral properties) with girth $g=\Theta(\log n)$ [20 Theorem 5.4]. Ramanujan graphs are expanders and thus have linear treewidth (because expanders do not have sublinear separators [34]).

Every bipartite cubic graph can be 3-edge-colored (König’s Line Coloring Theorem). Hence, the edges can be partitioned into three matchings $M_1,M_2,M_3$. Together, two of them form a collection of disjoint cycles (because each vertex has two incident edges from them) with $n$ edges in total. Consider one of these cycles $C$ in $M_1\cup M_2$ or $M_1\cup M_3$ of length $q\ge g=\Omega(\log n)$. $E(C)$ can be covered by $O(q/g)=O(1/\log n)$ edge-disjoint paths, each of length less than $g/2$. These paths are automatically shortest paths, because a shortcut would imply the existence of a cycle of length less than the girth, which is impossible. Overall, we have $\Theta(n/\log n)$ shortest paths covering the edges of $M_1\cup M_2$, and the same for $M_1\cup M_3$. Hence, taking the union of all these shortest paths covering $M_1 \cup M_2$ and $M_1 \cup M_3$, we have $k = \Theta(n/\log n)$ shortest paths covering all edges of the graph. Hence, $k \log k = \Theta(n)$, and the treewidth of $G$ is $\Omega(n)$, which is thus $\Omega(k \log k)$.

Small quasi-shortest path covers can have unbounded pathwidth

We now show that when $\alpha> 1$, pathwidth cannot be bounded in terms of $k$ when the graph is covered by $(\alpha,\beta)$-quasi-shortest paths, even for $k = 2$ and $\beta= 0$.

Proof. Fix $\alpha> 1$. For each $h \ge0$, we construct a connected graph $G_h$ edge-covered by two $(\alpha,0)$-quasi-shortest paths $P_h,Q_h$ of equal length with a common final endpoint.

For $h = 0$, take a single vertex and paths that consist of that vertex. Suppose $G_{h-1}$ has been constructed, and its two paths have length $d$. Take two disjoint copies $A$, $B$ of $G_{h-1}$ and a new vertex $z$. Choose $l \ge2$ as the smallest integer satisfying the first inequality below, and then choose $m \ge2$ as the smallest integer satisfying the second:

Join the corresponding path endpoints according to Figure 1 by new paths of length $l$ or $m$ to obtain

Let $G_h = P_h \cup Q_h$. Both $P_h$ and $Q_h$ have length $2d + l + m$ and final endpoint $z$.

We first prove quasi-shortness of $P_h$ and $Q_h$. For any two distinct vertices $x,y$ lying on both $P_h$ and $Q_h$, we claim that their distance along these paths differs by a factor of at most $\alpha$. If $x,y$ belong to the same copy $A$ or $B$, this follows from induction. If they belong to $A$ and $B$, both distances lie in $[l,l+2d]$. If one is $z$ and the other belongs to $A$ or $B$, both distances lie in $[m,m+l+2d]$. (2) proves the quasi-shortness condition of the subpaths of $P_h$ or $Q_h$ with endpoints $x$ and $y$.

Now let $x,y \in V(P_h)$, and take a shortest $x$–$y$ path $R$ in $G_h$. Every excursion of $R$ outside $P_h$ is a subpath of $Q_h$ with endpoints common to both covering paths. Replace each excursion by the corresponding subpath of $P_h$ that is at most by a factor $\alpha$ longer because of the preceding paragraph. The resulting walk is contained in $P_h$ and has length at most $\alpha|R|$ and therefore $\operatorname{dist}_{P_h}(x,y) \le\alpha\cdot\operatorname{dist}_{G_h}(x,y)$. Thus $P_h$ is $(\alpha,0)$-quasi-shortest and the same argument applies to $Q_h$. Finally, deleting the two length-$l$ connecting paths, but retaining their endpoints, at every recursive level, leaves a subdivision of the complete binary tree of height $h$, rooted at the common final endpoint. The case $h=0$ is a single vertex, and at each step the two length-$m$ connecting paths join the new root $z$ to the roots of the subdivisions in $A$ and $B$. According to [7 Theorem 67], the complete binary tree of height $h$ has pathwidth $\lceil h/2\rceil$. Thus, $G_h$ contains the complete binary tree of height $h$ as a minor, and since pathwidth is minor-monotone, taking $h=2w$ gives us the required graph $G_h$ with pathwidth at least $w$. By our choices of $l$ and $m$, both are in $O_\alpha(d)$, and therefore $d$ grows geometrically with every recursive construction, implying that $G_h$ has order $2^{O_\alpha(w)}$.

Exponential size is optimal up to the constant in the exponent: by Theorem 5, every graph covered by two quasi-shortest paths has constant treewidth. Since every $n$-vertex graph of treewidth $t>0$ has pathwidth $O(t\log n)$ [7], pathwidth $w$ implies $n=2^{\Omega_\alpha(w)}$.

XP recognition for quasi-shortest path/walk covers

Counting Monadic Second-Order (CMSO) logic refers to Monadic Second-Order (MSO) logic augmented with fixed modular-cardinality predicates (that is, checking whether a given set has size $a$ modulo $b$, for fixed values $a,b$). When considering graphs as inputs, CMSO$_1$ quantifies over vertex sets, while CMSO$_2$ also quantifies over edge sets. It can express paths, incidence, and connectivity, but cannot compare the cardinalities of two quantified sets. We recall the precise CMSO$_2$ fragment of Dreier, Ganian, and Hamm [24 Section 3.3 and Definition 2] that we will use. To do so, we fix nonnegative integer vertex and edge weight symbols $w_i$ (given as inputs along with the graph).

A linear weight term has the form $a+\sum_{i,j}a_{ij}w_i(X_j)$, where $w_i(X)=\sum_{x\in X}w_i(x)$, and the terms $a$ and $a_{ij}$ are constants called coefficients. A coefficient is nonnegative if $a$ and all $a_{ij}$ are nonnegative real numbers, and natural if they are all natural numbers, including zero. The logic CMSO[$\preceq$] extends classical CMSO [22] by allowing atomic comparisons between weight terms.

A block formula has the form $\forall\overline{Y}\ \phi(\overline{X},\overline{Y})$, where $\phi$ is a CMSO[$\preceq$] formula containing only nonnegative weight terms. All but at most one exceptional weight term depend only on the outer variables $\overline{X}$. This exceptional term, if present, may also depend on $\overline{Y}$, but it occurs only on one side of a single comparison. Blocked CMSO, denoted $\forall$CMSO, is the closure of block formulas under conjunction, disjunction, and existential first- and second-order quantification. For the sake of readability, we will slightly abuse notation when quantifiers and weight functions are applied to single variables. In particular, we will write $\forall x$ instead of $\forall x'\in\{x\}$, and $w(x)$ instead of $w(\{x\})$.

A $\forall$CMSO query pairs a constraint using natural weight comparisons with an integral linear optimization target. An assignment for a query is a set of values for the free variables involved in it, and it is satisfying if the query constraints hold when using the assigned values. Every query used here is a feasibility query with the constant-zero target; it returns either a satisfying assignment or a report that none exists.

Proof. Let $\alpha=\frac{p}{q}$ and $\beta=\frac{r}{s}$ with nonnegative integers $p,q,r,s$. Let $\operatorname{Path}(P)$ be the standard MSO$_2$ predicate that $P$ is the edge set of a nonempty positive-length simple path. It asks that $P$ forms a connected subgraph, no vertex of $G$ is incident to three edges of $P$, and $P$ is acyclic (every subset of $P$ has a leaf), see [23 Chapter 7]. Moreover, let RootedPath$(R,x,y)$ say that $R$ is the edge set of an $x$–$y$ path (same as Path$(R)$ but $x,y$ are distinct and have degree 1 when considering only edges of $R$), AllEdges$(F)$ say that $F=E(G)$, and Complement$(S,F,R)$ say that $S=F\setminus R$. These are all ordinary MSO$_2$ predicates.

Let SubPath$(Q,P,x,y)$ be the predicate saying that $Q\subseteq P$ is a subpath of $P$ with endpoints $x,y$. It is expressed as RootedPath$(Q,x,y)$ together with the fact that $Q\subseteq P$. Hence, SubPath$(Q,P,x,y)$ is MSO$_2$.

For a subpath $Q$ with endpoints $x$ and $y$, quasi-shortness requires $|Q|\leq\alpha|R|+\beta=\frac{p}{q}|R|+\frac{r}{s}$ for any shortest $x$–$y$ path $R$ (and thus, for any $x$–$y$ path $R$), that is, $sq|Q|\leq sp|R|+rq$. Blocked CMSO does not allow this comparison because both sides depend on universally quantified sets $Q$ and $R$. However, by using $S=E(G)\setminus R=F\setminus R$, we get $|R|=|F|-|S|$, and so the above condition can be reformulated as

which is allowed in Blocked CMSO because only $Q$ and $S$ are universally quantified (since $F=E(G)$ is fixed), and these universally quantified terms appear only on one side of the comparison. This is a crucial point. Formally, let $\varphi_{\alpha,\beta}(P)$ be the following query:

Requiring (3) for every $x$–$y$ path $R$ and subpath $Q$ is equivalent to $|Q|\leq\alpha\cdot\operatorname{dist}_{G}(x,y)+\beta$. Universally quantifying $Q,x,y$ therefore gives exactly Definition 1.

In $\varphi_{\alpha,\beta}(P)$, $P$ and $F$ are fixed outside the universal block. Hence $sp|F|+rq$ is an outer term, while $sq|Q|+sp|S|$ is the unique term depending on block variables and occurs on only one side of one comparison. Both are nonnegative natural weight terms, and all predicates are pure MSO$_2$. Thus the formula belongs to $\forall$CMSO$_2$.

Proof. For every label $i$, the vertex set $X_i$ and edge set $P_i$ encode one path. An ordinary MSO$_2$ predicate distinguishes two cases. If $P_i$ is empty, then $X_i$ is empty or a singleton. If $P_i$ is nonempty, then $X_i$ is exactly the set of vertices incident with $P_i$, and $\varphi_{\alpha,\beta}(P_i)$ holds. Finally, require $X_1\cup\cdots\cup X_k=V(G)$. Empty labels allow fewer than $k$ paths. The obtained formula is closed under the required conjunctions, disjunctions, and existential quantifiers, and each of the $k$ copies has constant size for fixed $\alpha,\beta$.

We use the following XP algorithmic meta-theorem to get the main result of this section.

We apply Theorem 24 to obtain the following.

Proof. Let $a = 2\alpha+ \beta+ 1$ and $w = 49a^2k^2 + 30ak$. Apply the single-exponential $2$-approximation for treewidth due to Korhonen [35]. It either correctly reports $\operatorname{tw}(G) > w$, in which case we answer no due to Theorem 5, or returns a tree decomposition of width at most $w' = 2w + 1$. The standard nice tree decomposition conversion transforms it into a nice tree decomposition of at most $4n$ nodes and width at most $w'$ in time $O(wn)$ [8 Lemma 6].

By Lemma 23, the formula $\hat{\psi}_{k,\alpha,\beta}$ has size $O(k)$ and its assignments are exactly the required quasi-shortest path covers. Evaluate the corresponding feasibility query exactly on the width-$w'$ decomposition using Theorem 24. If it is infeasible, answer no. Otherwise, return the paths encoded by the free sets $(X_i,P_i)$.

With $\alpha= \frac{p}{q}$ and $\beta= \frac{r}{s}$, the weight bound from Theorem 24 is the constant $M = \max\{sq,sp,rq\}$. Exact evaluation therefore takes time $(M + (w+1)n)^{h(O(k),2w+1)}$.

The treewidth approximation takes $2^{O(w)}n$ time, the nice tree decomposition conversion takes $O(wn)$ time, and writing the $k$ paths takes $O(kn)$ time. Since $w = O_{\alpha,\beta}(k^2)$ by Theorem 5 and $M$ is constant for fixed $\alpha,\beta$, these costs have the claimed form, by aggregating all parameter-only factors into the exponent $f_{\alpha,\beta}$. ◀

We next prove that the XP algorithm from Theorem 25 can be extended to walks, by a reduction to a slightly constrained version of $(\alpha,\beta)$-Quasi-Shortest Path Cover.

(2) is satisfied. Since $W$ did not contain two consecutive occurrences of the same vertex, (1) is satisfied. Every clique of $C$ is intersected since the walks cover all vertices of $G$. Finally, for vertices $x \in C_u$, $y \in C_v$ with $u \ne v$, we have $\operatorname{dist}_H(x,y) = \operatorname{dist}_G(u,v)$, so, a subpath between $x$ and $y$ is $(\alpha,\beta)$-quasi-shortest since the walks are as well. If $x,y$ are in the same clique $C_v$, $\operatorname{dist}_H(x,y) = 1$, and as we proved (2), it has at most $b - 1 \le\beta\le\alpha\cdot\operatorname{dist}_H(x,y) + \beta$ edges, so it is also $(\alpha,\beta)$-quasi-shortest.

Conversely, let $P$ be a set of $(\alpha,\beta)$-quasi-shortest (simple) paths of $H$ satisfying all three conditions. In each path, we replace each vertex of say $C_v$ by $v$, to obtain a collection of walks of $G$ of the same size as $P$. Condition (2) guarantees that a subpath with at least $b$ edges in any path of $P$ is projected into a subwalk in $G$ with distinct endpoints, hence subwalks with the same starting and ending vertex are $(\alpha,\beta)$-quasi-shortest. For vertices $x \in C_u$, $y \in C_v$ with $u \ne v$, we have $\operatorname{dist}_H(x,y) = \operatorname{dist}_G(u,v)$, so, subwalks with distinct endpoints are $(\alpha,\beta)$-quasi-shortest since the paths of $P$ do as well. Since every clique in $C$ is intersected by a path of $P$, every vertex of $G$ is covered by one of the walks.

For fixed $\beta$, the three additional conditions are ordinary MSO$_2$ predicates. Combine them with the path formulas of Lemma 22, treating empty and singleton paths as in Lemma 23. This gives a $\forall$CMSO$_2$ query of size $O(k)$ on the colored graph $H$. As in the proof of Theorem 25, by Theorem 7 and running Korhonen’s treewidth 2-approximation [35], we may reject if the treewidth is too large for a yes-instance, or obtain a tree decomposition of $G$ of width $w = O_{\alpha,\beta}(k^2)$. Replacing each bag $B$ by $\bigcup_{u \in B} C_u$ gives a decomposition of $H$ of width $O(bw)$. Moreover, $|V(H)| = bn$. Adapting the proof of Theorem 25, Exact Blocked-CMSO evaluation therefore has the stated XP running time. ◀

Conclusion

For graphs $G$ covered by $k$ exact shortest paths, our results establish that $\operatorname{tw}(G) = O(k^2)$ and $\operatorname{pw}(G) = O(k^3)$. For covering the edges, the treewidth upper bound remains, and we obtained $\operatorname{pw}(G) = O(k^2 \log k)$. For all these cases, we provide an $\Omega(k \log k)$ lower bound for infinitely many graphs, showing that a linear upper bound is impossible (negatively answering a question from Baste et al. [4]).

The polynomial pathwidth upper bound for the vertex-covering case answers the most intriguing formerly open question in the area, since previously, only an exponential upper bound was known. The other bounds improve those from the literature.

The gaps between the lower and upper bounds come from the quadratic treewidth upper bound, and the additional cost from the pathwidth-modulator and the well-colored path partition, respectively. Note that improving the $\Omega(k \log k)$ lower bound in treewidth would also improve the treewidth lower bound with respect to linear growth from [12 Theorem 8].

The main open question is to obtain tight bounds for the above problems.

▶ Open Problem 27. What are the maximum treewidth and pathwidth of a graph covered by $k$ shortest paths? Is $O(k^2)$ optimal, or even $O(k \log k)$? Do the optimal bounds for vertices and edges differ? What about $H$-minor-free graphs?

We introduced the problems $(\alpha,\beta)$-Quasi-Shortest Path/Walk Cover, which can arguably better model real-world applications. Vertex-covering by quasi-shortest paths/walks also implies quadratic treewidth, enabling XP recognition and construction algorithms. The use of the Blocked-CMSO-based meta-theorem yields XP bounds whose exponents depend on the formula and treewidth, but explicit exponents and FPT algorithms remain open.

Note that this is already open for Shortest Path Cover ($\alpha= 1$ and $\beta= 0$) [26, 28]. The related Shortest Path Partition problem is W[1]-hard for pathwidth [15] (but the solution size parameterization remains open). The edge-disjoint version of Shortest Path Cover for oriented graphs is W[1]-hard for solution size [28].

Disclosure of generative-AI assistance.

We used generative AI (GPT 5 and 6) for initial language drafting, literature search and review of our candidate proofs. In particular, it assisted with examining the applicability of cited results, suggesting alternative arguments, and checking inequalities and boundary cases. These were treated as suggestions and carefully verified by us. The core ideas, proofs and final manuscript are due to the authors: we entirely reviewed, rewrote and verified proofs, citations, final text and retain full responsibility for the content.