Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number

The reduction starts constructing $G$ by adding the following vertices: $\{g_1,g_2,g_3,g_4\}$, $\{p^{\alpha },q^{\alpha },r^{\alpha }\}$, $\{p^{\beta },q^{\beta },r^{\beta }\}$, and $\{p^{\gamma },q^{\gamma },r^{\gamma }\}$. All set-encoding gadgets and element-encoding gadgets, which we define below, are connected via these common branching vertices. These common branching vertices are denoted using grey shaded region in all the figures. Apart from the vertices in $\{q^{\alpha },q^{\beta },q^{\gamma }\}$, the reduction adds pendant vertices adjacent to each common branching vertex. In all the figures, vertices that are adjacent to a pendant vertex are highlighted by enclosed squares around them. Define an integer $M$ such that $M\in 𝒪(n^2)$ and for any $a\in [n]$, we have $0.99\cdot M^2\le M^2-2aM,M^2+2aM\le 1.01\cdot M^2$. The reduction connects $g_1$ to $g_2$ and $g_3$ to $g_4$ using a path of length $M^2$ for each connection. See Figure 1.

The reduction adds $n$ identical set-encoding gadgets denoted by ${𝒮}^1,{𝒮}^2,\mathrm{\dots },{𝒮}^n$. For any $i\in [n]$, set-encoding gadget ${𝒮}^i$ contains sets of vertices $X^i$, $Y^i$, and two auxiliary vertices $z_1^i$ and $z_2^i$. Sets $X^i$ and $Y^i$ contain $m$ vertices each. The reduction adds matching edges across $X^i$ and $Y^i$. Each of these matching edges and their endpoints corresponds to a unique set in $𝒮$. Then, the reduction replaces each of these matching edges with a simple path of length $M^2$. For each vertex in $Y^i$, the reduction adds a pendant vertex adjacent to it. It connects $z_1^i$ with every vertex in $\{z_2^i\}\cup X^i$ using a simple path of length $M^2$ for each connection.

We now specify how the vertices mentioned above are connected to common branching vertices. The reduction connects $(i)$ $g_1$ to $z_1^i$ and $z_2^i$, $(ii)$ $g_2$ to $z_1^i$, and $(iii)$ $g_4$ to every vertex in $Y^i$, using paths of length $M^2$ for each connection. It connects $g_2$ to every vertex in $Y^i$ using a path of length $M^2-1$. We remark that these are the only paths that are of length $M^2-1$. To specify the connection to the remaining common branching vertices, consider a set $S=\{(\alpha ,a^{\prime }),(\beta ,b^{\prime }),(\gamma ,c^{\prime })\}$ in $𝒮$ and the vertex $x$ corresponding to it in $X^i$. The reduction connects $x$ to all the remaining common branching vertices such that

• $\mathrm{■}$

  $\mathrm{dist}(x,p^{\alpha })=M^2+2a^{\prime }M$, $\mathrm{dist}(x,q^{\alpha })=M^2-a^{\prime }M$, and $\mathrm{dist}(x,r^{\alpha })=M^2-2a^{\prime }M$;

• $\mathrm{■}$

  $\mathrm{dist}(x,p^{\beta })=M^2+2b^{\prime }M$, $\mathrm{dist}(x,q^{\beta })=M^2-b^{\prime }M$, and $\mathrm{dist}(x,r^{\beta })=M^2-2b^{\prime }M$; and

• $\mathrm{■}$

  $\mathrm{dist}(x,p^{\gamma })=M^2+2c^{\prime }M$, $\mathrm{dist}(x,q^{\gamma })=M^2-c^{\prime }M$, and $\mathrm{dist}(x,r^{\gamma })=M^2-2c^{\prime }M$.

See Figure 2 for an illustration.

Now, consider the vertex on the path connecting $x$ to $p^{\alpha }$ which is adjacent to $x$. We denote this vertex by $x_{p^{\alpha }}$. The reduction connects $x_{p^{\alpha }}$ with $g_2$ and $g_3$ using the paths of length $M^2$ each. It repeats this process to add vertices $x_{q^{\alpha }}$, $x_{r^{\alpha }}$, $x_{p^{\beta }}$, $x_{q^{\beta }}$, $x_{r^{\beta }}$, $x_{p^{\gamma }}$, $x_{q^{\gamma }}$, and $x_{r^{\gamma }}$, and their connection to $g_2$ and $g_3$.

Consider an element $(\alpha ,a)$ in $𝒰$. The reduction adds three vertices $u_a^{\alpha },v_a^{\alpha }$ and $w_a^{\alpha }$. It adds a pendant vertex adjacent to $u_a^{\alpha }$ and another pendant vertex adjacent to $w_a^{\alpha }$. It connects $w_a^{\alpha }$ with $u_a^{\alpha }$ and $v_a^{\alpha }$ using a simple path of length $M^2$ for each connection.

The reduction connects $u_a^{\alpha }$ with $\{p^{\alpha },q^{\alpha },r^{\alpha }\}$ using simple paths such that

• $\mathrm{■}$

  $\mathrm{dist}(u_a^{\alpha },p^{\alpha })=M^2-2aM$, $\mathrm{dist}(u_a^{\alpha },q^{\alpha })=M^2+aM$, and $\mathrm{dist}(u_a^{\alpha },r^{\alpha })=M^2+2aM$.

It connects $v_a^{\alpha }$ (only) to $q^{\alpha }$ such that $\mathrm{dist}(v_a^{\alpha },q^{\alpha })=M^2+aM$. See Figure 2 for an illustration. Consider the vertex in the simple path connecting $q^{\alpha }$ and $u_a^{\alpha }$ which is adjacent with $q^{\alpha }$. We denote the vertex by $q_a^{\alpha }$. The reduction adds a pendant vertex and makes it adjacent with $q_a^{\alpha }$.

The reduction repeats the constructions for elements $(\beta ,b)$ and $(\gamma ,c)$ in $𝒰$. In the first case, the vertices in the gadgets are connected to $\{p^{\beta },q^{\beta },r^{\beta }\}$ whereas in the latter case they are connected to $\{p^{\gamma },q^{\gamma },r^{\gamma }\}$.

Finally, for any vertices of the type $w_a^{\alpha }$, $w_b^{\beta }$, and $w_c^{\gamma }$ added in the above steps, the reduction connects each of them to $g_4$ using simple paths of length $M^2$ for each connection. See Figure 1.

This completes the construction. Suppose $P$ is the collection of all the pendant vertices in $G$. The reduction returns $(G,k=n+|P|)$ as an instance of Geodetic Set.

Note that each edge in Figure 1 corresponds to a simple path whose length is at least $0.99\cdot M^2$ and at most $1.01\cdot M^2$. Hence, the distance between any two vertices in Figure 1, where we use an edge to denote a simple path connecting two of its endpoints, is proportional to their distance in $G$.

Define $P$ to be the collection of all the pendants vertices in $G$. To prove the correctness of the reduction, we first argue that vertices in $P$ covers most of the vertices in $G$. We argue that the only vertices they do not cover are internal vertices in the red edges of Figure 1. We define these uncovered vertices as follows. Define $V^{g_1}$ as the collection of all the internal vertices in the simple path connecting $g_1$ to $z_1^i$ for any $i\in [n]$. For every $a\in [n]$, define $V_a^{\alpha }$ as the collection of internal vertices in the simple path connecting $q^{\alpha }$ to $u_a^{\alpha }$ and simple path connecting $u_a^{\alpha }$ to $w_a^{\alpha }$. Define $V^{\alpha }={\bigcup }_{a\in [n]}{V}_a^{\alpha }$. Similarly, define $V^{\beta }$ and $V^{\gamma }$.

Recall that $I(u,v)$ denotes the set of vertices in $G$ that are part of some shortest path between $u$ and $v$. Also, we generalize this definition to set $S$ by taking the union of $I(u,v)$ for all pairs of vertices $u,v$ in $S$.

We first prove that $V(G)\setminus (V^{g_1}\cup V^{\alpha }\cup V^{\beta }\cup V^{\gamma })\subseteq I(P)$. By the construction, any vertex $u$ in $G$ is adjacent with at most one pendant vertex. We use $\text{pndt}(u)$ to denote the pendant vertex adjacent with $u$, if it exists. We first consider the partition of vertices in $G$ based on the simple paths they are part of.

From the construction, $I(\text{pndt}(g_1),\text{pndt}(g_2))$ contains all the vertices in the simple path connecting $g_1$ and $g_2$. Similarly, $I(\text{pndt}(z_2^i),\text{pndt}(g_1))$ covers all the vertices in the simple path connecting $z_2^i$ and $g_1$ for every $i\in [n]$. Note that the statement of the lemma excludes the vertices in simple paths connecting $g_1$ and $z_1^i$.

From the construction, $I(\text{pndt}(z_2^i),\text{pndt}(g_2))$ covers all the vertices in the simple path connecting $z_1^i$ to $g_2$ for every $i\in [n]$. Consider vertices $x$ in $X^i$ and $y$ in $Y^i$ which are the part of $i^{th}$ set-encoding gadget ${𝒮}^i$ for some $i$ in $[n]$. $I(\text{pndt}(y),\text{pndt}(g_2))$ covers all the vertices in the simple path connecting $y$ to $g_2$. Also, $I(\text{pndt}(g_2),\text{pndt}(g_3))$ covers all the vertices in the path connecting $g_2$ with $x_{p^{\alpha }}$. A similar statement is true for the other branching vertices adjacent to $x$.

From the construction, $I(\text{pndt}(g_3),\text{pndt}(g_4))$ contains all the vertices in the simple path connecting $g_3$ and $g_4$. As argued in the previous paragraph, $I(\text{pndt}(g_2),\text{pndt}(g_3))$ covers all the vertices in the path connecting $g_3$ with all the branching vertices like $x_{p^{\alpha }}$ that are adjacent with $x$.

For all such paths, there other endpoints are adjacent to some pendant vertex. By the construction, the shortest path between the pendant vertices adjacent to the endpoints covers all the vertices in the simple path.

All the simple paths ending at $p^{\alpha }$ can be partitioned into two parts: ones that have the other endpoint in a set-encoding gadget (i.e. $x_{p^{\alpha }}$ for some $x$ in $X^i$ for some $i\in [n]$) or ones that have the other endpoint in an element-encoding gadget (i.e. $u_a^{\alpha }$ for some $a\in [n]$). In the second case, both the endpoints of the simple path are adjacent to pendant vertices. Hence, by the construction, the shortest path between the pendant vertices adjacent to the endpoints cover all the vertices in the simple path. In the first case, suppose the other endpoint of the simple path is $x_{p^{\alpha }}$ for some $x$ in $X^i$. Consider vertex $x$ and the unique vertex $y$ in $Y^i$ which is at the distant $M^2$ from $x$. By the construction, there is a shortest path from $p^{\alpha }$ to $y$ that contains $x$. Hence, $I(\text{pndt}(p^{\alpha }),\text{pndt}(y))$ covers all the vertices in the simple path connecting $p^{\alpha }$ to $x$. Since $x$ is an arbitrary point in $X^i$, the statement is true for all the vertices in the first type of simple path. These vertices are also covered by $I(\text{pndt}(p^{\alpha }),\text{pndt}(g_3))$. A similar set of arguments implies that all the vertices in the simple path ending at $p^{\beta }$ and $p^{\gamma }$ are covered by vertices in $P$.

Once again, all the simple paths ending at $q^{\alpha }$ can be partitioned into two parts: ones that have the other endpoint in a set-encoding gadget (i.e. $x_{q^{\alpha }}$ for some $x$ in $X^i$ for some $i\in [n]$) or ones that have the other endpoint in an element-encoding gadget (i.e. $u_a^{\alpha }$ or $v_a^{\alpha }$ for some $a\in [n]$). Fix an integer $a\in [n]$ and recall that $q_a^{\alpha }$ is adajcent with $q^{\alpha }$. Using the same arguments as in the above paragraph, $I(\text{pndt}(q_a^{\alpha }),\text{pndt}(y))$ covers all the vertices in the simple path connecting $q^{\alpha }$ and $x$. This proves the claim for the vertices in the first type of path. $I(\text{pndt}(q_a^{\alpha }),\text{pndt}(u_a^{\alpha }))$ covers all the vertices in the path connecting $q_a^{\alpha }$ and $u_a$. Note that the vertices in the simple path connecting $q_a^{\alpha }$ and $v_a$ are in $V^{\alpha }$, which are excluded in the statement of the lemma. A similar set of arguments implies that all the vertices in the simple path ending at $q^{\beta }$ and $q^{\gamma }$ are covered by vertices in $P$.

A similar set of arguments regarding paths ending at $p^{\alpha }$, $p^{\beta }$ or $p^{\gamma }$ proves that all the vertices in simple paths ending at $r^{\alpha }$, $r^{\beta }$ or $r^{\gamma }$ are covered by vertices in $P$.

Consider a set-encoding gadget ${𝒮}^i$ for a fixed $i$ in $[n]$. The shortest paths connecting $z_2^i$ and $g_3$ covers all vertices in simple paths connecting $z_2^i$ to $z_1^i$ and $z_1^i$ to $x$ for every $x$ in $X^i$. As argued before, there is a shortest path from $p^{\alpha }$ to $y$, for any $y$ in $Y^i$, that contains the corresponding $x$ in $X^i$. Hence, $I(\text{pndt}(p^{\alpha }),\text{pndt}(y))$ covers all the vertices in the simple path connecting $x$ to $y$. This implies that all the vertices in ${𝒮}^i$, except the vertices in $V^{g_1}$ are covered. Recall that $V^{g_1}$ contains the internal vertices of the path connecting $g_1$ with $z_1^i$.

Consider an element-encoding gadget encoding $(\alpha ,a)$ for some $a$ in $[n]$. By the construction, $I(\text{pndt}(u_a^{\alpha }),\text{pndt}(w_a^{\alpha }))$ covers all the vertices in the simple path connecting $u_a^{\alpha }$ and $w_a^{\alpha }$. We remark that the vertices in the simple path connecting $v_a^{\alpha }$ and $w_a^{\alpha }$ are part of $V^{\alpha }$ and hence excluded from the statement of the lemma. Using similar arguments for elements of the form $(\beta ,b)$ and $(\gamma ,c)$ for some $b,c$ in $[n]$.

The arguments above imply that $V(G)\setminus (V^{g_1}\cup V^{\alpha }\cup V^{\beta }\cup V^{\gamma })\subseteq I(P)$. It remains to prove that no vertex in $(V^{g_1}\cup V^{\alpha }\cup V^{\beta }\cup V^{\gamma })$ is covered by the vertices in $P$.

Consider the vertices in $V^{g_1}$ which are in the $i^{th}$ copy of set-encoding gadget for some $i$ in $[n]$. It is easy to see that vertices in $P\setminus \{\text{pndt}(z_2^i),\text{pndt}(g_1)\}$ can not cover the vertices mentioned in the previous sentence. Any shortest path whose one endpoint is $\text{pndt}(z_2^i)$ and other endpoint is in $P\setminus \{\text{pndt}(g_1)\}$ contains either $\{g_1,g_2\}$ or $\{z_1^i,g_2\}$. Hence, none of such paths can cover vertices in the path connecting $g_1$ and $z_1^i$. Similarly, any shortest path whose one endpoint is $\text{pndt}(g_1)$ and other endpoint is in $P\setminus \{\text{pndt}(z_2^i)\}$ contains $g_2$ and hence can not contain $z_1^i$. This implies that $P$ can not cover any vertex in $V^{g_1}$.

Consider the vertices in $V^{\alpha }$. It is easy to verify that vertices in $V^{\alpha }$ are not covered by the shortest path between any two common branching vertices. Also, the shortest paths between the pendant vertices in the element-encoding gadget do not cover vertices in $V^{\alpha }$. Consider vertices in $V^{\alpha }$, which are part of the element-encoding gadget corresponding to element $(\alpha ,a)$ for some $a$ in $[n]$. Any shortest path between the vertices in $P$ that can cover these vertices has $\text{pndt}(w_a^{\alpha })$ as one of its endpoint and should contain $q^{\alpha }$. By the construction, no path connecting $\text{pndt}(w_a^{\alpha })$ to any of the pendant vertex adjacent with common branching vertices contains $q^{\alpha }$. It is easy to see for $p^{\alpha }$, $r^{\alpha }$, $g_3$ and $g_4$. For the remaining common vertices, it is sufficient to prove that the shortest path from $\text{pndt}(w_a^{\alpha })$ to $g_2$ do not contain $q^{\alpha }$. Note that the path from $w_a^{\alpha }$ to $g_2$ that contains $q^{\alpha }$ and $x_{q^{\alpha }}$ for some $x$ in $X^i$, is of length close to $4M^2$. However, the shortest path from $\text{pndt}(w_a^{\alpha })$ to $g_2$ is of length $3M^2$ and contains $y$ in some $Y^i$ and $g_4$. This implies that $P$ does not cover any vertex in $V^{\alpha }$. Using similar arguments, the statement holds for vertices in $V^{\beta }$ and $V^{\gamma }$ which concludes the proof of the lemma. $◀$

In the following two lemmas, we prove that the reduction is safe.

Without loss of generality, suppose $\{S_1,S_2,\mathrm{\dots },S_n\}$ is a collection of $n$ sets in collection of $𝒮$ (which contains $m$ sets) that partitions all the vertices in $𝒰$. For every $i$ in $[n]$, consider a vertex in $X^i$ in the set-encoding gadget ${𝒮}^i$ corresponding to set $S_i$. Define set $Q=\{x_1^1,x_2^2,\mathrm{\dots },x_n^n\}$, where $x_i^i$ is in $X^i$. Recall that $P$ is the collection of all the pendant vertices in $G$. It is easy to see that $|P\cup Q|=k$. Due to Lemma 2, to prove that $P\cup Q$ is a geodetic set of $G$, it is sufficient to prove that $Q$ covers vertices in $V^{g_1}\cup V^{\alpha }\cup V^{\beta }\cup V^{\gamma }$. See the paragraph above Lemma 2 for the definition of these sets. Also, recall that for any vertex $u$, $\text{pndt}(u)$ denotes the unique pendant vertex adjacent to it, if one exists.

For a fixed $i$ in $[n]$, $I(x_i^i,\text{pndt}(g_1))$ covers all the vertices in the simple path connecting $z_1^i$ to $g_1$. As this is true for any $i$ in $[n]$, $Q$ covers vertices in $V^{g_1}$. Suppose $S^i=\{(\alpha ,a),(\beta ,b),(\gamma ,c)\}$ for some $a,b,c$ in $[n]$. Consider vertex $x_i^i$ in $X^i$. We argue that the shortest paths between $x_i^i$ and $w_a^{\alpha }$ covers the vertices in $V^{\alpha }$ that are part of the element-encoding gadget that is encoding element $(\alpha ,a)$. Consider Figure 2 with $a^{\prime }=a$. In this case, all three paths from $x_i^i$ to $u_a^{\alpha }$ via $p^{\alpha }$, $q^{\alpha }$, and $q^{\alpha }$ as the same length of $2M^2$. This implies the shortest distance between $x_i^i$ and $w_a^{\alpha }$ is $3M^2$. Moreover, the path connecting $x_i^i$ to $w_a^{\alpha }$ that contains $q^{\alpha }$ and $v_a^{\alpha }$ is the shortest path between these two vertices. Hence, the shortest path between $x_i^i$ and $\text{pndt}(w_a^{\alpha })$ covers all the vertices in $V^{\alpha }$ that are part of element-encoding gadget. As $\{S_1,S_2,\mathrm{\dots },S_n\}$ partitions $𝒰$, (exactly) one of these $n$ set contains element $(\alpha ,a)$ for every $a$ in $[n]$, all the vertices in $V^{\alpha }$ are covered by a vertex in $Q$ and a vertex in $P$. Using the similar arguments, all the vertices in $V^{\beta }$ and $V^{\gamma }$ are covered by vertices in $P\cup Q$. This concludes the proof of the lemma. $◀$

Recall that $P$ is the collection of all the pendant vertices in $G$, and $P$ is a subset of any geodetic set of $G$. Suppose $P\cup Q$ is the geodetic set of $G$ of size of $k$, and hence $|Q|\le n$. By Lemma 2, vertices in $Q$ covers all the vertices in $V^{g_1}\cup V^{\alpha }\cup V^{\beta }\cup V^{\gamma }$. See the paragraph before Lemma 2 for the definition of these sets.

We first prove that $Q$ contains at least one vertex in the $i^{th}$ copy of set-encoding gadget ${𝒮}^i$ for every $i$ in $[n]$. Assume, for the sake of contradiction, that this is not the case for an index $i$. Recall that $V^{g_1}$ is the union of internal vertices connecting paths $g_1$ and $z_1^i$ for $i$ in $[n]$. Define $V_i^{g_1}$ as the set of vertices in $V^{g_1}$ which are in ${𝒮}^i$. Consider a vertex, say $h$, in $V_i^{g_1}$. As $P\cup Q$ is a geodetic set of $G$, there are two vertices in it, say $s_1$ and $s_2$, that covers the vertex $h$. By Lemma 2, $s_1$ and $s_2$ are not in $P$. By the above assumption, $s_1$ and $s_2$ are not in ${𝒮}^i$. Consider the shortest path from $s_1$ to $s_2$ that contains the vertex $h$. Suppose that the paths enter and exit ${𝒮}^i$ via common branching vertices $c_1$ and $c_2$. Consider the case when $\{c_1,c_2\}\cap \{q^{\alpha },q^{\beta },q^{\gamma }\}=\mathrm{\varnothing }$. In this case, the shortest path between $\text{pndt}(c_1)$ and $\text{pndt}(c_2)$ also contains the vertex $h$. However, this contradicts Lemma 2, which states vertices in $P$ can not cover any vertex in $V^{g_1}$. Consider the other case when the shortest path enters ${𝒮}^i$ via, say, $q^{\alpha }$. In this case, the above arguments can be extended to the shortest path from $\text{pndt}(q_a^{\alpha })$ for some $a$ in $[n]$. This also leads to contradiction to Lemma 2. Hence, our assumption is wrong and $Q$ contains at least one vertex in ${𝒮}^i$.

As the cardinality of $Q$ is at most $n$, this implies that $Q$ contains exactly one vertex in ${𝒮}^i$ for every $i$ in $[n]$. Let $q$ be the unique vertex in $Q$ which is in ${𝒮}^i$. We determine the position of $Q$ in ${𝒮}^i$ using the fact that the shortest paths from $q$ to some other vertices in $(P\cup Q)\setminus \{q\}$ covers all the uncovered vertices in the set-encoding gadget ${𝒮}^i$. We now restrict the possible cases for this other vertex in $P\cup Q$. Let $h$ be the other vertex in $(P\cup Q)\setminus \{q\}$, so the shortest path from $q$ to $h$ covers some vertices in $V_i^{g_1}$. By the arguments above, $h$ is not in ${𝒮}^i$. As argued in the previous paragraph, the vertices covered by the shortest path from $q$ to $h$ are also covered by the shortest path from $q$ to $\text{pndt}(c)$ where $c$ is a common branching vertex or the vertex with pendant neighbor which is adjacent to either $q^{\alpha }$, $q^{\beta }$, or $q^{\gamma }$. Hence, while considering the cases of shortest path from $q$ to $h$, it is sufficient to check the cases when $h$ is one of the vertex mentioned in the previous sentence. Note that as no vertex in $Q$ is present in any element-encoding gadget, vertices in $Q$, which are in set-encoding gadgets, are also used to cover the uncovered vertices in the element-encoding gadget. We use this property to narrow the location of $q$ in ${𝒮}^i$.

We partition ${𝒮}^i$ into the following parts and prove that $q$ can be located in particular types of parts. By the construction, deleting all the common branching vertices results in a collection of trees. Consider ${𝒮}^i$ and root it at $z_1^i$.

• $\mathrm{■}$

  For a vertex $x$ in $X^i$, consider the vertex $x_{p^{\alpha }}$ adjacent with it and on the path connecting $p^{\alpha }$. Define $x_{p^{\alpha }}$-part as the subtree rooted at $x_{p^{\alpha }}$. Similarly, define $x_{p^{\beta }}$-part and $x_{p^{\gamma }}$-part. In Figure 3, $x_{p^{\alpha }}$-part is highlighted in blue.

• $\mathrm{■}$

  For every $y$ in $Y^i$, define $y$-part as subtree rooted at $y$, which is highlighted using orange color in Figure 3.

• $\mathrm{■}$

  For every $x$ in $X^i$ and the corresponding $y$ in $Y^i$, i.e. the unique vertex in $Y^i$ which is at distance $M^2$ from $x$, define $(x,y)$-part as the collection of internal vertices of the path from $x$ to $y$. See the brown edge in Figure 3.

• $\mathrm{■}$

  For every $x$ in $X^i$, define $(z_1^i,x]$-part as the vertex $x$ and the internal vertices of the path from $x$ to $z_1^i$. See the green part in Figure 3. Note that the part contains $x$ but not $z_1^i$.

• $\mathrm{■}$

  Let $h,h_1$ and $h_2$ be the middle points of the paths from $z_1^i$ to $z_2^i$, from $z_1^i$ to $g_1$, and from $z_2^i$ to $g_2$, respectively. Define $z_1^i$-part as the tree rooted at $z_1^i$ with $h,h_1$ and $h_2$ as its leaves. This is highlighted by the purple color in Figure 3.

• $\mathrm{■}$

  All the remaining vertices are considered as left-over part, highlighted using cyan color in Figure 3. Note that this is the only disconnected part in the partition.

Using the fact that $q$ is used to cover the vertices in $V_i^{g_1}$, we first argue it is not in the part of the first-type or of the second type mentioned above, nor can it be in the leftover part. Assume $q$ is in $x_{p^{\alpha }}$-part for some $x$ in $X^i$. In this case, the shortest path from $q$ to $g_1$ is via $g_2$ and hence does not contain vertices in $V_i^{g_1}$. Similarly, the shortest path from $q$ to $z_2^i$ is via $g_1$ or via $z_1^i$ and can not contain vertices in $V_i^{g_1}$. It is easy to see that in this case, there are no paths from $q$ to any other vertex in $P$ can cover vertices in $V_i^{g_1}$. Hence, $q$ cannot be in $x_{p^{\alpha }}$-part. Now, assume $q$ is in $y$-part for some $y$ in $Y^i$. The shortest path from $q$ to $g_1$ is via $g_2$ and to $z_2^i$ is via $g_1$ or $z_1^i$; hence, no such short paths can cover vertices in $V_i^{g_1}$. Finally, it is easy to see that there is no vertex in the leftover part can cover any vertex in $V_i^{g_1}$.

We now turn our attention to the remaining parts, viz $(x,y)$-part, $(z_1^i,x]$-part, for some $x$ in $X^i$, or $z_1^i$-part. Note that the shortest path from any vertex in $(z_1^i,x]$-part or $z_1^i$-part to $g_1$ covers all the vertices in $V_i^{g_1}$ whereas the same is true for half the vertices in $(x,y)$-part which are closer to $x$ than they are to $y$. In the next few paragraphs, we argue that the only vertices in the $(z_1^i,x]$-part can be used to cover the uncovered vertices in the element encoding gadget. Recall that for every $a\in [n]$, define $V_a^{\alpha }$ as the collection of internal vertices in the simple path connecting $q^{\alpha }$ to $u_a^{\alpha }$ and the simple path connecting $u_a^{\alpha }$ to $w_a^{\alpha }$. We also defined $V^{\alpha }={\bigcup }_{a\in [n]}{V}_a^{\alpha }$ and defined $V^{\beta }$ and $V^{\gamma }$ in a similar way. Note that $V^{\alpha }$, $V^{\beta }$, and $V^{\gamma }$ are the collection of uncovered vertices in the element-encoding gadget.

Suppose vertex $x$ in $X^i$ corresponds to set $S=\{(\alpha ,a^{\prime }),(\beta ,b^{\prime }),(\gamma ,c^{\prime })\}$ and $h$ is a vertex in $(z_1^i,x]$-part. We prove that $I(h,w_a^{\alpha })$ covers $V_a^{\alpha }$ if and only if $a^{\prime }=a$. For a vertex $h$ in $(z_1^i,x]$-part, suppose $\mathrm{dist}(h,x)=d_h$. Consider the four paths from $h$ to $w_a^{\alpha }$ that are of length at most $d_h+3M^2$ and contains exactly one common branching point amongst $\{g_4,p^{\alpha },q^{\alpha },r^{\alpha }\}$. Consider the path from $h$ to $w_a^{\alpha }$ that contains $x$, the corresponding $y$, and $g_4$. By the construction, the length of this path is $d_h+3M^2$. For the remaining three paths, consider Figure 2. The lengths of these three paths is $d_h+3M^2+2(a^{\prime }-a)M$, $d_h+3M^2+(a-a^{\prime })M$, and $d_h+3M^2+2(a-a^{\prime })M$ when it contains $p^{\alpha }$, $q^{\alpha }$, and $r^{\alpha }$, respectively. Note that $I(h,w_a^{\alpha })$ covers $V_a^{\alpha }$ if and only the shortest path from $h$ to $w_a^{\alpha }$ contains $q^{\alpha }$. From the distances above, it is easy to see that this condition is true only when $a=a^{\prime }$. Following the identical arguments, we can prove that $I(h,w_b^{\beta })$ covers $V_b^{\beta }$ if and only if $b^{\prime }=b$, and $I(h,w_c^{\gamma })$ covers $V_a^{\gamma }$ if and only if $c^{\prime }=c$.

We next prove that no vertex from $(x,y)$-part or $z_1^i$-part can cover any uncovered vertex in the element-encoding gadget. Consider a vertex $h$ in $(x,y)$-part. As argued in the previous paragraph, $I(h,w_a^{\alpha })$ can cover the vertices in $V^{\alpha }$ if and only if the shortest path from $h$ to $w_a^{\alpha }$ contains $q^{\alpha }$. However, the shortest path from $h$ to $w_a^{\alpha }$ contains $g_4$ and hence cannot cover the vertices in $V^{\alpha }$. Now consider the vertices in $z_1^i$-part. For any vertex $h$ in $z_1^i$-part which is an internal vertex of path from $z_1^i$ to $g_2$, the shortest path $h$ to $w_a^{\alpha }$ contains $g_4$ and hence can not cover vertices in $V^{\alpha }$. Note that the shortest path from $z_1^i$ to $w_a^{\alpha }$ also contains $g_4$ in it. This is implied by the fact that the distance between $g_2$ and every vertex in $Y^i$ is $M^2-1$ (instead of $M^2$ like most of the other paths). Hence, $I(z_1^i,w_a^{\alpha })$ does not cover any vertex in $V^{\alpha }$. For any vertex in the remaining $z_1^i$-part, the shortest path from it to $w_a^{\alpha }$ is via $z^i$, which contains $g_4$. These arguments imply that $q$ can not be in $(x,y)$-part or $z_1^i$- part for any $x$ in $X^i$.

We are in a position to conclude the proof of the lemma. Recall that $P\cup Q$ is a geodetic set of $G$. Considering the position of vertices in $Q$, we construct a collection of $n$ subsets ${𝒮}^{\prime }$ of $𝒮$ as follows: For every $i$ in $[n]$, let $x$ be the unique vertex in $X^i$ such that the vertex in $Q$ is in $(z_1^i,x]$-part of ${𝒮}^i$. If $x$ corresponds to set $S$, then include $S$ in ${𝒮}^{\prime }$. It is easy to see that the cardinality of ${𝒮}^{\prime }$ is at most $n$. We argue that ${𝒮}^{\prime }$ covers all the vertices in $𝒰$. Consider an arbitrary element, say $(\alpha ,a)$, in $𝒰$. The vertices in $V^{\alpha }$ are part of the element-encoding gadget that encodes $(\alpha ,a)$. By above arguments, for some $i$ in $[n]$, there is $x$ in $X^i$ such that $(z_1^i,x_1]$-part of ${𝒮}^i$ contains vertex $q$ in $Q$ with the property that $I(q,w_a^{\alpha })$ covers vertices in $V^{\alpha }$ in the element-encoding gadget. Suppose $x$ corresponds to the vertex $S=\{(\alpha ,a^{\prime }),(\beta ,b^{\prime }),(\gamma ,c^{\prime })\}$ for some $a^{\prime },b^{\prime },c^{\prime }\in [n]$. From the arguments above, $I(q,w_a^{\alpha })$ covers vertices in $V^{\alpha }$ if and only if $a^{\prime }=a$. This implies that $(\alpha ,a)$ is covered by some set in ${𝒮}^{\prime }$. Since this is an arbitrary element in $𝒰$, one can conclude that ${𝒮}^{\prime }$ covers all the vertices in $𝒰$. This implies that $(𝒰,𝒮)$ is a Yes-instance of 3-Dimensional Matching. $◀$

We present a mixed search strategy to clean $G$ using $17$ searchers to bound the pathwidth of $G$. Place $13$ searchers on common branching vertices. These searchers will never move from their places. (This is equivalent to deleting common branching vertices and presenting a mixed search strategy using four searchers for the resulting graph.) We search the graph in $3n+n$ rounds, one round for each element-encoding gadget and one round for each set of set-encoding gadget, respectively.

Consider an element-encoding gadget encoding an element, say $(\alpha ,a)$ for some $a$ in $[n]$. We can place three searchers on $u_a^{\alpha }$, $v_a^{\alpha }$, and $w_a^{\alpha }$, and the fourth searcher can move along the simple path connecting these vertices and with common branching vertices to clean all the edges in the connecting paths.

By the construction, deleting all the common branching vertices results in a collection of trees. Consider the set-encoding gadget ${𝒮}^i$ for some $i$ in $[n]$ and root it at $z_1^i$. In each round, we fix a searcher on $z_1^i$. We need one searcher to clean all the edges between the simple path connecting $z_1^i$ to $g_1$ via $z_2^i$, path of length $M^2$ connecting $z_1^i$ to $g_1$, and finally path connecting $z_1^i$ to $g_2$. Once these paths are cleaned, the searcher is free and can be used to clean the remaining part of the set-encoding gadget. We divide the remaining part of this round into $m$ sub-rounds corresponding to each vertex in $X^i$. For a sub-round, fix two searchers on a vertex $x$ in $X^i$ and another searcher on the corresponding vertex $y$ in $Y^i$ which is at distance $M^2$ from $x$. The remaining searcher can clean all the edges in the simple paths connecting $x$ to $y$, $y$ to common vertices, and $x$ to $z_1^i$. Next, the searcher placed on $y$ can be relocated to each of the branching vertices adjacent to $x$, i.e. vertices of the form $x_{p^{\alpha }}$. Now, the other searcher can be used to clean the subtree rooted at the branching vertex. This completes one sub-round. Completing such $m$ sub-rounds clears all the paths in ${𝒮}^i$.

As we need $17$ searchers to clean the graph, result of Takahashi et al. [38] implies that $\mathrm{𝚙𝚠}(G)\le 17$.

As deleting all the common branching vertices results in a collection of trees, feedback vertex set number of the graph is $13$. $◀$