A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by $k$ Shortest Paths

In this work, we consider undirected finite simple graphs, without loops. For a graph $G$, we denote with $V(G)$ its set of vertices, and $E(G)$ its set of edges. For any set $X\subseteq V(G)$ of vertices, $G[X]$ denotes the subgraph of $G$ induced by $X$, that is, the vertex set of $G[X]$ is $X$, and $G[X]$ contains all edges of $G$ with both end-points in $X$. $G-X$ denotes the subgraph of $G$ induced by $V(G)\setminus X$. For simplicity, for every vertex $x$, we let $G-x$ denote the graph $G-\{x\}$. For all subsets $X,Y\subseteq V(G)$ of vertices, we denote $E_G(X,Y):=\{xy\in E(G):x\in X\setminus Y,y\in Y\setminus X\}$. Let $G^{\prime }$ be a graph, whose vertex set potentially intersects the one of $G$. The union of $G$ and $G^{\prime }$ is the graph $G\cup G^{\prime }:=(V(G)\cup V(G^{\prime }),E(G)\cup E(G^{\prime }))$.

For every $v\in V(G)$, we let $N_G(v)$ (or simply $N(v)$ when the context is clear) denote the set of neighbors of $v$. Similarly, for every subset $X\subseteq V(G)$ of vertices, we let $N_G(X)$ (or simply $N(X)$) denote the set of vertices in $V(G)\setminus X$ having at least one neighbor in $X$. If $U\subseteq V(G)$, we similarly let $N_U(X)$ denote the set of vertices in $U\setminus X$ having at least one neighbor in $X$.

For every three subsets $X,A,B\subseteq V(G)$, we say that $X$ separates $A$ from $B$ in $G$ if no component of $G-X$ contains both a vertex from $A$ and a vertex from $B$.

A path $P$ is a sequence of pairwise distinct vertices $v_1,\mathrm{\dots },v_k$ such that for each , $v_i{v}_{i+1}\in E(G)$. Note that by definition, a path is a sequence of vertices; however, by abuse of notations, we will often identify a path $P=v_1,\mathrm{\dots },v_k$ of $G$ and its corresponding subgraph in $G$ (that is, the graph with vertices $v_1,\mathrm{\dots },v_k$ and edges $v_i{v}_{i+1}$ for each $i$ such that ). A path connecting two vertices $v_1=x$ and $v_k=y$ will also be called an $xy$-path. We call the vertices $v_1$ and $v_k$ the endvertices of $P$, while all its other vertices are its internal vertices. The length of $P$ corresponds to its number of edges. For each $i\le j$, we let $P[v_i,v_j]$ denote the subpath $v_i,v_{i+1},\mathrm{\dots },v_j$ of $P$, and we let $P^{-1}$ denote the path $v_k,\mathrm{\dots },v_1$. For every two paths $P=v_1,\mathrm{\dots },v_p$ and $Q=w_1,\mathrm{\dots },w_q$ such that $v_p=w_1$, and such that $P-v_p$ is disjoint from $Q-w_1$, we define the path $P\cdot Q:=v_1,\mathrm{\dots },v_p=w_1,\mathrm{\dots },w_q$. If $P=v_1,\mathrm{\dots },v_k$ is a path, for every , we say that $v_i$ is before $v_j$ on $P$, and that $v_j$ is after $v_i$ on $P$. A path $P$ is vertical with respect to a vertex $u$, if for every $i\in \mathbb{N}$, $P$ has at most one vertex at distance $i$ from $u$ in $G$. Note that every path vertical with respect to some vertex $u$ is a shortest path, and that every shortest path starting from $u$ is vertical with respect to $u$.

Let $G$ be a graph and $H_1,\mathrm{\dots },H_k$ be subgraphs of $G$. We say that the graphs $H_1,\mathrm{\dots },H_k$ edge-cover $G$ if $E(G)={\bigcup }_{i=1}^{k}E(H_i)$. Similarly, we say that $H_1,\mathrm{\dots },H_k$ vertex-cover $G$ if $V(G)={\bigcup }_{i=1}^{k}V(H_i)$.

We let $d_G(\cdot ,\cdot )$ (or simply $d(\cdot ,\cdot )$ when the context is clear) denote the shortest-path metric of a graph $G$. Recall that a graph $H$ is an isometric subgraph of $G$ if $H$ is a subgraph of $G$ such that every shortest path in $H$ is also a shortest path in $G$. For every vertex $v$ of a graph $G$, we let $\mathrm{ecc}(v):=\max \{d_G(u,v):u\in V(G)\}\in \mathbb{N}\cup \{\mathrm{\infty }\}$ denote the eccentricity of $v$.

Let $(X,\le )$ be a partially ordered set. For every two disjoint subsets $A,B\subseteq X$, we write if for every $(a,b)\in A\times B$. Moreover, for every $x\in X$ and every $A\subseteq X$, we let ${A|}_{\le x}:=\{a\in A:a\le x\}$ and ${A|}_{\ge x}:=\{a\in A:a\ge x\}$. We define similarly and ${A|}_{>x}$. A chain is a sequence $(x_1,\mathrm{\dots },x_k)$ of distinct elements of $X$ such that $x_1\le x_2\le \mathrm{\cdots }\le x_k$.

A path-decomposition of a graph $G$ is a sequence $𝒫=(X_1,X_2,\mathrm{\dots },X_q)$ of vertex subsets of $G$, called bags, such that $V(G)={\bigcup }_{i=1}^q{X}_i$, for every edge $\{x,y\}\in E$ there is at least one bag containing both endpoints, and for every vertex $x\in V$, the bags containing $x$ form a continuous subsequence of $𝒫$. The width of $𝒫$ is $\max \{|X_i|-1:1\le i\le q\}$, and the pathwidth $\mathrm{pw}(G)$ of $G$ is the smallest width of a decomposition, among all path-decomposition of $G$. The bags $X_1,X_q$ are called the extremities of $𝒫$.

Let $G$ be a graph and denote a total ordering on $V(G)$. The vertex-separation number of is the value . The vertex separation number of $G$ is the minimum over the vertex separation numbers of , for all possible linear orderings of $G$.

A layering of a graph $G$ is a partition of its vertices into a sequence $(V_1,\mathrm{\dots },V_t)$ of subsets of $V(G)$ such that each graph $G[V_i]$ is an independent set, and for every $i,j\in \{1,\mathrm{\dots },t\}$ such that $|j-i|\ge 2$, we have $|E_G(V_i,V_j)|=0$.⁴⁴4Note that our definition of layering differs from the one which is commonly used in the literature, as one usually allows in a layering edges between vertices from a same layer. A $k$-layering of a graph $G$ is a partition of $V(G)$ into a sequence $(V_1,\mathrm{\dots },V_t)$ of sets such that each graph $G[V_i]$ is an independent set, and for every , we have $|E_G(V_i,V_{i+1})|\le k$. Note that in particular, it implies that $|N_{V_{i+1}}(V_i)|\le k$ and $|N_{V_i}(V_{i+1})|\le k$. The bags $V_1$ and $V_t$ are the extremities of the layering.

Let $P$ be a shortest path between two vertices $a,b$ of $G$. A path $Q$ of $G$ is parallel to $P$ in $G$ if $Q$ is a subpath of a shortest $ab$-path of $G$.

Note that this does not define a symmetric relation in general: the fact that a path $Q$ is parallel to another path $P$ does not necessarily imply that $P$ is parallel to $Q$. However, in the remainder of the proof, we will always consider the property of being parallel to the path $P_1$, which is fixed and connects vertices $a_1$ and $b_1$. In particular, the following simple observation implies that every graph which is edge-coverable by a few number of paths that are all parallel to $P_1$ has a very restrained structure.

We consider the partial order ${\le }_1$ on $V(G)$ defined by setting for every two vertices $u,v\in V(G)$, $u{\le }_{1}v$ if and only if $d_G(a_1,u)\le d_G(a_1,v)$. Note in particular that the vertex set of every path $P$ which is parallel to $P_1$, forms a chain with respect to ${\le }_1$.

Note that $P\cdot Q$ must be a shortest $ac$ path, as for each $i\ge 0$, it contains at most one vertex at distance exactly $i$ from $a_1$. In particular, it is not hard to conclude that $P\cdot Q$ is parallel to $P_1$. $◀$

The first step in the proof of Theorem 7 consists in modifying the covering family $𝒫$ in order to make it reduced (see definition below). The intuition behind this step is that our proof of Theorem 7 works particularly well when all paths in $𝒫$ intersect $P_1$. Informally, the reduction operation consists in making $𝒫$ contain as much paths that intersect $P_1$ as possible. This step will turn out to be useful at the very end of our proof (see the proof of Lemma 15).

A shortest path $Q$ of $G$ is called a reducing path if

• $\mathrm{■}$

  $Q$ is disjoint from $P_1$, and admits a subpath $P$ parallel to $P_1$, that connects two vertices $u,v$, such that ,

• $\mathrm{■}$

  there exists a shortest path $R$ in $G$ from $u$ to $v$ that intersects $P_1$.

Figure 2 depicts a reducing path. If a family $𝒬$ of shortest paths has no reducing path, then we say that $𝒬$ is reduced.

Assume that $𝒬$ is not reduced, and let $Q$ be a reducing path in $𝒬$. We also let $P$ be a subpath of $Q$ with endvertices $u,v$ such that , and $R$ be a shortest path in $G$ from $u$ to $v$ intersecting $P_1$. We let $R_1,R_2$ denote two shortest paths respectively from $a_1$ to $u$ and from $v$ to $b_1$. We also write $Q=Q_1\cdot Q_2\cdot Q_3$, so that $Q_2$ is the $uv$-subpath of $Q$ parallel to $P_1$ (see Figure 2). Observe now that both paths $Q^{\prime }:=Q_1\cdot R\cdot Q_3$ and $Q^{\prime \prime }:=R_1\cdot Q_2\cdot R_2$ are shortest paths in $G$ that both intersect $P_1$ and cover all the edges of $Q$. In particular, it implies that the family of paths ${𝒬}^{\prime }:=(𝒬\setminus \{Q\})\cup \{Q^{\prime },Q^{\prime \prime }\}$ covers all the edges covered by the paths of $𝒬$, and has strictly fewer paths than $𝒬$ that do not intersect $P_1$. We apply iteratively the same operation as long as the obtained family ${𝒬}^{\prime }$ is not reduced. In particular, as at each step, the number of paths of $𝒬$ which are disjoint with $P_1$ strictly decreases, then after at most $|𝒬|$ iterations, we obtain a reduced family with the desired properties. $◀$

Up to applying Proposition 9 to $𝒫$, we will assume from now on that $𝒫$ is a reduced family of at most $2k$ shortest paths of $G$ that edge-cover $G$.

We now partition the set $𝒫:=\{P_i:1\le i\le 2k\}$ into the subset ${𝒫}_1$ of the paths in $𝒫$ that intersect $P_1$, and ${𝒫}_2:=𝒫\setminus {𝒫}_1$.

For every $P\in {𝒫}_1$, we let $C_P$ denote the maximal subpath of $P$ with both endvertices $a_P,b_P$ in $V(P_1)$, so that $a_P{\le }_1{b}_P$ (up to considering $P^{-1}$ instead of $P$, we also assume that $a_P$ is before $b_P$ on $P$). Note that $C_{P_1}=P_1$, and that by definition of ${𝒫}_1$, each $C_P$ has at least one vertex, and is parallel to $P_1$. We moreover consider for every $P\in {𝒫}_1$ the two vertices $u_P,v_P$ that respectively maximize $d_G(u_P,a_P)$ and $d_G(b_P,v_P)$, such that $u_P,a_P,b_P,v_P$ appear in this order on $P$, and such that the paths $P[u_P,a_P]$ and $P[b_P,v_P]$ are parallel to $P_1$. We now let ${\tilde{C}}_P:=P[u_P,v_P]$ and $A_P,B_P$ denote the two subpaths of $P$ such that $P=A_P\cdot {\tilde{C}}_P\cdot B_P$ (see Figure 3). We stress out that in general, the path ${\tilde{C}}_P$ is not necessarily parallel to $P_1$.

We let $𝒜:=\{A_P^{-1}:P\in {𝒫}_1\}\cup \{B_P:P\in {𝒫}_1\}$ and $ℬ:=\{{\tilde{C}}_P:P\in {𝒫}_1\}$. In particular, $P_1\in ℬ$. Note that by definition, every path in $ℬ$ is the concatenation of at most $3$ paths that are parallel to $P_1$, and recall that $|𝒫|\le 2k$, hence we have $|ℬ|\le 2k$.

We say that the edges of the paths in $𝒜\cup {𝒫}_2$ are bad, and we call a vertex $v\in V(G)$ bad if it is the endvertex of a bad edge. We call every vertex which is not bad good, and we let $V_b$ and $V_g$ denote respectively the set of bad and good vertices of $G$. We moreover set $X_0:=\{a_P:P\in {𝒫}_1\}\cup \{b_P:P\in {𝒫}_1\}$ and $X_1:=\{u_P:P\in {𝒫}_1\}\cup \{v_P:P\in {𝒫}_1\}$. Note that in particular, $|X_0|\le 4k$ and that the only bad vertices that belong to $P_1$ are the vertices $a_P,b_P$ for $P\in {𝒫}_1$, hence $V(P_1)\cap V_b\subseteq X_0$.

We now consider the subgraph $G_0:={\bigcup }_{P\in ℬ}P$ of $G$. The following remark immediately follows from the definition of $ℬ$, the fact that $|{𝒫}_1|\le |𝒫|\le 2k$, and that every path in $ℬ$ is edge-covered by at most $3$ paths that are parallel to $P_1$.

Let $u$ be a good vertex. As $G$ is covered by $𝒫$, there exists some path $P\in 𝒫$ such that $u\in V(P)$. In particular, as $u$ is a good vertex, we must have $P\in {𝒫}_1$, and moreover $u$ must be a vertex of ${\tilde{C}}_P$. It implies that $u\in V(G_0)$, and thus that $V_g\subseteq V(G_0)$. The “Moreover” part follows from the fact that by definition, no bad edge can be incident to a good vertex. In particular, note that every edge from $E(G)\setminus E(G_0)$ is bad, hence $G[V_g]$ is indeed a subgraph of $G_0$. $◀$

Our goal from now on will be to prove the following lemma.

We let $X$ be given by Lemma 12. In particular, by Lemma 11, every component of $G-X$ that contains a vertex of $P_1$ induces a subgraph of $G_0$. By Section 2.2, Section 3.1 and Remark 10, $G_0$ is $6k$-layered, and thus has pathwidth at most $6k$, allowing us to conclude the proof of Theorem 7. $◀$

We will now show that, in order to prove Lemma 12, it is enough to separate $V(P_1)$ from $V_b$ in the subgraph $G_0$ of $G$. We show that Lemma 12 amounts to prove the following key lemma, that we will prove in Section 3.2.

Recall that every path of $ℬ$ is the concatenation of at most $3$ paths parallel to $P_1$. We thus consider a set ${ℬ}^{\prime }$ of size at most $3|ℬ|$ of paths parallel to $P_1$ that cover the edges of the paths from $ℬ$. We let $I$ denote the set of all pairs $(A,P)$ such that $A\in 𝒜\cup {𝒫}_2$, $P\in {ℬ}^{\prime }$, and $V(A)\cap V(P)\ne \mathrm{\varnothing }$.

We set

where the sets $X_{A,P}$ are given by Lemma 13. Note that $|𝒜\cup {𝒫}_2|\le 2|{𝒫}_1|+|{𝒫}_2|\le |{𝒫}_1|+|𝒫|\le 4k$ and $|{ℬ}^{\prime }|\le 3|ℬ|=3|{𝒫}_1|\le 6k$, thus $|I|\le 24k^2$ and $|X|\le 720k^3+4k$.

We now show that $X$ separates $V(P_1)$ from $V_b$ in $G$. Suppose, for contradiction, that there exists a path $R$ in $G-X$ connecting a vertex $v$ from $V_b$ to a vertex $u$ on $P_1$. Among those paths, choose a path $R$ with minimum length. Since $V(P_1)\cap V_b\subseteq X_0\subseteq X$, we have $v\notin V(P_1)$ and thus $R$ has length at least $1$. Also, since $R$ is a path of minimum length connecting $V_b$ to $P_1$, every vertex in $R-v$ must be good. Since every vertex in $R-v$ is good, there is no bad edge in $R$. Hence, as $𝒫$ edge-covers $G$, all the edges of $R$ must be covered by the paths from $ℬ$, implying that $R$ is also a path of $G_0$.

This implies in particular that $v\in V(G_0)\cap V_b$. Thus by definition of $G_0$ and $V_b$, there exist some paths $P\in ℬ$ and $A\in 𝒜\cup {𝒫}_2$ such that $v\in V(P)\cap V(A)$. Lemma 13 then implies that $R$ intersects $X_{A,P}\subseteq X$, giving a contradiction. $◀$

We assume first that $A=A_S^{-1}$ for some $S\in {𝒫}_1$, and claim that the case where $A=B_S$ is symmetric. We moreover assume that $A[u_S,b]$ is a subpath of $A[u_S,c]$, as depicted in Figure 6, and claim that the case where $A[u_S,c]$ is a subpath of $A[u_S,b]$ is symmetric. We show that in this case, $Q$ must be $\nearrow$-free. As $P$, and thus $Q$ are parallel to $P_1$, note that every vertex $v\in V(Q)$ satisfies $\iota (v)\in [\iota (b),\iota (c)]$. We let $A^{\prime }$ denote the subpath of $S^{-1}$ which starts at $a_S$ and contains $A$ as a subpath.

We assume for sake of contradiction that there exists some path $R$ in $G_0$ which is parallel to $P_1$ in $G$, and which connects a vertex $x\in U_Q$ to a vertex $y\in V(Q)$, with $x{\le }_{1}y$. We consider two cases according to whether $a_S{\le }_{1}x$ or not, described in Figure 6.

If $a_S{\le }_{1}x$, then by Lemma 8, the path $P_1[a_S,x]\cdot R\cdot Q[y,c]$ is parallel to $P_1$. On the other hand, recall that by definition of $u_S$, and as $c\ne u_S$ (this is because $b\ne c$ and $A[u_S,c]$ contains $b$), $A^{\prime }[a_S,c]$ cannot be parallel to $P_1$. In particular, $A^{\prime }[a_S,c]$ must be strictly longer than $P_1[a_S,x]\cdot R\cdot Q[y,c]$, implying a contradiction as $A^{\prime }$ is a shortest path in $G$.

If $a_S{>}_{1}x$, then as $x\in U_Q$, $x{>}_{1}b$. Then, the path $R\cdot Q[y,c]$ is vertical with respect to $a_1$, and thus strictly shorter than $Q$. Note in this case, the path $A^{\prime }[a_S,b]$ is also strictly longer than $P_1[a_S,x]$. It thus implies that $P_1[a_S,x]\cdot R\cdot Q[y,c]$ is strictly shorter than the path $A^{\prime }[a_S,c]$, contradicting again that $A^{\prime }$ is a shortest path in $G$. $◀$

If $Q$ is $\nearrow$-free, then we immediately conclude by choosing $Q_1$ to be the path having $b$ as a single vertex, thus we may assume that there exists some path $R$ parallel to $P_1$ connecting some vertex $x\in U_Q$ to a vertex $y\in V(Q)$ such that $x{\le }_{1}y$. We moreover choose such a path so that $x$ is maximal with respect to ${\le }_1$. We let $z$ be the unique vertex of $Q$ such that $\iota (z)=\iota (x)$, and set $Q_1:=Q[b,z],Q_2:=Q[z,c]$. By maximality of $x$, note that $Q_2$ must be $\nearrow$-free. We moreover claim that $Q_1$ is $\searrow$-free. Assume for a contradiction that it is not the case, and that there exists a shortest path $R^{\prime }$ parallel to $P_1$ connecting a vertices $y^{\prime }{\le }_1{x}^{\prime }$, with $y^{\prime }\in V(Q_1)$ and $x^{\prime }\in U_{Q_1}$ (see Figure 7). Then the path $T:=Q_1[b,y^{\prime }]\cdot R^{\prime }\cdot P_1[x^{\prime },x]\cdot R\cdot Q_2[y,c]$ is a path in $G$ from $b$ to $c$ that intersects $P_1$ and which is parallel to $P_1$. In particular, as $b,c\in V(A)$ the existence of $T$ implies that $A$ is a reducing path belonging to $𝒫$, contradicting our assumption that $𝒫$ is reduced. $◀$

The next lemma is the crucial part from the proof of Lemma 13. As its proof is slightly technical, we included it in the long version.

By Lemmas 14 and 15, there exist two subpaths $Q_1,Q_2$ of $Q$ such that $Q=Q_1\cdot Q_2$, and such that for each $i\in \{1,2\}$, $Q_i$ is either $\nearrow$-free or $\searrow$-free. In particular, by Section 3.2, there exist two sets $X_1,X_2$ of size at most $18k$ such that for each $i\in \{1,2\}$, $X_i$ separates in $G_0$ the set $V(Q_i)$ from $V(P_1)$. In particular, the set $X:=X_1\cup X_2$ then separates $V(Q)$ from $V(P_1)$. Moreover, we claim that when going through the proof of Section 3.2, one gets that $X_1$ and $X_2$ both contain a common layer $V_i$ (for $i:=\iota (c_{Q_1})=\iota (b_{Q_2})$), allowing us to slightly reduce our upper bound on $|X_1\cup X_2|$ to obtain $|X_1\cup X_2|\le 30k$ (instead of $36k$). $◀$

Assume for sake of contradiction that there exist three such vertices $a,b,c\in V(P)\cap V(Q)$. Since $b$ is an internal vertex of $P[a,c]$, . But since $c$ is an internal vertex of $Q[a,b]$, , a contradiction. $◀$

We let $P_1,P_2$ be two isometric paths that edge-cover $G$, and let $x_1,\mathrm{\dots },x_{\mathrm{\ell }}$ denote the vertices from $V(P_1)\cap V(P_2)$, such that for each , $x_i$ is before $x_j$ on $P_1$. By Lemma 17, for each , $x_i$ is also before $x_j$ on $P_2$. It thus implies that each $x_i$ separates in $G$ all vertices appearing before it in $P_1$ and $P_2$ from all vertices appearing after it in $P_1$ and $P_2$. In particular, it easily follows that $G$ is a skewer. $◀$

As explained above, observe that, up to replacing $P_2$ by $P_2^{-1}$, one of the four cases between (1), (2), (3) and (4) should occur. We thus conclude that $\mathrm{pw}(G)\le 3$ after applying according accordingly Section 4.2, Section 4.2, Section 4.2 and Section 4.2. $◀$