Hardness of Metric Dimension in Graphs of Constant Treewidth

Abstract

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set $S \subseteq V(G)$ is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth $24$.

1 Introduction

Let G be an unweighted and undirected graph and let $S \subseteq V(G)$. For a vertex $v \in V(G)$, the distance vector from v to S is the assignment $S \ni w \mapsto \mathrm {dist}_G(v,w)$, where $\mathrm {dist}_G$ denotes the distance in the graph G. The set S is resolving if a distance vector to S uniquely determines the source vertex; that is, no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum possible size; such a set is sometimes called the metric basis of G. The decision version of Metric Dimension asks for a resolving set of size not exceeding a given threshold k.

Metric Dimension has already been introduced in 1970s [8, 13]. Determining its computational complexity turned out to be quite challenging. It is polynomial-time solvable on trees [8, 11, 13], outerplanar graphs [3], and chain graphs [6], but NP-hard for example on planar graphs [3], split graphs [5] or even interval graphs and permutation graphs [7]. From the parameterized complexity point of view, the FPT status of the Metric Dimension parameterized by the solution size has been open for a while and finally resolved in negative by Hartung and Nichterlein [9]. In the search of a tractable structural parameterization, FPT algorithms has been shown for parameters: treelength plus maximum degree [1], vertex cover number [9], max leaf number [4], and modular-width [1].

The above list misses probably the most important graph width measure, namely treewidth. Determining the complexity of Metric Dimension, parameterized by treewidth, remained elusive in the last years, and has been asked a few times [1, 3, 4]. Bonnet and Purohit in a paper presented at IPEC 2019 [2] showed that the problem is W[1]-hard, even with treewidth parameterization. In this work we strengthened their result by proving para-NP-hardness of this parameterization.

Theorem 1

Metric Dimension, restricted to graphs of treewidth at most $24$, is NP-hard.

Theorem 1 brings us much closer to closing (unfortunately mostly in negative) the question of the complexity of Metric Dimension in graphs of bounded treewidth. The remaining gap is to determine the exact treewidth value where the problem becomes hard: note that it is open if Metric Dimension is polynomial-time solvable on graphs of treewidth 2.

The proof of Theorem 1 starts with a construction of a graph with a separation of order 9 over which a lot of information on a partial solution to Metric Dimension is transfered. More formally, similarly as Bonnet and Purohit [2], we use the Multicolored Resolving Set problem as an auxiliary intermediate problem. In this problem, the input graph is additionally equipped with an integer k, a tuple of k disjoint vertex sets $X_1,X_2,\ldots ,X_k$, and a set $\mathcal {P}$ of vertex pairs. The goal is to choose a set S consisting of exactly one vertex from each set $X_i$ so that for every $\{u,v\} \in \mathcal {P}$, the pair $\{u,v\}$ is resolved by S, that is, u and v have different distance vectors to S. In our construction, the sets $X_i$ are on one side of the said separation of order 9, while the pairs $\mathcal {P}$ are on the second side. The crux of the construction is to make every distance from a vertex of the separator to a chosen vertex of S count: despite the fact that the separation has constant size, S is of unbounded size, giving $\Omega (|S|)$ distances to work with. Overall, the above gives a relatively clean reduction giving NP-hardness of Multicolored Resolving Set in graphs of constant treewidth, presented in Sect. 3. This reduction is the main new insight and technical contribution of this paper.

Then, again similarly as in the work of Bonnet and Purohit [2], it takes a lot of effort (presented in Sect. 4) to turn the above reduction to Multicolored Resolving Set into a reduction to Metric Dimension. Here, there are two problems. First, one needs to introduce some gadgets to force the solution to take exactly one vertex from each set $X_i$. Second, one needs to ensure that the intended solution resolves all vertex pairs, not only the ones from $\mathcal {P}$. For both problems, we borrow the tools from Bonnet and Purohit [2]. In particular, the first problem is resolved by forced set gadgets in a way very similar to [2]. The second problem is resolved by adding a number of new connections to the graph and forced vertex gadgets of [2]. Thus, while the toolbox remains the same as in [2], the application is different as the graph we are working with is significantly different. The construction is presented in Sections 4.1-4.2.

After applying all the modifications to obtain a Metric Dimension instance, one needs to check three aspects. First, one needs to ensure that the forced set gadgets work as intended, forcing the solution to take one vertex from each $X_i$; this check is rather simple and very similar to the analogous check of [2]. Second, one needs to check that the introduced forced vertex gadgets, that contain extra vertices from the intended resolving set (apart from the ones in $X_i$s), do not accidentally resolve any pair from $\mathcal {P}$. This check is not trivial, but still relatively simple. Note that the mentioned two properties already ensure one of the implications in the proof of the correctness of the reduction: if the final Metric Dimension instance is a yes-instance, then the input instance of the source problem is a yes-instance. These two checks are presented in Sect. 4.3.

Then one needs to check that every pair of vertices is resolved by an intended solution. Due to the complexity of the construction and the properties of this problem, this turned out to be long and arduous, spanning more than half of the volume of this paper (Sect. 5).

Besides, we show that the treewidth of the constructed graph is bounded by a constant in Sect. 4.4.

2 Preliminaries

In this paper, all graphs are undirected. In a graph G, let V(G) be the set of vertices of G. For a vertex $v\in V(G)$, we denote the open neighborhood and closed neighborhood of v by $N_G(v)$ and $N_G[v]$ respectively (or just N(v) and N[v] if the graph is clear in the context). For two vertices $u,v\in V(G)$, let P(u, v) be a path from u to v. Since the graph is undirected, P(u, v) and P(v, u) denote the same path. We denote the neighbor of u on P(u, v) by $N_u(u,v)$ (also the neighbor of v on P(u, v) by $N_v(u,v)$). Similarly, if there is a path which is named as, for example, $P^{h}(i,j,x)$ such that u is one endpoint of $P^{h}(i,j,x)$, we denote the neighbor of u on $P^{h}(i,j,x)$ by $N^{h}_{u}(i,j,x)$. For simplicity, we abuse the notation in the sense that for a path P, we use P to denote the path or the vertex set of the path. The meaning should be clear in the context. We define the length of a path P to be the number of edges on the path and denote it by |P|. For two vertices $u,v\in V(G)$, we define the distance between u and v to be the length of any shortest path from u to v, denoted by $\text {dist}_G(u,v)$. Note that in this paper we use $\text {dist}(u,v)$ to denote the distance between u and v mostly if the graph is clear in the context. For a path P of even length with two endpoints u and v, let w be the vertex on P such that the length of the subpath of P from u to w equals the length of the subpath of P from w to v. Then we call w the middle vertex of P and denote it by $\text {mid}(P)$. We say that two distinct vertices $u,u'$ are true twins if $N[u]=N[u']$. Since a path decomposition is also a tree decomposition, the treewidth of a graph G is at most the pathwidth of G. In this paper, for convenience of the proof, we use the alternative characterization of pathwidth, i.e. the pathwidth of a graph G equals the node search number of G minus one [12]. The definition of the node search number comes from the node search game. We give an informal definition of the node search game as follows. Imagine that the edges of an undirected graph G are tunnels and they are contaminated by some gas. We need to put searchers on vertices of G to clean the gas. The rule is that when both of the two endpoints of an edge are occupied by searchers, this edge becomes clean. However, if we remove some searchers from the graph, a cleaned edge can be recontaminated immediately through an unoccupied endpoint to which a contaminated edge is incident. The node search number of G is the minimum number of searchers required to clean all edges of G.

3 Reduction from 3-Dimensional Matching to Multicolored Resolving Set

Bonnet and Purohit introduced k -Multicolored Resolving Set as an intermediate problem in order to show the W[1]-hardness of Metric Dimension parameterized by treewidth [2].

We show that this problem is NP-hard on graphs of constant treewidth. We make a reduction from 3-dimensional matching, which is well-known to be NP-hard [10].

Given an instance $(U,\mathcal F)$ of 3-dimensional matching with the universe $U=\{1,2,3\}\times [n]$ and a set $\mathcal{F}$ of m tuples $A_1,...,A_m\subseteq U$, we construct an instance $(G,n,\chi ,\mathcal P)$ of n -Multicolored Resolving Set as follows. First, we create m vertices $s_i^1,...,s_i^m$ as $X_i$ for each $i\in [n]$. Let $\chi =\{X_1,...,X_n\}$ and $X=\bigcup \limits _{i=1}^{n}X_i$. Then we create n vertex pairs $\{u_r^1,v_r^1\},...,\{u_r^n,v_r^n\}$ for each $r\in \{1,2,3\}$ and let $\mathcal{P}_r=\{\{u_r^i,v_r^i\}|i=1,...,n\}$. We create 3 vertices $a_r,b_r,c_r$ and let $W_r=\{a_r,b_r,c_r\}$ for each $r\in \{1,2,3\}$. Let $\mathcal{P}=\mathcal{P}_1\cup \mathcal{P}_2\cup \mathcal{P}_3$ and $W=W_1\cup W_2\cup W_3$. Finally, let $M=40(n+1)$. For each tuple $A_j=\{(1,x),(2,y),(3,z)\}$ ($j\in [m],x,y,z\in [n]$) of the given instance and each integer $i\in [n]$, we link $s_i^j$ to $a_1,b_1,c_1$ with three paths $P(s_i^j,a_1),P(s_i^j,b_1),P(s_i^j,c_1)$ of lengths $\frac{M}{2}+10x, \frac{M}{2}+5x+1$ and $\frac{M}{2}-10x$ respectively, link $s_i^j$ to $a_2,b_2,c_2$ with three paths $P(s_i^j,a_2),P(s_i^j,b_2),P(s_i^j,c_2)$ of lengths $\frac{M}{2}+10y, \frac{M}{2}+5y+1$ and $\frac{M}{2}-10y$ respectively, and link $s_i^j$ to $a_3,b_3,c_3$ with three paths $P(s_i^j,a_3),P(s_i^j,b_3),P(s_i^j,c_3)$ of lengths $\frac{M}{2}+10z, \frac{M}{2}+5z+1$ and $\frac{M}{2}-10z$ respectively. For every vertex pair $\{u_r^p,v_r^p\}$ ($p\in [n],r\in \{1,2,3\}$), we link $u_r^p$ to $a_r,b_r,c_r$ with three paths $P(u_r^p, a_r),P(u_r^p, b_r),P(u_r^p, c_r)$ of lengths $\frac{M}{2}-10p, \frac{M}{2}-5p-1$ and $\frac{M}{2}+10p$ respectively, and link $v_r^p$ to $a_r,b_r,c_r$ with three paths $P(v_r^p, a_r),P(v_r^p, b_r),P(v_r^p, c_r)$ of lengths $\frac{M}{2}-10p, \frac{M}{2}-5p-2$ and $\frac{M}{2}+10p$ respectively. This finishes the construction. See Fig. 1 for an example.

Fig. 1

An example of the reduction from 3-Dimensional Matching to n -Multicolored Resolving Set in which $U=\{1,2,3\}\times [n]$ and $\mathcal{F}=\{A_1,...,A_m\}$. Here we only draw the corresponding paths and resolved pairs of the tuple $A_j=\{(1,x),(2,y),(3,z)\}$

Lemma 1

For an arbitrary vertex pair $\{u_r^x,v_r^x\}\in \mathcal{P}$ ($r\in \{1,2,3\}, x\in [n]$),$\{u_r^x,v_r^x\}$ is resolved by $s_i^j$ ($i\in [n],j\in [m]$) if and only if $(r,x)\in A_j$.

Proof

On one hand, suppose that $(r,x)\in A_j$. For an arbitrary $i\in [n]$, the three paths from $s_i^j$ to $u_r^x$ via $a_r,b_r$ and $c_r$ have lengths M, M and M respectively. The three paths from $s_i^j$ to $v_r^x$ via $a_r,b_r$ and $c_r$ have lengths $M,M-1$ and M respectively. Note that there could be other paths from $s_i^j$ to $v_r^x$ or $u_r^x$ that go repeatedly between vertices in X and vertices in W. However, the lengths of such paths are at least $M-20n+M-10n>M$. As a result, the shortest paths from $s_i^j$ to $u_r^x$ and $v_r^x$ are of lengths M and $M-1$ respectively. Thus $\{u_r^x,v_r^x\}$ is resolved by $s_i^j$.

On the other hand, for an arbitrary tuple $A_i=\{(1,p_1),(2,p_2),(3,p_3)\}$, the paths from the vertex $s_i^j$ ($i\in [n]$) to $u_r^x$ ($r\in \{1,2,3\}$) via $a_r,b_r$ and $c_r$ have lengths $M+10(p_r-x),M+5(p_r-x)$ and $M-10(p_r-x)$ respectively. The paths from the vertex $s_i^j$ ($i\in [n]$) to $v_r^x$ ($r\in \{1,2,3\}$) via $a_r,b_r$ and $c_r$ have lengths $M+10(p_r-x),M+5(p_r-x)-1$ and $M-10(p_r-x)$ respectively. Note that the paths from $s_i^j$ to $u_r^x$ (or $v_r^x$) that go repeatedly between the vertices in X and the vertices in W have lengths at least $M-20n+M-10n>M+10n$. They are not the shortest paths from $s_i^j$ to $u_r^x$ (or $v_r^x$). If $p_r<x$, the shortest paths from $s_i^j$ to $u_r^x$ and $v_r^x$ both have lengths $M+10(p_r-x)$. If $p_r>x$, the shortest paths from $s_i^j$ to $u_r^x$ and $v_r^x$ both have lengths $M-10(p_r-x)$. If $p_r=x$, the shortest paths from $s_i^j$ to $u_r^x$ and $v_r^x$ have lengths M and $M-1$ respectively. As a result, if $\{u_r^x,v_r^x\}$ is resolved by $s_i^j$, then $p_r=x$. According to the construction, $(r,x)\in A_j$. $\square$

Lemma 2

The constructed instance $(G,n,\chi ,\mathcal P)$ of n -Multicolored Resolving Set is a yes-instance if and only if the given instance $(U,\mathcal F)$ of 3-dimensional matching is a yes-instance.

Proof

($\Leftarrow$) For an arbitrary tuple $A_i=\{(1,x),(2,y),(3,z)\}$, according to Lemma 1, pairs $\{u_1^x,v_1^x\}$,$\{u_2^y,v_2^y\}$ and $\{u_3^z,v_3^z\}$ are all resolved by $s_i^j$ for every $i\in [n]$. Suppose that the given instance of 3-dimensional matching is a yes-instance, that is, there exists $A_{j_1},...,A_{j_n}$ satisfying that $\bigcup \limits _{h=1}^{n} A_{j_h}=U$. It follows that $S=\{s_h^{j_h}:h\in [n]\}$ is a solution for the constructed instance of n -Multicolored Resolving Set.

($\Rightarrow$) Let $S=\{s_h^{j_h}:h\in [n]\}$ be a solution for the constructed instance of n -Multicolored Resolving Set. For an arbitrary pair $\{u_r^x,v_r^x\}$, since it is resolved by some $s_{h'}^{j_{h'}}\in S$, according to Lemma 1, $(r,x)\in A_{j_{h'}}$. As a result, $\{A_{j_h}:h\in [n]\}$ is a solution for the instance of 3-dimensional matching. $\square$

It is well-known that the treewidth of a graph is bounded by the size of a minimum feedback vertex set of the graph. We can easily observe that W is a feedback vertex set of size 9 for G. It follows that the treewidth of G is at most 10. Then we have the following lemma.

Lemma 3

k-Multicolored Resolving Set is NP-hard even on graphs of treewidth at most 10.

4 Reduction from Multicolored Resolving Set to Metric Dimension

In this section, we create in polynomial time an instance $(G',k)$ of Metric Dimension, which is equivalent to the instance $(G,n,\chi ,\mathcal P)$ of n -Multicolored Resolving Set we created in last section. Roughly speaking, the reduction consists in adding gadgets on base of the constructed instance $(G,n,\chi ,\mathcal P)$ to solve the following two issues: (1) the solution for Metric Dimension could contain vertices not in any set of $\chi$ or more than one vertex from some set of $\chi$, which would spoil the desired reduction; (2) we did not make sure that every pair of distinct vertices are resolved by the solution in an instance of n -Multicolored Resolving Set. We find that similar strategies to those in [2] can be used to solve these two issues. More specifically, we solve the first issue by adding forced set gadgets. One such gadget contains two pairs of vertices such that they are only resolved simultaneously by a vertex of $X_i$ (where it is attached). We solve the second issue by adding forced vertex gadgets. One such gadget contains a pair of pendant neighboring vertices (true twins), both of which are also adjacent to an identical vertex. Such construction forces at least one vertex of the true twins to be chosen in the solution. The chosen vertices (forced vertices) are designed to resolve the remaining unresolved vertex pairs. Besides, we need to add a number of extra paths and set appropriate budget k to make sure that the reduction works as described above.

4.1 Construction of the Forced Set Gadgets

Let $(G,n,\chi ,\mathcal P)$ be an instance of n -Multicolored Resolving Set that we created in last section. For every $X_i\in \chi$ ($i\in [n]$), we add two pairs of isolated vertices $\{p_i^1,q_i^1\}$ and $\{p_i^2,q_i^2\}$. Then we add two vertices $\pi _i^1$ and $\pi _i^2$ such that $p_i^1,q_i^1$ are adjacent to $\pi _i^1$ while $p_i^2,q_i^2$ are adjacent to $\pi _i^2$. The vertex triples $p_i^1,q_i^1,\pi _i^1$ and $p_i^2,q_i^2,\pi _i^2$ ($i\in [n]$) form a forced set gadget. Then we create a path $P(s_i^j, p_i^1)$ of length $20(n+1)$ from $s_i^j$ to $p_i^1$ and create a path $P(s_i^j, p_i^2)$ of length $20(n+1)$ from $s_i^j$ to $p_i^2$ for each $i\in [n], j\in [m]$. In order to make sure that a vertex can resolve $p_i^1,q_i^1$ and $p_i^2,q_i^2$ simultaneously if and only if it belongs to $X_i$, we need to create 4 paths of length $20(n+1)$ from $\pi _i^1$ to $N_{s_i^j}(s_i^j,a_r)$, from $\pi _i^1$ to $N_{s_i^j}(s_i^j,b_r)$, from $\pi _i^1$ to $N_{s_i^j}(s_i^j,c_r)$ and from $\pi _i^1$ to $N_{s_i^j}(s_i^j,p_i^2)$ respectively for each $i\in [n]$, $j\in [m]$ and $r\in \{1,2,3\}$. For simplicity, we name the four paths as $P^{1}(i,j,a_r)$, $P^{1}(i,j,b_r)$, $P^{1}(i,j,c_r)$ and $P^{1}(i,j,p_i^2)$ respectively. Symmetrically, we need to create 4 paths of length $20(n+1)$ from $\pi _i^2$ to $N_{s_i^j}(s_i^j,a_r)$, from $\pi _i^2$ to $N_{s_i^j}(s_i^j,b_r)$, from $\pi _i^2$ to $N_{s_i^j}(s_i^j,c_r)$ and from $\pi _i^2$ to $N_{s_i^j}(s_i^j,p_i^1)$ respectively for each $i\in [n]$ and $r\in \{1,2,3\}$. For simplicity, we name the four paths as $P^{2}(i,j,a_r)$, $P^{2}(i,j,b_r)$, $P^{2}(i,j,c_r)$ and $P^{2}(i,j,p_i^1)$ respectively. Let $\Pi ^{h}(i,j,r)=\{P^{h}(i,j,a_r), P^{h}(i,j,b_r), P^{h}(i,j,c_r), P^{h}(i,j,p_i^{3-h})\}$ for $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$.

This completes the construction of the first phase.

4.2 Construction of the Forced Vertex Gadgets

A forced vertex gadget consists of a triangle, namely three vertices such that each vertex is adjacent to the other two vertices. Two vertices of the triangle are true twins whose degrees are exactly 2 and we call the other vertex in the triangle the connecting vertex of the gadget. When we say that we add a forced vertex gadget F to a vertex v, we mean that we create a forced vertex gadget F such that v is identified with the connecting vertex of F. For each $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$, we add a forced vertex gadget $F^{h}(i,j,a_r)$ to $N_{\pi _h}^{h}(i,j,a_r)$, $F^{h}(i,j,b_r)$ to $N_{\pi _h}^{h}(i,j,b_r)$, $F^{h}(i,j,c_r)$ to $N_{\pi _h}^{h}(i,j,c_r)$ and $F^{h}(i,j,p_i^{3-h})$ to $N_{\pi _h}^{h}(i,j,,p_i^{3-h})$ respectively.

In order to make sure that the true twins of $F^{h}(i,j,b_r)$ for $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$ do not resolve any vertex pair of $\mathcal P$, we create a path $P(\pi _i^h,a_r)$ and a path $P(\pi _i^h,c_r)$ both of length $10(n+1)$ for $i\in [n]$, $h\in \{1,2\}$ and $r\in \{1,2,3\}$.

For each $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$, we add a forced vertex gadget $F(\pi _i^h,a_r)$ to $N_{a_r}(\pi _i^h,a_r)$ and a forced vertex gadget $F(\pi _i^h,c_r)$ to $N_{c_r}(\pi _i^h,c_r)$. For each $i\in [n],j\in [m],r\in \{1,2,3\}$, we add a forced vertex gadget $F(s_i^j,a_r)$ to $N_{a_r}(s_i^j,a_r)$ and a forced vertex gadget $F(s_i^j,c_r)$ to $N_{c_r}(s_i^j,c_r)$.

Let $\text {mid}(P^{h}(i,j,p_i^{3-h}))$ be the middle vertex of $P^{h}(i,j,p_i^{3-h})$ for $i\in [n],j\in [m],h\in \{1,2\}$. In order to make sure that the true twins of $F^{h}(i,j,p_i^{3-h})$ do not resolve the vertex pair $\{p_i^{3-h},q_i^{3-h}\}$, create a path $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from $q_i^h$ to $\text {mid}(P^{3-h}(i,j,p_i^{h}))$ of length $|P^{3-h}(i,j,p_i^h)|/2+|P(s_i^j, p_i^h)|-1$. Then add a forced vertex gadget $F^{mid}(i,j,h)$ to $\text {mid}(P^{h}(i,j,p_i^{3-h}))$.

For $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$, add a forced vertex gadget $F^{ecc}(i,j,h,r)$ to the vertex $x\in P^{h}(i,j,a_r)$ such that $\text {dist}(\pi _i^h,x)=10(n+1)+1$.

For each $i\in [n],r\in \{1,2,3\}$, create two forced vertex gadgets $F^1(u_r^i,v_r^i)$ and $F^2(u_r^i,v_r^i)$ for the vertex pair $\{u_r^i,v_r^i\}\in \mathcal{P}_r$. Then create an edge from the connecting vertex of $F^1(u_r^i,v_r^i)$ to $u_r^i$, to $v_r^i$, to $N_{u_r^i}(a_r,u_r^i)$ and to $N_{u_r^i}(c_r,u_r^i)$ respectively for $i\in [n],r\in \{1,2,3\}$. Create an edge from the connecting vertex of $F^2(u_r^i,v_r^i)$ to $u_r^i$, to $v_r^i$, to the vertex x such that $x\in P(a_r,u_r^i)$ and $\text {dist}(x,u_r^i)=2$, and to the vertex y such that $y\in P(c_r,u_r^i)$ and $\text {dist}(y,u_r^i)=2$. This completes the construction of the second phase.

Finally, let $G'$ be the graph constructed by above two phases and set $k=34nm+19n$. This finishes constructing the instance $(G',k)$ of Metric Dimension. Figure 2 shows a part of $G'$.

Fig. 2

An example showing a part of $G'$. Triangles represent corresponding forced vertex gadgets. Curves or lines represent paths. We use different colors, dotted and dashed lines just to avoid the chaos caused by many crowded curves or lines. For clarity, some forced vertex gadgets do not appear on the figure

4.3 Soundness of the Reduction

First, we define the vertex sets to be used in the following parts. Recall that $X_i=\{s_i^1,...,s_i^m\}$. For every $i\in [n],r\in \{1,2,3\},h\in \{1,2\}$, let

$$\begin{aligned} U_i^h= & {} \bigcup _{j\in [m]}P(s_i^j,p_i^h),\\ H_{i,r}= & {} \bigcup _{j\in [m]}P(s_i^j,a_r)\cup P(s_i^j,b_r)\cup P(s_i^j,c_r),\\ S_i^h= & {} \bigcup _{r\in \{1,2,3\}}P(\pi _i^h,a_r)\cup P(\pi _i^h,c_r),\\ L_i^h= & {} \bigcup _{j\in [m]}P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h}))),\\ R_r= & {} \bigcup _{i\in [n]}P(a_r,u_r^i)\cup P(a_r,v_r^i)\cup P(b_r,u_r^i)\\&\quad \cup P(b_r,v_r^i)\cup P(c_r,u_r^i)\cup P(c_r,v_r^i),\text { and}\\ \Pi ^h(i,j,r)= & {} P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}). \end{aligned}$$

For every $i\in [n]$, let

$$\begin{aligned} U_i= & {} \bigcup _{h\in \{1,2\}}U_i^h \quad \quad \quad H_i=\bigcup _{r\in \{1,2,3\}}H_{i,r} \quad \quad \quad S_i=\bigcup _{h\in \{1,2\}}S_i^h\\ L_i= & {} \bigcup _{h\in \{1,2\}}L_i^h \quad \quad \quad \quad \quad \quad \Pi _i=\bigcup _{j\in [m],r\in \{1,2,3\},h\in \{1,2\}}\Pi ^h(i,j,r). \end{aligned}$$

Let $\mathcal{F}$ be the union of the vertex sets of all forced vertex gadgets, i.e. $\mathcal{F}=\bigcup _{i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}}(F(s_i^j,a_r)\cup F(s_i^j,c_r)\cup F(\pi _i^h,a_r)\cup F(\pi _i^h,c_r)\cup F^h(u_r^i,v_r^i)\cup F^{h}(i,j,a_r)\cup F^{h}(i,j,b_r)\cup F^{h}(i,j,c_r)\cup F^{h}(i,j,p_i^{3-h})\cup F^{mid}(i,j,h)\cup F^{ecc}(i,j,h,r))$.

Next we introduce a lemma about forced set gadgets and this lemma is important for the correctness of the reduction.

Lemma 4

The following three statements are true for the instance $(G',k)$.

• (a) The vertex $s_i^j$ for $i\in [n],j\in [m]$ resolves both pairs $\{p_i^1,q_i^1\}$ and $\{p_i^2,q_i^2\}$. Moreover, $s_i^j$ does not resolve any vertex pair $\{p_{i'}^h,q_{i'}^h\}$ such that $i'\in [n],h\in \{1,2\}$ and $i'\ne i$.

• (b) The vertices of any forced vertex gadget do not resolve any vertex pair of $\{\{p_i^h,q_i^h\}~|~i\in [n],h\in \{1,2\}\}$.

• (c) Any vertex $v\in V(G')\setminus (X_i\cup \mathcal{F})$ resolves at most one vertex pair of $\{\{p_i^h,q_i^h\}~|~i\in [n],h\in \{1,2\}\}$.

Proof

By the construction of $G'$, $\text {dist}(s_i^j,q_i^h)=|P(s_i^j,p_i^h)|+2=20(n+1)+2>\text {dist}(s_i^j,p_i^h)$ for $i\in [n],j\in [m]$ and $h\in \{1,2\}$. Thus any vertex of $X_i$ resolves both pairs $\{p_i^1,q_i^1\}$ and $\{p_i^2,q_i^2\}$ for $i\in [n]$. For a vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ such that $i'\ne i$, there is a shortest path from $s_i^j$ to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $c_{r'}$ and $\pi _{i'}^{h'}$ with some integer $r'\in \{1,2,3\}$. Thus a vertex $s\in X_i$ resolves exactly two vertex pairs of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$.

First we claim that vertices of $\mathcal{F}$ do not resolve any vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ for $i'\in [n],h'\in \{1,2\}$. For any vertex $v\in F^h(u_r^i,v_r^i)$ for $i\in [n],r\in \{1,2,3\},h\in \{1,2\}$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $a_r$ and $\pi _{i'}^{h'}$. Thus v does not resolve any vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ for $i'\in [n],h'\in \{1,2\}$. For any vertex $v\in F^{mid}(i,j,h)\cup F^{ecc}(i,j,h,r)$ for $i\in [n],j\in [m],h\in \{1,2\},r\in \{1,2,3\}$, we can see that $\text {dist}(v,p_{i'}^{h'})=\text {dist}(v,q_{i'}^{h'})$ with $i'=i$. There is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _i^h$, $a_r$ and $\pi _{i'}^{h'}$ with $i'\ne i$. Thus v does not resolve any vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ for $i'\in [n],h'\in \{1,2\}$. For any vertex $v\in \mathcal{F}\setminus \bigcup _{i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}}(F^h(u_r^i,v_r^i)\cup F^{ecc}(i,j,h,r)\cup F^{mid}(i,j,h))$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$ with $i'=i$. There is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $c_r$ (or $a_r$) and $\pi _{i'}^{h'}$ with $i'\ne i$. Thus v does not resolve any pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$. As a result, vertices of $\mathcal{F}$ do not resolve any vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ for $i'\in [n],h'\in \{1,2\}$.

Then we show that any vertex $v\in V(G')\setminus (X_i\cup \mathcal{F})$ resolves at most one pair of $\{p_i^1,q_i^1\}$ and $\{p_i^2,q_i^2\}$.

For a vertex $v\in U_i^h\setminus X_i$ for $i\in [n],h\in \{1,2\}$, $\text {dist}(v,p_i^h)=\text {dist}(v,q_i^h)-2<\text {dist}(v,q_i^h)$. $\text {dist}(v,q_i^{3-h})=\text {dist}(v,N_{s_i^j}(s_i^j,p_i^h))+|P^{3-h}(i,j,p_i^{h})|+1=\text {dist}(v,p_i^{3-h})$. For a vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ such that $i'\ne i$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$. Thus $v\in U_i^h\setminus X_i$ for $i\in [n],h\in \{1,2\}$ resolves exactly one vertex pair of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$.

Let $P(\text {mid}(P^{3-h}(i,j,p_i^{h})),N_{s_i^j}(s_i^j,p_i^h))$ be the subpath of $P^{3-h}(i,j,p_i^{h})$ from $\text {mid}(P^{3-h}(i,j,p_i^{h}))$ to $N_{s_i^j}(s_i^j,p_i^h)$. Let $\Lambda _i^h=(\bigcup _{j\in [m]}P(\text {mid}(P^{3-h}(i,j,p_i^{h})), N_{s_i^j}(s_i^j,p_i^h)))\setminus \{\text {mid}(P^{3-h}(i,j,p_i^{h}))~|~j\in [m]\}$. For a vertex $v\in \Lambda _i^h$ for $i\in [n],h\in \{1,2\}$, $\text {dist}(v,p_i^h)=\text {dist}(v,q_i^h)-2<\text {dist}(v,q_i^h)$. $\text {dist}(v,q_i^{3-h})=\text {dist}(v,\pi _i^{3-h})+1=\text {dist}(v,p_i^{3-h})$. For a vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ such that $i'\ne i$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$. Thus $v\in \Lambda _i^h$ for $i\in [n],h\in \{1,2\}$ resolves exactly one vertex pair of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$.

For a vertex $v\in L_i^h\setminus \{\text {mid}(P^{h}(i,j,p_i^{3-h}))~|~j\in [m]\}$ for $i\in [n],h\in \{1,2\}$, $\text {dist}(v,q_i^h)=\text {dist}(v,p_i^h)-2<\text {dist}(v,p_i^h)$. There is a shortest path from v to $p_i^{3-h}$ or $q_i^{3-h}$ going through $\pi _i^{3-h}$. For a vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ such that $i'\ne i$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$. Thus $v\in L_i^h\setminus \{\text {mid}(P^{h}(i,j,p_i^{3-h}))~|~j\in [m]\}$ for $i\in [n],h\in \{1,2\}$ resolves exactly one vertex pair of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$.

For a vertex $v\in \Pi _i\cup S_i\cup H_i\setminus (X_i\cup \Lambda _i^1\cup \Lambda _i^2)$ for $i\in [n]$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$ with $i=i',h'\in \{1,2\}$. For a vertex pair $\{p_{i'}^{h'},q_{i'}^{h'}\}$ such that $i'\ne i$, there is a shortest path from v to $p_{i'}^{h'}$ or $q_{i'}^{h'}$ going through $\pi _{i'}^{h'}$. Thus v does not resolve any vertex pair of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$.

For a vertex $v\in R_r$ for $r\in \{1,2,3\}$, there is a shortest path from v to $p_i^h$ or $q_i^h$ for $i\in [n],h\in \{1,2\}$ going through $a_r$ and $\pi _i^h$. Thus v does not resolve any vertex pair of $\{\{p_i^h,q_i^h\}:i\in [n], h\in \{1,2\}\}$. This completes the proof for the lemma. $\square$

By the properties of true twins, we need to choose exactly one vertex of the true twins (arbitrarily) of every forced vertex gadget in the resolving set of $G'$, which we call a forced vertex. For convenience, we use $f(\cdot )$ to represent the chosen forced vertex of the corresponding gadget $F(\cdot )$. Then we have the following lemma.

Lemma 5

The forced vertices do not resolve any vertex pair $\{u_r^i,v_r^i\}\in \mathcal P$ for $r\in \{1,2,3\}$ and $i\in [n]$.

Proof

We fix arbitrary integers $i\in [n],j\in [m],r\in \{1,2,3\},h\in \{1,2\}$. For the forced vertex $f^{h}(i,j,a_r)$, $\text {dist}(f^{h}(i,j,a_r),u_{r'}^{i'})=2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|=2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},v_{r'}^{i'})|=\text {dist}(f^{h}(i,j,a_r),v_{r'}^{i'})$ for $i'\in [n], r'\in \{1,2,3\}$. Thus $f^{h}(i,j,a_r)$ does not resolve any vertex pair of $\mathcal P$. Similarly, the forced vertices $f^{h}(i,j,b_r)$, $f^{h}(i,j,c_r)$ and $f^{h}(i,j,p_i^{3-h})$ do not resolve any vertex pair of $\mathcal P$. For the forced vertex $f^{mid}(i,j,h)$, $\text {dist}(f^{mid}(i,j,h),u_{r'}^{i'})=\text {dist}(f^{mid}(i,j,h),v_{r'}^{i'})=|P^h(i,j,p_i^{3-h})|/2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|$. Thus $f^{mid}(i,j,h)$ does not resolve any vertex pair of $\mathcal P$. For the forced vertex $f^{ecc}(i,j,h,r)$, $\text {dist}(f^{ecc}(i,j,h,r),u_{r'}^{i'})=\text {dist}(f^{ecc}(i,j,h,r),v_{r'}^{i'})=10(n+1)+1+|P(\pi _i^h,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|$. Thus $f^{ecc}(i,j,h,r)$ does not resolve any vertex pair of $\mathcal P$.

We fix arbitrary integers $i\in [n],j\in [m],r\in \{1,2,3\}$. For the forced vertex $f(s_i^j,a_r)$, $\text {dist}(f(s_i^j,a_r),u_r^{i'})=2+|P(a_r,u_r^{i'})|=2+|P(a_r,v_r^{i'})|=\text {dist}(f(s_i^j,a_r),v_r^{i'})$ for $i'\in [n]$. For the forced vertex $f(s_i^j,c_r)$, $\text {dist}(f(s_i^j,c_r),u_r^{i'})=2+|P(c_r,u_r^{i'})|=2+|P(c_r,v_r^{i'})|=\text {dist}(f(s_i^j,c_r),v_r^{i'})$ for $i'\in [n]$. Thus $f(s_i^j,a_r)$ and $f(s_i^j,c_r)$ do not resolve any vertex pair of $\mathcal{P}_r$. Similarly, $f(\pi _i^h,a_r)$ and $f(\pi _i^h,c_r)$ for $i\in [n],h\in \{1,2\},r\in \{1,2,3\}$ do not resolve any vertex pair of $\mathcal{P}_r$. For vertex pairs of $\mathcal{P}_{r'}$ with $r'\in \{1,2,3\}$ and $r'\ne r$, $\text {dist}(f(s_i^j,a_r),u_{r'}^{i'})=2+|P(a_r,\pi _i^1)|+|P(a_{r'},\pi _i^1)|+|P(a_{r'},u_r^{i'})|=2+|P(a_r,\pi _i^1)|+|P(a_{r'},\pi _i^1)|+|P(a_{r'},v_r^{i'})| =\text {dist}(f(s_i^j,a_r),v_{r'}^{i'})$ for $i'\in [n]$. $\text {dist}(f(s_i^j,c_r),u_{r'}^{i'})=2+|P(c_r,\pi _i^1)|+|P(a_{r'},\pi _i^1)|+|P(a_{r'},u_r^{i'})|=2+|P(c_r,\pi _i^1)|+|P(a_{r'},\pi _i^1)|+|P(a_{r'},v_r^{i'})| =\text {dist}(f(s_i^j,a_r),v_{r'}^{i'})$ for $i'\in [n]$. Thus $f(s_i^j,a_r)$ and $f(s_i^j,c_r)$ do not resolve any vertex pair of $\mathcal{P}_{r'}$.

We fix arbitrary integers $i\in [n],r\in \{1,2,3\}$. For the forced vertex $f^1(u_r^i,v_r^i)$ or $f^2(u_r^i,v_r^i)$, obviously it does not resolve the vertex pair $\{u_r^i,v_r^i\}$. For a vertex pair $\{u_r^{i'},v_r^{i'}\}$ with $i'\in [n]\text { and }i'\ne i$, $\text {dist}(f^1(u_r^i,v_r^i),u_r^{i'})=2+|P(a_r,u_r^i)|-1+|P(a_r,u_r^{i'})|=2+|P(a_r,u_r^i)|-1+|P(a_r,v_r^{i'})|=\text {dist}(f^1(u_r^i,v_r^i),v_r^{i'})$. For a vertex pair $\{u_{r'}^{i'},v_{r'}^{i'}\}$ with $i'\in [n]$ and $r'\in \{1,2,3\}\text { and }r'\ne r$, $\text {dist}(f^1(u_r^i,v_r^i),u_{r'}^{i'})=2+|P(a_r,u_r^i)|-1+|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|=\text {dist}(f^1(u_r^i,v_r^i),v_{r'}^{i'})$. As a result, $f^1(u_r^i,v_r^i)$ does not resolve any vertex pair of $\mathcal P$. For a vertex pair $\{u_r^{i'},v_r^{i'}\}$ with $i'\in [n]\text { and }i'\ne i$, $\text {dist}(f^2(u_r^i,v_r^i),u_r^{i'})=2+|P(a_r,u_r^i)|-2+|P(a_r,u_r^{i'})|=2+|P(a_r,u_r^i)|-2+|P(a_r,v_r^{i'})|=\text {dist}(f^2(u_r^i,v_r^i),v_r^{i'})$. For a vertex pair $\{u_{r'}^{i'},v_{r'}^{i'}\}$ with $i'\in [n]$, $r'\in \{1,2,3\}\text { and }r'\ne r$, $\text {dist}(f^2(u_r^i,v_r^i),u_{r'}^{i'})=2+|P(a_r,u_r^i)|-2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|=\text {dist}(f^2(u_r^i,v_r^i),v_{r'}^{i'})$. As a result, $f^2(u_r^i,v_r^i)$ does not resolve any vertex pair of $\mathcal P$. This completes the proof for the lemma. $\square$

Lemma 6

If $G'$ has a resolving set of size at most $34nm+19n$, then $(G,n,\chi ,\mathcal P)$ is a yes-instance.

Proof

Suppose that $\mathcal S$ is a resolving set for $G'$ of size at most $34nm+19n$. Let $\hat{\mathcal{S}}=\mathcal{S}\cap X$. (Recall that $X=\bigcup \limits _{i=1}^{n}\{s_i^1,...,s_i^m\}$.) We claim that $\hat{\mathcal{S}}$ is solution for $(G,n,\chi ,\mathcal P)$. Note that for the true twins $\{u,u'\}$ of a forced vertex gadget, no vertex resolves the vertex pair $\{u,u'\}$ except u (or $u'$). It follows that $\mathcal S$ contains $34nm+18n$ forced vertices since there are $34nm+18n$ forced vertex gadgets in $G'$. Since X has no intersection with the vertex set of all forced vertex gadgets, $|\hat{\mathcal{S}}|\le n$. By Lemma 4, we get that $|\hat{\mathcal{S}}\cap X_i|=1$ for each $i\in [n]$. Thus $|\hat{\mathcal{S}}|=n$. By Lemma  5 and the assumption that $\mathcal S$ is a resolving set for $G'$, $\hat{\mathcal{S}}$ resolves every pair $\{u_r^i,v_r^i\}$ in $G'$ for $r\in \{1,2,3\}$ and $i\in [n]$. We can check that the distance between $s_i^j$ and $u_r^{i'}$ in $G'$ (and the distance between $s_i^j$ and $v_r^{i'}$ in $G'$) for $i\in [n],j\in [m],i'\in [n],r\in \{1,2,3\}$ is the same as that in G. Thus $\hat{\mathcal{S}}$ is a solution for $(G,n,\chi ,\mathcal P)$. $\square$

4.4 Treewidth Bound of the Graph

Since the completeness proof takes a large amount of space, before proceeding to that, we first show that $G'$ is of constant treewidth. In fact, we will prove a slightly stronger statement that $G'$ is of constant pathwidth by giving a search strategy with a constant number of searchers.

Lemma 7

The pathwidth of $G'$ is at most $24$.

Proof

Following the characterization of pathwidth by Kirousis and Papadimitriou [12], we give a search strategy with 25 searchers. First, we put 9 searchers on $\bigcup _{r\in \{1,2,3\}}\{a_r,b_r,c_r\}$. The 9 searchers remain there until the end of the whole searching process. The searching process consists of two phases. We search the “left” part of $G'$ in the first phase and the “right” part of $G'$ in the second phase.

The first phase of the searching process consists of n rounds. At the beginning of the i-th round ($i\in [n]$), we put 6 searchers on $\bigcup _{h\in \{1,2\}}\{p_i^h,q_i^h,\pi _i^h\}$. Here when we say that we clean a path, this means that there are already two searchers guarding at the endpoints (or the neighbor of the endpoints) of this path and we use 3 extra searchers x, y, z such that x, y move alternately from one end of the path to the other end to clean the edges of the path. When a searcher, say x arrives at the connecting point of a forced vertex gadget, we put y, z on the true twins of this forced vertex gadget to clean the edges of this gadget and then after removing y, z, put y ahead of x to continue the alternating process unless x reaches the endpoint of this path. Then for each $j\in [m]$, we

• put 5 vertices on $N_{G'}(s_i^j)$.

• put 2 vertices on $\text {mid}(P^h(i,j,p_i^{3-h}))$ for $h\in \{1,2\}$.

• use 3 extra searchers to clean the paths $P(s_i^j,p_i^h)$ for $h\in \{1,2\}$, the paths $P(s_i^j,a_r)$, $P(s_i^j,b_r)$, $P(s_i^j,c_r)$ for $r\in \{1,2,3\}$, the paths $P^{h}(i,j,a_r)$, $P^{h}(i,j,b_r)$, $P^{h}(i,j,c_r)$, $P^{h}(i,j,p_i^{3-h})$ for $h\in \{1,2\},r\in \{1,2,3\}$, the paths $P(\pi _i^h,a_r)$, $P(\pi _i^h,c_r)$ for $h\in \{1,2\},r\in \{1,2,3\}$ and the path $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ for $h\in \{1,2\}$ successively (including all forced vertex gadgets attached to the vertices on these paths).

• remove the above 10 searchers that are still on the graph.

At the end of the i-th round, we remove the 6 searchers on $\bigcup _{h\in \{1,2\}}\{p_i^h,q_i^h,\pi _i^h\}$.

The second phase of the searching process consists of 3 rounds. During the r-th round ($r\in \{1,2,3\}$), we operate as follows. For each $i\in [n]$, we

• put 4 searchers on $u_r^i$, $v_r^i$ and the connecting point of $F^h(u_r^i,v_r^i)$ for $h\in \{1,2\}$.

• use 2 extra searchers to clean the paths $P(a_r,u_r^i),P(b_r,u_r^i),P(c_r,u_r^i),P(a_r,v_r^i), P(b_r,v_r^i)$ and $P(c_r,v_r^i)$ (including the forced vertex gadgets $F^h(u_r^i,v_r^i)$ for $h\in \{1,2\}$ and the incident edges of the connecting vertex of $F^h(u_r^i,v_r^i)$).

• remove the above 6 searchers that are still on the graph.

This completes the description of the the search strategy.

As a result, the node search number of $G'$ is at most 25. It follows that the pathwidth of $G'$ is at most $24$. $\square$

5 Completeness of the Reduction

Since the proof of completeness for the reduction from n -Multicolored Resolving Set to metric dimension takes up a large amount of space, we put it in a separate section.

For every forced vertex gadget of $G'$, we choose a vertex from the true twins arbitrarily as a forced vertex and let the set of all chosen forced vertices be F. In this section, we show that if $(G,n,\chi ,\mathcal P)$ has a solution $\mathcal{S}$, then $\mathcal{S}'=\mathcal{S}\cup F$ is a resolving set of size at most $34nm+19n$ for $G'$. Formally, we will prove the following lemma.

Lemma 8

(Completeness) If $(G,n,\chi ,\mathcal P)$ is a yes-instance, then $G'$ has a resolving set of size at most $34nm+19n$.

The proof of Lemma 8 consists of a list of lemmas. Suppose that $V(G')=V_1\cup V_2\cup ...\cup V_t$. Our general method is to show that for each $i\in [t]$,

• (i) every internal vertex pair of $V_i$ is resolved by $\mathcal{S}'$

• (ii) every vertex pair of $V_{i'}\times V_i$ for each $i'<i$ is resolved by $\mathcal{S}'$.

Note that when we mention the vertex pairs of $V_{i'}\times V_i$, we ignore the vertex pairs with two identical vertices by default as it’s meaningless in our problem. Let $U=\bigcup _{i\in [n]}U_i,\Pi =\bigcup \nolimits _{i\in [n]}\Pi _i,H=\bigcup _{i\in [n]}H_i,S=\bigcup _{i\in [n]}S_i,L=\bigcup _{i\in [n]}L_i$ and $R=\bigcup _{r\in \{1,2,3\}}R_r$. Table 1 shows the indexes of the corresponding lemmas.

Table 1 Indexes of the lemmas for the completeness of the reduction

First of all, We have the following claim.

Claim 1

Every vertex pair $\{u_r^{i'},v_r^{i'}\}$ in $G'$ for $r\in \{1,2,3\}, i'\in [n]$ is resolved by $\mathcal{S}'$.

Proof

Since $(G,n,\chi ,\mathcal P)$ is a yes-instance, $\text {dist}_{G}(s_i^j,u_r^{i'})=\text {dist}_{G'}(s_i^j,u_r^{i'})$, $\text {dist}_{G}(s_i^j,v_r^{i'})=\text {dist}_{G'}(s_i^j,v_r^{i'})$ for $i,i'\in [n],j\in [m],r\in \{1,2,3\}$, every vertex pair $\{u_r^{i'},v_r^{i'}\}$ in $G'$ for $r\in \{1,2,3\}$ and $i'\in [n]$ is resolved by some vertex of $\mathcal{S}\subset \mathcal{S}'$. $\square$

Lemma 9 shows that every vertex pair with at least one vertex from a forced vertex gadget is resolved by the solution $\mathcal{S}'$.

Lemma 9

For any vertex $v_f\in \mathcal{F}$, every vertex pair $\{x,y\}\in \{v_f\}\times V(G')\setminus \{v_f\}$ is resolved by $\mathcal{S}'$.

Proof

Without loss of generality, suppose that $v_1,v_2,v_c\in F^1(u_r^i,v_r^i)$ for some $r\in \{1,2,3\},i\in [n]$, where $v_c$ is the connecting vertex of $F^1(u_r^i,v_r^i)$, $v_1,v_2$ are the true twins and $v_1\in \mathcal{S}'$. Then obviously every vertex pair of $\{v_1\}\times V(G')\setminus \{v_1\}$ is resolved by $v_1$. Every vertex pair of $\{v_2\}\times V(G')\setminus \{v_2\}$ is resolved $v_1$ except the vertex pair $\{v_2,v_c\}$. Let $w_f$ be an arbitrary vertex of $\mathcal{S}'\setminus F^1(u_r^i,v_r^i)$. Then there is a shortest path from $w_f$ to $v_2$ going through $v_c$. Thus $\text {dist}(w_f,v_2)=\text {dist}(w_f,v_c)+1$ and $\{v_2,v_c\}$ is resolved by $w_f$. For any vertex $u\in V(G')\setminus F^1(u_r^i,v_r^i)$, $\text {dist}(v_1,u)>\text {dist}(v_1,v_c)=1$. Then the correctness of the lemma follows. $\square$

5.1 Internal Vertex Pairs of the Vertex Sets

In this subsection, we prove Lemmas 10 - 15 in Table 1.

Lemma 10

Every pair of distinct vertices $x,y\in \bigcup _{i\in [n],h\in \{1,2\}}U_i^h$ is resolved by $\mathcal{S}'$.

Proof

First, we show that every pair of distinct vertices $x,y\in \bigcup _{h\in \{1,2\}}U_i^h$ for $i\in [n]$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m]$ and $h\in \{1,2\}$ such that $j'\ne j$.

Suppose that $x,x'\in P(s_i^j,p_i^h)$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(s_i^j,x)$ be the subpath of $P(s_i^j,p_i^h)$ from $s_i^j$ to x and $|P(s_i^j,x)|=\ell _x$. Since $\text {dist}(f^h(i,j',a_1),x)=3+20(n+1)-\ell _x$, $f^h(i,j',a_1)$ resolves every pair $\{x,x'\}$ such that $\ell _x\ne \ell _{x'}$.

Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(s_i^{j'},p_i^h)$ such that $j'\in [m]$ and $j'\ne j$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the second paragraph. $\text {dist}(f^{mid}(i,j,3-h),x)=10(n+1)+\ell _x$ if $\ell _x\ge 1$ and $\text {dist}(f^{mid}(i,j,3-h),x)=10(n+1)+2$ if $\ell _x=1$. $\text {dist}(f^{mid}(i,j,3-h),y)=\text {min }(2+|P^{3-h}(i,j,p_i^h)|/2+|P(s_i^{j'},p_i^{3-h})|+\ell _y,|P^{3-h}(i,j,p_i^h)|/2+|P(s_i^j,p_i^h)|+|P(s_i^{j'},p_i^h)|-\ell _y)=\text {min }(2+30(n+1)+\ell _y,50(n+1)-\ell _y)\ge 30(n+1)\ge \text {dist}(f^{mid}(i,j,3-h),x)$ and the equalities hold if and only if $x=y=p_i^h$. Thus every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$.

Suppose that $x\in P(s_i^j,p_i^h)\setminus \{s_i^j\}$ and $y\in P(s_i^j,p_i^{3-h})\setminus \{s_i^j\}$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the second paragraph. Then $\text {dist}(f^h(i,j',a_1),x)=3+20(n+1)-\ell _x\le 2+20(n+1)$ and $\text {dist}(f^h(i,j',a_1),y)=\text {min }(1+|P^h(i,j,p_i^{3-h})|+\ell _y,3+|P(\pi _i^h,c_1)|+|P(\pi _i^{3-h},c_1)|+|P(s_i^j,p_i^{3-h})|-\ell _y)=\text {min }(1+20(n+1)+\ell _y,3+40(n+1)-\ell _y)\ge 2+20(n+1)$. We see from the two equations that $\text {dist}(f^h(i,j,a_1),x)\ne \text {dist}(f^h(i,j,a_1),y)$ unless $\ell _x=\ell _y=1$. We can check that $f^h(i,j,p_i^{3-h})$ resolves the pair $\{x,y\}$ with $\ell _x=\ell _y=1$. Thus every pair $\{x,y\}$ is resolved by $f^h(i,j',a_1)$ or $f^h(i,j,p_i^{3-h})$.

Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(s_i^{j'},p_i^{3-h})$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the second paragraph. Then $\text {dist}(f^{mid}(i,j,h),x)=\text {min }(2+|P^h(i,j,p_i^{3-h})|/2+\ell _x,2+|P^h(i,j,p_i^{3-h})|/2+|P(s_i^j,p_i^h)|-\ell _x)=\text {min }(2+10(n+1)+\ell _x,2+30(n+1)-\ell _x)\le 2+20(n+1)$. $\text {dist}(f^{mid}(i,j,h),y)=\text {min }(|P^h(i,j,p_i^{3-h})|/2+|P(s_i^j,p_i^{3-h})|+|P(s_i^{j'},p_i^{3-h})|-\ell _y,2+|P^h(i,j,p_i^{3-h})|/2+|P(s_i^{j'},p_i^h)|+\ell _y)=\text {min }(50(n+1)-\ell _y,2+30(n+1)+\ell _y)\ge 2+30(n+1)$. Thus every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,h)$.

Finally we show that every pair of distinct vertices $\{x,y\}\in \bigcup _{h\in \{1,2\}}U_i^h\times \bigcup _{h'\in \{1,2\}}U_{i'}^{h'}$ with $i,i'\in [n]$ and $i\ne i'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n], j,j'\in [m]$ and $h,h'\in \{1,2\}$ such that $i\ne i'$. Let $x\in P(s_i^j,p_i^h)$ and $y\in P(s_{i'}^{j'},p_{i'}^{h'})$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the second paragraph. Then as we show in last paragraph, $\text {dist}(f^{mid}(i,j,h),x)=\text {min }(2+10(n+1)+\ell _x,2+30(n+1)-\ell _x)\le 2+20(n+1)$. $\text {dist}(f^{mid}(i,j,h),s_{i'}^{j'})=\text {min}_{r\in \{1,2,3\}}(1+|P^h(i,j,p_i^{3-h})|/2+|P(\pi _i^h,c_r)|+|P(c_r,s_{i'}^{j'})|)$. $\text {dist}(f^{mid}(i,j,h),y)= \text {min }(\text {dist}(f^{mid}(i,j,h),s_{i'}^{j'})+\ell _y,2+|P^h(i,j,p_i^{3-h})|/2+|P(\pi _i^h,c_1)|+|P(\pi _{i'}^{h'},c_1)|+|P(s_{i'}^{j'},p_{i'}^{h'})|-\ell _y)> 1+30(n+1)>\text {dist}(f^{mid}(i,j,h),x)$. Thus every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,h)$. This completes the proof for the lemma. $\square$

Lemma 11

Every pair of distinct vertices $x,y\in \bigcup _{i\in [n],r\in \{1,2,3\}}H_{i,r}$ is resolved by $\mathcal{S}'$.

Proof

First we show that every vertex pair of $H_{i,r}\times H_{i',r}$ such that $i',i\in [n]$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j\in [m]$ and $r\in \{1,2,3\}$.

Given two distinct vertices $x_1,x_2\in P(s_i^j,a_r)$, we can verify that $f(\pi _i^1,a_r)$ resolves the pair $\{x_1,x_2\}$. Similarly, two distinct vertices $x'_1,x'_2\in P(s_i^j,c_r)$ are distinguished by $f(\pi _i^1,c_r)$. Suppose that $x\in P(s_i^j,a_r)\setminus \{s_i^j\}$, $y\in P(s_i^j,b_r)\setminus \{s_i^j\}$ and $z\in P(s_i^j,c_r)\setminus \{s_i^j\}$. Let $P(s_i^j,x)$, $P(s_i^j,y)$ and $P(s_i^j,z)$ be the subpath of $P(s_i^j,a_r)$, $P(s_i^j,b_r)$ and $P(s_i^j,c_r)$ respectively. Let $|P(s_i^j,x)|=\ell _x$, $|P(s_i^j,y)|=\ell _y$ and $|P(s_i^j,z)|=\ell _z$. Similarly, for a vertex $y'\in P(s_i^j,b_r)$, we define $|P(s_i^j,y')|=\ell _{y'}$. Since $\text {dist}(f^{mid}(i,j,1),y)=2+|P^{1}(i,j,p_i^{2})|/2+\ell _y$ and $\text {dist}(f^{mid}(i,j,1),y')=2+|P^{1}(i,j,p_i^{2})|/2+\ell _{y'}$, two distinct vertices y and $y'$ are distinguished by $f^{mid}(i,j,1)$. $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x$. $\text {dist}(f(\pi _i^1,a_r),b_r)=\text {min}_{j'\in [m]}(2+|P(s_i^{j'},a_r)|+|P(s_i^{j'},b_r)|)=2+20(n+1)+10+20(n+1)+5$. $\text {dist}(f(\pi _i^1,a_r),y)=\text {min }(2+|P(s_i^j,a_r)|+\ell _y,\text {dist}(f(\pi _i^1,a_r),b_r)+|P(s_i^j,b_r)|-\ell _y)$. For a vertex pair $\{x,y\}$ such that $\text {dist}(f(\pi _i^1,a_r),y)=2+|P(s_i^j,a_r)|+\ell _y$, obviously the pair is resolved by $f(\pi _i^1,a_r)$. For a vertex pair $\{x,y\}$ such that $\text {dist}(f(\pi _i^1,a_r),y)=\text {dist}(f(\pi _i^1,a_r),b_r)+|P(s_i^j,b_r)|-\ell _y$, $\text {dist}(f(\pi _i^1,a_r),y)\ge 40(n+1)+17>\text {dist}(f(\pi _i^1,a_r),x)$. Thus every pair $\{x,y\}$ is resolved by $f(\pi _i^1,a_r)$. Similarly, every pair $\{y,z\}$ is resolved by $f(\pi _i^1,c_r)$. For a vertex pair $\{x,z\}$, $\text {dist}(f(\pi _i^1,c_r),z)=2+|P(s_i^j,c_r)|-\ell _z<20(n+1)$ if $z\ne c_r$ and $\text {dist}(f(\pi _i^1,c_r),c_r)=2$. $\text {dist}(f(\pi _i^1,c_r),x)=\text {min }(2+|P(s_i^j,c_r)|+\ell _x,|P(\pi _i^1,c_r)|+|P(\pi _i^1,a_r)|+|P(s_i^j,a_r)|-\ell _x)\ge 2+|P(s_i^j,c_r)|>\text {dist}(f(\pi _i^1,c_r),z)$. Thus every pair $\{x,z\}$ is resolved by $f(\pi _i^1,c_r)$.

Let $i'\in [n],j'\in [m]$ be integers such that $i'\ne i$ or $j'\ne j$. Suppose that $x\in P(s_i^j,a_r)\setminus \{a_r\}$, $y\in P(s_i^j,b_r)\setminus \{b_r\}$ and $z\in P(s_i^j,c_r)\setminus \{c_r\}$. Suppose that $x'\in P(s_{i'}^{j'},a_r)\setminus \{a_r\}$, $y'\in P(s_{i'}^{j'},b_r)\setminus \{b_r\}$ and $z'\in P(s_{i'}^{j'},c_r)\setminus \{c_r\}$. We define $\ell _x$, $\ell _y$, $\ell _z$, $\ell _{x'}$, $\ell _{y'}$ and $\ell _{z'}$ in a similar way to that of $\ell _{x}$ in the second paragraph. For a pair $\{x,x'\}$, since $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x$ and $\text {dist}(f(\pi _i^1,a_r),x')=2+|P(s_{i'}^{j'},a_r)|-\ell _{x'}$, $f(\pi _i^1,a_r)$ resolves every pair $\{x,x'\}$ such that $|P(s_i^j,a_r)|-\ell _x \ne |P(s_{i'}^{j'},a_r)|-\ell _{x'}$. Since $\text {dist}(f(s_i^j,a_r),x)=|P(s_i^j,a_r)|-\ell _x$ and $\text {dist}(f(s_i^j,a_r),x')=2+|P(s_{i'}^{j'},a_r)|-\ell _{x'}$, $f(s_i^j,a_r)$ resolves every pair $\{x,x'\}$ such that $|P(s_i^j,a_r)|-\ell _x=|P(s_{i'}^{j'},a_r)|-\ell _{x'}$. As a result, every pair $\{x,x'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. Similarly, every pair $\{z,z'\}$ is resolved by $f(\pi _i^1,c_r)$ or $f(s_i^j,c_r)$. For a pair $\{y,y'\}$, there are two cases. Case 1: $i=i'$ and $j\ne j'$. $\text {dist}(f^{mid}(i,j,1),y)=2+|P^{1}(i,j,p_i^{2})|/2+\ell _y$. $\text {dist}(f^{mid}(i,j,1),y')=\text {min }(2+|P^{1}(i,j,p_i^{2})|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _{y'},1+|P^{1}(i,j,p_i^{2})|/2+|P^1(i',j',b_r)|+\ell _{y'}-1)$ if $y'\ne s_{i'}^{j'}$ and $\text {dist}(f^{mid}(i,j,1),s_{i'}^{j'})=2+30(n+1)$. If a pair $\{y,y'\}$ satisfies that $\text {dist}(f^{mid}(i,j,1),y')=2+|P^{1}(i,j,p_i^{2})|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _{y'}$, obviously $f^{mid}(i,j,1)$ resolves this pair. Thus if a pair $\{y,y'\}$ is not resolved by $f^{mid}(i,j,1)$, then we have $\text {dist}(f^{mid}(i,j,1),y)=2+10(n+1)+\ell _y=\text {dist}(f^{mid}(i,j,1),y')=30(n+1)+\ell _{y'}$, i.e. $\ell _y-\ell _{y'}=20(n+1)-2$. For this pair, $\text {dist}(f^{mid}(i',j',1),y')=2+10(n+1)+\ell _{y'}<\text {dist}(f^{mid}(i',j',1),y)=\text {min }(2+10(n+1)+|P(s_{i'}^{j'},b_r)|+|P(s_i^j,b_r)|-\ell _y,30(n+1)+\ell _y)$. Thus in this case, every pair $\{y,y'\}$ is resolved by $f^{mid}(i,j,1)$ or $f^{mid}(i',j',1)$. Case 2: $i\ne i'$. $\text {dist}(f^{mid}(i,j,1),y)=2+|P^{1}(i,j,p_i^{2})|/2+\ell _y$. $\text {dist}(f^{mid}(i,j,1),s_{i'}^{j'})=1+|P^{1}(i,j,p_i^{2})|/2+\text {min}_{r'\in \{1,2,3\}}(|P(\pi _i^1,c_{r'})|+|P(s_{i'}^{j'},c_{r'})|)$. $\text {dist}(f^{mid}(i,j,1),y')=\text {min }(2+|P^{1}(i,j,p_i^{2})|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _{y'},\text {dist}(f^{mid}(i,j,1),s_{i'}^{j'})+\ell _{y'})$. If a pair $\{y,y'\}$ satisfies that $\text {dist}(f^{mid}(i,j,1),y')=2+|P^{1}(i,j,p_i^{2})|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _{y'}$, obviously $f^{mid}(i,j,1)$ resolves this pair. Thus if a pair $\{y,y'\}$ is not resolved by $f^{mid}(i,j,1)$, then we have $\text {dist}(f^{mid}(i,j,1),y)=2+10(n+1)+\ell _y=\text {dist}(f^{mid}(i,j,1),y')=\text {dist}(f^{mid}(i,j,1),s_{i'}^{j'})+\ell _{y'}$, i.e. $\ell _y-\ell _{y'}=\text {dist}(\pi _i^1,s_{i'}^{j'})-1$. For this pair, $\text {dist}(f^{mid}(i',j',1),y')=2+10(n+1)+\ell _{y'}<\text {dist}(f^{mid}(i',j',1),y)=\text {min }(2+10(n+1)+|P(s_{i'}^{j'},b_r)|+|P(s_i^j,b_r)|-\ell _y, \text {dist}(f^{mid}(i',j',1),s_i^j)+\ell _y)$. Thus in this case, every pair $\{y,y'\}$ is resolved by $f^{mid}(i,j,1)$ or $f^{mid}(i',j',1)$. It follows that every pair $\{y,y'\}$ is resolved by $f^{mid}(i,j,1)$ or $f^{mid}(i',j',1)$. For a pair $\{x,y'\}$, there are two cases. Case 1: $|P(s_i^j,a_r)|>20(n+1)+10\cdot 1=\min _{\alpha \in [m]}|P(s_i^{\alpha },a_r)|$. Then $\text {dist}(f(\pi _i^1,a_r),y')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{y'},2+20(n+1)+10\cdot 1+20(n+1)+5\cdot 1+1+|P(s_{i'}^{j'},b_r)|-\ell _{y'})=\text {dist}(f(s_i^j,a_r),y')$ and $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x=\text {dist}(f(s_i^j,a_r),x)+2$. In this case, $\{x,y'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. Case 2: $|P(s_i^j,a_r)|=20(n+1)+10\cdot 1=\min _{p\in [m]}|P(s_i^p,a_r)|$. Then $\text {dist}(f(s_i^j,a_r),x)\le 20(n+1)+10<\text {dist}(f(s_i^j,a_r),y')$. Thus in this case, $\{x,y'\}$ is resolved by $f(s_i^j,a_r)$. It follows that every pair $\{x,y'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. For a pair $\{x,z'\}$, $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x=\text {dist}(f(s_i^j,a_r),x)+2$, and $\text {dist}(f(\pi _i^1,a_r),z')= min (2+|P(s_{i'}^{j'},a_r)|+\ell _{z'}, |P(\pi _i^1,a_r)|+|P(\pi _i^1,c_r)|+|P(s_{i'}^{j'},c_r)|-\ell _{z'})\le \text {dist}(f(s_i^j,a_r),z')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{z'},2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,c_r)|+|P(s_{i'}^{j'},c_r)|-\ell _{z'})$. It follows that every pair $\{x,z'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. For a pair $\{y,z'\}$, there are two cases. Case 1: $|P(s_{i'}^{j'},c_r)|+|P(s_{i'}^{j'},b_r)|>20(n+1)-10n+20(n+1)+5n+1=\min _{\alpha \in [m]}{(|P(s_{i'}^{\alpha },c_r)|+|P(s_{i'}^{\alpha },b_r)|)}$. Then $\text {dist}(f(\pi _i^1,c_r),y)=\text {min }(2+|P(s_i^j,c_r)|+\ell _y,3+40(n+1)-5n+|P(s_i^j,b_r)|-\ell _y)=\text {dist}(f(s_{i'}^{j'},c_r),y)$ and $\text {dist}(f(\pi _i^1,c_r),z')=2+|P(s_{i'}^{j'},c_r)|-\ell _{z'}=\text {dist}(f(s_{i'}^{j'},c_r),z')+2$. In this case, $\{y,z'\}$ is resolved by $f(\pi _i^1,c_r)$ or $f(s_{i'}^{j'},c_r)$. Case 2: $|P(s_{i'}^{j'},c_r)|+|P(s_{i'}^{j'},b_r)|=20(n+1)-10n+20(n+1)+5n+1$. Then $\text {dist}(f(s_{i'}^{j'},c_r),y)\ge 2+20(n+1)-10n>\text {dist}(f(s_{i'}^{j'},c_r),z')$. It follows that every pair $\{y,z'\}$ is resolved by $f(\pi _i^1,c_r)$ or $f(s_{i'}^{j'},c_r)$. This completes the proof to show that every vertex pair of $H_{i,r}\times H_{i',r}$ such that $i',i\in [n]$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$.

Next we show that every vertex pair of $H_{i,r}\times H_{i',r'}$ such that $i,i'\in [n]$, $r,r'\in \{1,2,3\}$ and $r\ne r'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m]$ and $r,r'\in \{1,2,3\}$ such that $r\ne r'$. Suppose that $x\in P(s_i^j,a_r)$, $y\in P(s_i^j,b_r)$, $z\in P(s_i^j,c_r)$, $x'\in P(s_{i'}^{j'},a_{r'})$, $y'\in P(s_{i'}^{j'},b_{r'})$ and $z'\in P(s_{i'}^{j'},c_{r'})$. We define $\ell _x$, $\ell _y$, $\ell _z$, $\ell _{x'}$, $\ell _{y'}$ and $\ell _{z'}$ in a similar way to that of $\ell _{x}$ in the second paragraph. For a vertex pair $\{x,x'\}$, there are two cases. Case 1: $i=i'$ and $j=j'$. Then $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x$, $\text {dist}(f(\pi _i^1,a_r),x')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{x'},|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(s_{i'}^{j'},a_r)|-\ell _{x'})$. $\text {dist}(f(s_i^j,a_r),x)=|P(s_i^j,a_r)|-\ell _x$ when $x\ne a_r$ and $\text {dist}(f(s_i^j,a_r),a_r)=1$. $\text {dist}(f(s_i^j,a_r),x')=\text {min }(|P(s_i^j,a_r)|+\ell _{x'},2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(s_i^j,a_{r'})|-\ell _{x'})$. Thus for the vertex pair $\{x,x'\}$ which is not resolved by $f(s_i^j,a_r)$, i.e.,$\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),x')=2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(s_i^j,a_{r'})|-\ell _{x'}$, it satisfies that $\text {dist}(f(\pi _i^1,a_r),x)>\text {dist}(f(s_i^j,a_r),x)$ and $\text {dist}(f(\pi _i^1,a_r),x')<\text {dist}(f(s_i^j,a_r),x')$. Thus in this case, every pair every pair $\{x,x'\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^1,a_r)$. Case 2: $i\ne i'$ or $j\ne j'$. $\text {dist}(f(s_i^j,a_r),x)=|P(s_i^j,a_r)|-\ell _x$ when $x\ne a_r$ and $\text {dist}(f(s_i^j,a_r),a_r)=1$. $\text {dist}(f(s_i^j,a_r),x')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{x'},2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,a_{r'})|+|P(s_{i'}^{j'},a_{r'})|-\ell _{x'})$. For the vertex pair $\{x,x'\}$ which is not resolved by $f(s_i^j,a_r)$, i.e., $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),x')$, it satisfies that $\text {dist}(f(\pi _i^1,a_r),x)>\text {dist}(f(s_i^j,a_r),x)$ and $\text {dist}(f(\pi _i^1,a_r),x')\le \text {dist}(f(s_i^j,a_r),x')$. Thus in this case, every pair every pair $\{x,x'\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^1,a_r)$. It follows that every pair $\{x,x'\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^1,a_r)$. For a vertex pair $\{z,z'\}$, similarly it is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^1,c_r)$. For a vertex pair $\{y,y'\}$, let $\{u_r^{i_r},v_r^{i_r}\}$ be the vertex pair resolved by $s_i^j$, i.e. $|P(s_i^j,b_r)|=20(n+1)+5i_r+1$. Then $\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),y)=40(n+1)+1-\ell _y=\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),y)$ when $y\ne s_i^j$. We observe that there is a shortest path from $f^h(u_r^{i_r},v_r^{i_r})$ ($h\in \{1,2\}$) to $y'$ which either goes through one vertex of $\{a_r,c_r\}$, then goes through $s_{i'}^{j'}$, finally reaches $y'$ or goes through one vertex of $\{a_r,c_r\}$, then goes through some vertex $s_{i''}^{j''}$ ($i''\in [n],j''\in [m]$), then goes through $b_{r'}$, finally reaches $y'$. Thus we get that $\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),y')=\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),y')+1$. Thus every vertex pair $\{y,y'\}$ such that $y\ne s_i^j$ is resolved by $f^1(u_r^{i_r},v_r^{i_r})$ or $f^2(u_r^{i_r},v_r^{i_r})$. For a pair $\{s_i^j,y'\}$, obviously $\text {dist}(f^{mid}(i,j,1),s_i^j)<dist(f^{mid}(i,j,1),y')$. It follows that every vertex pair $\{y,y'\}$ is resolved by $f^1(u_r^{i_r},v_r^{i_r})$, $f^2(u_r^{i_r},v_r^{i_r})$ or $f^{mid}(i,j,1)$. For a vertex pair $\{x,y'\}$, there are two cases. Case 1: $i\ne i'$ or $j\ne j'$. $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x$. $\text {dist}(f(\pi _i^1,a_r),b_{r'})=2+\text {min}_{\alpha \in [m]} (|P(s_i^{\alpha },a_r)|+|P(s_i^{\alpha },b_{r'})|)$. Then $\text {dist}(f(\pi _i^1,a_r),y')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{y'},\text {dist}(f(\pi _i^1,a_r),b_{r'})+|P(s_{i'}^{j'},b_{r'})|-\ell _{y'})$. $\text {dist}(f(s_i^j,a_r),x)=|P(s_i^j,a_r)|-\ell _x<\text {dist}(f(\pi _i^1,a_r),x)$ if $x\ne a_r$ and $\text {dist}(f(s_i^j,a_r),a_r)=2$. $\text {dist}(f(s_i^j,a_r),y')=\text {dist}(f(\pi _i^1,a_r),y')$. Thus in this case, every pair $\{x,y'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. Case 2: $i=i'$ and $j=j'$. $\text {dist}(f(s_i^j,a_r),y')=\text {min }(|P(s_i^j,a_r)|+\ell _{y'},\text {dist}(f(\pi _i^1,a_r),b_{r'})+|P(s_{i'}^{j'},b_{r'})|-\ell _{y'})$. If $\text {dist}(f(s_i^j,a_r),y')=|P(s_i^j,a_r)|+\ell _{y'}$, then $\{x,y'\}$ is obviously resolved by $f(s_i^j,a_r)$. Otherwise, for a vertex pair $\{x,y'\}$ which is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),y')=\text {dist}(f(\pi _i^1,a_r),y')<\text {dist}(f(\pi _i^1,a_r),x)$. Thus in this case, every pair $\{x,y'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. It follows that every pair $\{x,y'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. For a vertex pair $\{y,z'\}$, similarly we can show that every pair $\{y,z'\}$ is resolved by $f(\pi _i^1,c_r)$ or $f(s_i^j,c_r)$. For a vertex pair $\{x,z'\}$, there are two cases. Case 1: $i\ne i'$ or $j\ne j'$. $\text {dist}(f(\pi _i^1,a_r),x)=2+|P(s_i^j,a_r)|-\ell _x>\text {dist}(f(s_i^j,a_r),x)$ if $x\ne a_r$. $\text {dist}(f(\pi _i^1,a_r),z')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{z'},|P(\pi _i^1,a_r)|+|P(\pi _i^1,c_{r'})|+|P(s_{i'}^{j'},c_{r'})|-\ell _{z'})$. $\text {dist}(f(s_i^j,a_r),z')=\text {min }(2+|P(s_{i'}^{j'},a_r)|+\ell _{z'},2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,c_{r'})|+|P(s_{i'}^{j'},c_{r'})|-\ell _{z'})\ge \text {dist}(f(\pi _i^1,a_r),z')$. Thus in this case, every pair $\{x,z'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. Case 2: $i=i'$ and $j=j'$. $\text {dist}(f(s_i^j,a_r),z')=\text {min }(|P(s_i^j,a_r)|+\ell _{z'},2+|P(\pi _i^1,a_r)|+|P(\pi _i^1,c_{r'})|+|P(s_{i'}^{j'},c_{r'})|-\ell _{z'})$. If $\text {dist}(f(s_i^j,a_r),z')=|P(s_i^j,a_r)|+\ell _{z'}$ Then $\{x,z'\}$ ($x\ne a_r$) is obviously resolved by $f(s_i^j,a_r)$. Otherwise, for a vertex pair $\{x,z'\}$ which is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(\pi _i^1,a_r),x)>\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),z')>\text {dist}(f(\pi _i^1,a_r),z')$. Thus every pair $\{x,z'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. It follows that every pair $\{x,z'\}$ is resolved by $f(\pi _i^1,a_r)$ or $f(s_i^j,a_r)$. This completes the proof for the lemma. $\square$

Lemma 12

Every pair of distinct vertices $x,y\in \bigcup _{i\in [n],h\in \{1,2\}}S_i^h$ is resolved by $\mathcal{S}'$.

Proof

Let $x\in P(\pi _i^h,a_r)$ for arbitrary integers $i\in [n],h\in \{1,2\},r\in \{1,2,3\}$. Let $x'\in P(\pi _{i'}^{h'},a_r)$ for arbitrary integers $i'\in [n],h'\in \{1,2\}$. We fix an arbitrary integer $j\in [m]$. Let $P(x,a_r)$ be the subpath of $P(\pi _i^h,a_r)$ and $\ell _x=|P(x,a_r)|$. Let $P(x',a_{r})$ be the subpath of $P(\pi _{i'}^{h'},a_{r})$ and $\ell _{x'}=|P(x',a_{r})|$. For a vertex pair $\{x,x'\}$, $\text {dist}(f(s_i^j,a_r),x)=2+\ell _x$ and $\text {dist}(f(s_i^j,a_r),x')=2+\ell _{x'}$. Then every vertex pair $\{x,x'\}$ such that $\ell _x\ne \ell _{x'}$ is resolved by $f(s_i^j,a_r)$. Since $\text {dist}(f(\pi _i^h,a_r),x)=\ell _x$ if $x\ne a_r$ and $\text {dist}(f(\pi _i^h,a_r),x')=2+\ell _{x'}$ if $i\ne i'$ or $h\ne h'$, every vertex pair $\{x,x'\}$ such that $\ell _x=\ell _{x'}$ is resolved by $f(\pi _i^h,a_r)$. It follows that every vertex pair $\{x,x'\}$ is resolved by $f(\pi _i^h,a_r)$ or $f(s_i^j,a_r)$. Let $y\in P(\pi _i^h,c_r)$ for arbitrary integers $i\in [n],h\in \{1,2\},r\in \{1,2,3\}$. Let $y'\in P(\pi _{i'}^{h'},c_r)$ for arbitrary integers $i'\in [n],h'\in \{1,2\}$. Similarly, we can show that every vertex pair $\{y,y'\}$ is resolved by $f(\pi _i^h,c_r)$ or $f(s_i^j,c_r)$.

Let $x_1\in P(\pi _i^h,a_r)$ for arbitrary integers $i\in [n],h\in \{1,2\},r\in \{1,2,3\}$. Let $x_2\in P(\pi _{i'}^{h'},a_{r'})$ for arbitrary integers $i'\in [n],h'\in \{1,2\},r'\in \{1,2,3\}$. We fix an arbitrary integer $j\in [m]$. We define $\ell _{x_1}$ and $\ell _{x_2}$ in a similar way to that of $\ell _x$ in the first paragraph. For a vertex pair $\{x_1,x_2\}$ such that $r\ne r'$, $\text {dist}(f(s_i^j,a_r),x_1)=2+\ell _{x_1}$ and $\text {dist}(f(s_i^j,a_r),x_2)=2+|P(\pi _{i'}^{h'},a_r)|+|P(\pi _{i'}^{h'},a_{r'})|-\ell _{x_2}=2+20(n+1)-\ell _{x_2}>\text {dist}(f(s_i^j,a_r),x_1)$ unless $x_1=\pi _i^h, x_2=\pi _{i'}^{h'}$ and $\pi _i^h\ne \pi _{i'}^{h'}$. The vertex pair $\{\pi _i^h,\pi _{i'}^{h'}\}$ is obviously resolved by $f^h(i,j,a_r)$. Thus every vertex pair $\{x_1,x_2\}$ such that $r\ne r'$ is resolved by $f(s_i^j,a_r)$ or $f^h(i,j,a_r)$. Let $y_1\in P(\pi _i^h,c_r)$ for arbitrary integers $i\in [n],h\in \{1,2\},r\in \{1,2,3\}$. Let $y_2\in P(\pi _{i'}^{h'},c_{r'})$ for arbitrary integers $i'\in [n],h'\in \{1,2\},r'\in \{1,2,3\}$ such that $r\ne r'$. We define $\ell _{y_1}$ and $\ell _{y_2}$ in a similar way to that of $\ell _x$ in last paragraph. Similarly, we can show that every vertex pair $\{y_1,y_2\}$ such that $r\ne r'$ is resolved by $f(s_i^j,c_r)$ or $f^h(i,j,a_r)$. For a pair $\{x_1,y_2\}$, $\text {dist}(f(s_i^j,a_r),x_1)=2+\ell _{x_1}$ and $\text {dist}(f(s_i^j,a_r),y_2)=2+|P(\pi _{i'}^{h'},a_r)|+|P(\pi _{i'}^{h'},c_{r'})|-\ell _{y_2}=2+20(n+1)-\ell _{y_2}>\text {dist}(f(s_i^j,a_r),x_1)$ unless $x_1=\pi _i^h, y_2=\pi _{i'}^{h'}$ and $\pi _i^h\ne \pi _{i'}^{h'}$. The vertex pair $\{\pi _i^h,\pi _{i'}^{h'}\}$ is obviously resolved by $f^h(i,j,a_r)$. Thus every vertex pair $\{x_1,y_2\}$ is resolved by $f(s_i^j,a_r)$ or $f^h(i,j,a_r)$. This completes the proof for the lemma. $\square$

Lemma 13

Every pair of distinct vertices $x,y\in \bigcup _{i\in [n],h\in \{1,2\},j\in [m],r\in \{1,2,3\}}\Pi ^h(i,j,r)$ is resolved by $\mathcal{S}'$.

Proof

Let $x_1,x_2\in P^{h}(i,j,a_r)$ be two distinct vertices for arbitrary integers $i\in [n],j\in [m],h\in \{1,2\},r\in \{1,2,3\}$. Let $j'\in [m]$ be an integer such that $j\ne j'$. Obviously the pair $\{x_1,x_2\}$ is resolved by $f^{h}(i,j',a_r)$. Similarly, the vertex pair $\{y_1,y_2\}$ for two distinct vertices $y_1,y_2\in P^{h}(i,j,b_r)$, the vertex pair $\{z_1,z_2\}$ for two distinct vertices $z_1,z_2\in P^{h}(i,j,c_r)$, and the vertex pair $\{w_1,w_2\}$ for two distinct vertices $w_1,w_2\in P^{h}(i,j,p_i^{3-h})$ are resolved by $f^{h}(i,j',a_r)$.

Let $x\in P^{h}(i,j,a_r),y\in P^{h}(i,j,b_r),z\in P^{h}(i,j,c_r)$ and $w\in P^{h}(i,j,p_i^{3-h})$ for arbitrary integers $i\in [n],j\in [m],h\in \{1,2\},r\in \{1,2,3\}$. Let $x'\in P^{h'}(i',j',a_{r'}),y'\in P^{h'}(i',j',b_{r'}),z'\in P^{h'}(i',j',c_{r'})$ and $w'\in P^{h'}(i',j',p_{i'}^{3-h'})$ for arbitrary integers $i'\in [n],j'\in [m],h'\in \{1,2\},r'\in \{1,2,3\}$. We define $\ell _x=\text {dist}(x,\pi _i^h)$. In a similar way, we define $\ell _y,\ell _z,\ell _w,\ell _{x'},\ell _{y'},\ell _{z'},\ell _{w'}$. For a pair $\{x,y\}$, $\text {dist}(f^{h}(i,j,c_r),x)=2+\ell _x$ and $\text {dist}(f^{h}(i,j,c_r),y)=2+\ell _y$. Thus $f^{h}(i,j,c_r)$ resolves every pair $\{x,y\}$ such that $\ell _x\ne \ell _y$. Since $\text {dist}(f^{h}(i,j,a_r),x)=\ell _x$ if $x\ne \pi _i^h$, $\text {dist}(f^{h}(i,j,a_r),\pi _i^h)=2$ and $\text {dist}(f^{h}(i,j,c_r),y)=2+\ell _y$, $f^{h}(i,j,a_r)$ resolves every pair $\{x,y\}$ such that $\ell _x=\ell _y$. Thus every pair $\{x,y\}$ is resolved by $f^{h}(i,j,a_r)$ or $f^{h}(i,j,c_r)$. In a similar way, we can show that two distinct vertices from $\bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^h(i,j,r)$ are distinguished by $\mathcal{S}'$. For a pair $\{x,y'\}$ with $i=i'$ and $h\ne h'$, $\text {dist}(f^{h}(i,j,c_r),x)=2+\ell _x<\text {dist}(f^{h}(i,j,c_r),y')=\text {min }(2+|P(\pi _i^h,a_r)|+|P(\pi _i^{h'},a_r)|+\ell _{y'},2+|P(\pi _i^h(i,j',b_{r'}))|+|P(\pi _i^{h'}(i,j',b_{r'})|-\ell _{y'})$. Thus every pair $\{x,y'\}$ with $i=i'$ and $h\ne h'$ is resolved by $f^{h}(i,j,c_r)$. Similarly we can show that every vertex pair of $\bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^h(i,j,r)\times \bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^{3-h}(i,j,r)$ is resolved by $\mathcal{S}'$. For a pair $\{x,y'\}$ with $i\ne i'$, $\text {dist}(f^{h}(i,j,c_r),x)=2+\ell _x$. $\text {dist}(f^{h}(i,j,c_r),s_{i'}^{j'})=\text {min}_{d\in \{1,2,3\}}(2+|P(\pi _i^h,c_d)|+|P(s_{i'}^{j'},c_d)|)$. Thus $\text {dist}(f^{h}(i,j,c_r),y')=\text {min }(2+|P(\pi _i^h,a_r)|+|P(\pi _i^{h'},a_r)|+\ell _{y'},\text {dist}(f^{h}(i,j,c_r),s_{i'}^{j'})+1+|P^{h'}(i',j',b_{r'})|-\ell _{y'})$. We can see that $\text {dist}(f^{h}(i,j,c_r),x)<\text {dist}(f^{h}(i,j,c_r),y')$ unless $\ell _x=20(n+1)$ and $\ell _{y'}=0$. If $\ell _x=20(n+1)$ and $\ell _{y'}=0$, $\text {dist}(f^{h}(i,j,a_r),y')=2+20(n+1)>\text {dist}(f^{h}(i,j,a_r),x)=20(n+1)$. Thus every pair $\{x,y'\}$ with $i\ne i'$ is resolved by $f^{h}(i,j,c_r)$ or $f^{h}(i,j,a_r)$. Similarly we can show that every vertex pair of $\bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^h(i,j,r)\times \bigcup _{j'\in [m],r'\in \{1,2,3\}}\Pi ^{h'}(i',j',r')$ with $i\ne i'$ is resolved by $\mathcal{S}'$. This completes the proof for the lemma. $\square$

Lemma 14

Every pair of distinct vertices $x,y\in \bigcup _{i\in [n],h\in \{1,2\}}L_i^h$ is resolved by $\mathcal{S}'$.

Proof

First we show that every vertex pair of $L_i^h\times L_i^h$ is resolved by $\mathcal{S}'$ for $i\in [n],h\in \{1,2\}$. We fix arbitrary integers $i\in [n],j\in [m]$ and $h\in \{1,2\}$. For a vertex $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, let $P(q_i^h,x)$ be the subpath of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from $q_i^h$ to x and let $|P(q_i^h,x)|=\ell _x$. For two distinct vertices $x_1,x_2\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, $\text {dist}(f^{mid}(i,j,3-h),x_1)=1+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _{x_1}=30(n+1)-\ell _{x_1}$ and $\text {dist}(f^{mid}(i,j,3-h),x_2)=30(n+1)-\ell _{x_2}$. Thus $f^{mid}(i,j,3-h)$ resolves every pair $\{x_1,x_2\}$. Let $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ and $x'\in P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))$ with some integer $j'\ne j$. $\text {dist}(f^h(i,j,a_1),x)=3+\ell _x$ and $\text {dist}(f^h(i,j,a_1),x')=3+\ell _{x'}$. Thus $f^h(i,j,a_1)$ resolves every pair $\{x,x'\}$ such that $\ell _x\ne \ell _{x'}$. For a pair $\{x,x'\}$ such that $\ell _x=\ell _{x'}$, $\text {dist}(f^{mid}(i,j,3-h),x)=30(n+1)-\ell _{x}$ and $\text {dist}(f^{mid}(i,j,3-h),x')=\text {min }(1+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|+\ell _{x'},1+|P^{3-h}(i,j,p_i^h)|/2+|P^{3-h}(i,j',p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))|-\ell _{x'})=\text {min }(30(n+1)+\ell _{x'},50(n+1)-\ell _{x'})$. Thus $\text {dist}(f^{mid}(i,j,3-h),x)\ne \text {dist}(f^{mid}(i,j,3-h),x')$ and $f^{mid}(i,j,3-h)$ resolves this pair. It follows that every pair $\{x,x'\}$ is resolved by $f^{mid}(i,j,3-h)$ or $f^h(i,j,a_1)$.

Next we show that every vertex pair of $L_i^h\times L_i^{3-h}$ is resolved by $\mathcal{S}'$ for $i\in [n],h\in \{1,2\}$. We fix arbitrary integers $i\in [n],j\in [m]$ and $h\in \{1,2\}$. Let $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ and $y\in P(q_i^{3-h},\text {mid}(P^{h}(i,j,p_i^{3-h})))$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in last paragraph. For a pair $\{x,y\}$, $\text {dist}(f^{mid}(i,j,3-h),x)=30(n+1)-\ell _{x}$ and $\text {dist}(f^{mid}(i,j,3-h),y)=\text {min }(2+|P^{3-h}(i,j,p_i^h)|/2+\ell _y,3+|P(q_i^{3-h},\text {mid}(P^h(i,j,p_i^{3-h})))|+|P^{3-h}(i,j,p_i^h)|/2+|P^h(i,j,p_i^{3-h})|/2-\ell _y)$. For a pair $\{x,y\}$ which is not resolved by $f^{mid}(i,j,3-h)$, there are two cases. Case 1: $\text {dist}(f^{mid}(i,j,3-h),y)=2+|P^{3-h}(i,j,p_i^h)|/2+\ell _y=2+10(n+1)+\ell _y\le 2+50(n+1)-\ell _y$ when $\ell _y\le 20(n+1)$. We have $\text {dist}(f^{mid}(i,j,3-h),x)=30(n+1)-\ell _{x}=\text {dist}(f^{mid}(i,j,3-h),y)=2+10(n+1)+\ell _y$, i.e. $\ell _x+\ell _y=20(n+1)-2$. Case 2: $\text {dist}(f^{mid}(i,j,3-h),y)=2+50(n+1)-\ell _y$ when $\ell _y>20(n+1)$. We have $\text {dist}(f^{mid}(i,j,3-h),x)=30(n+1)-\ell _{x}=\text {dist}(f^{mid}(i,j,3-h),y)=2+50(n+1)-\ell _y$, i.e. $\ell _y-\ell _x=20(n+1)+2$. $\text {dist}(f^{3-h}(i,j,a_1),y)=3+\ell _y$. $\text {dist}(f^{3-h}(i,j,a_1),x)=3+|P(\pi _i^{3-h},a_1)|+|P(\pi _i^{h},a_1)|+\ell _x$ when $\ell _x\le 10(n+1)$ and $\text {dist}(f^{3-h}(i,j,a_1),x)=2+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^{h},\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x$ when $\ell _x>10(n+1)$. For a pair $\{x,y\}$ which is not resolved by $f^{3-h}(i,j,a_1)$, there are two cases. Case 1: $\text {dist}(f^{3-h}(i,j,a_1),y)=\text {dist}(f^{3-h}(i,j,a_1),x)$ when $\ell _x\le 10(n+1)$, i.e. $\ell _y-\ell _x=3+20(n+1)$. Case 2: $\text {dist}(f^{3-h}(i,j,a_1),y)=\text {dist}(f^{3-h}(i,j,a_1),x)$ when $\ell _x>10(n+1)$, i.e. $\ell _y+\ell _x=40(n+1)-2$. Thus we see that if a pair $\{x,y\}$ is not resolved by $f^{mid}(i,j,3-h)$, then it is resolved by $f^{3-h}(i,j,a_1)$. It follows that every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$ and $f^{3-h}(i,j,a_1)$. Let $x'\in P(q_i^{h},\text {mid}(P^{3-h}(i,j',p_i^{h})))$ with some integer $j'\in [m]$ and $j'\ne j$. Then $\text {dist}(f^{mid}(i,j',3-h),x')=30(n+1)-\ell _{x'}$ and $\text {dist}(f^{mid}(i,j',3-h),y)=2+|P^{3-h}(i,j',p_i^h)|/2+\ell _{y}=2+10(n+1)+\ell _y$. For a pair $\{x',y\}$ which is not resolved by $f^{mid}(i,j',3-h)$, it satisfies that $30(n+1)-\ell _{x'}=2+10(n+1)+\ell _y$, i.e. $\ell _{x'}+\ell _y=20(n+1)-2$. Similar to vertex x, for vertex $x'$, $\text {dist}(f^{3-h}(i,j,a_1),x')=3+|P(\pi _i^{3-h},a_1)|+|P(\pi _i^{h},a_1)|+\ell _{x'}$ when $\ell _{x'}\le 10(n+1)$ and $\text {dist}(f^{3-h}(i,j,a_1),x')=2+|P^{3-h}(i,j',p_i^h)|/2+|P(q_i^{h},\text {mid}(P^{3-h}(i,j',p_i^{h})))|-\ell _{x'}$ when $\ell _{x'}>10(n+1)$. Thus for a pair $\{x',y\}$ which is not resolved by $f^{3-h}(i,j,a_1)$, there are two cases. Case 1: $\text {dist}(f^{3-h}(i,j,a_1),y)=\text {dist}(f^{3-h}(i,j,a_1),x')$ when $\ell _{x'}\le 10(n+1)$, i.e. $\ell _y-\ell _{x'}=3+20(n+1)$. Case 2: $\text {dist}(f^{3-h}(i,j,a_1),y)=\text {dist}(f^{3-h}(i,j,a_1),x')$ when $\ell _{x'}>10(n+1)$, i.e. $\ell _y+\ell _{x'}=40(n+1)-2$. Thus we see that if a pair $\{x',y\}$ is not resolved by $f^{mid}(i,j',3-h)$, then it is resolved by $f^{3-h}(i,j,a_1)$. It follows that every pair $\{x',y\}$ is resolved by $f^{mid}(i,j',3-h)$ and $f^{3-h}(i,j,a_1)$.

Finally we show that every vertex pair of $L_i^h\times L_{i'}^{h'}$ is resolved by $\mathcal{S}'$ for $i,i'\in [n],h,h'\in \{1,2\}$ and $i\ne i'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h,h'\in \{1,2\}$ such that $i\ne i'$. Let $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^h)))$ and $y\in P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the first paragraph. For a pair $\{x,y\}$, $\text {dist}(f^{mid}(i,j,3-h),x)=30(n+1)-\ell _{x}$ and $\text {dist}(f^{mid}(i,j,3-h),y)=\text {min }(2+|P^{3-h}(i,j,p_i^h)|/2+|P(\pi _i^{3-h},a_1)|+|P(\pi _{i'}^{3-h'},a_1)|+\ell _y, 1+|P^{3-h}(i,j,p_i^h)|/2+|P(\pi _i^{3-h},a_1)|+|P(\pi _{i'}^{3-h'},a_1)|+|P^{3-h'}(i',j',p_{i'}^{h'})|+|P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))|-\ell _y) \ge 1+30(n+1)>\text {dist}(f^{mid}(i,j,3-h),x)$. It follows that every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$. This completes the proof for the lemma. $\square$

Lemma 15

Every pair of distinct vertices $x,y\in \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

Let’s fix an arbitrary integer $r\in \{1,2,3\}$.

First, we show that every pair of distinct vertices of $\bigcup _{i\in [n]}(P(a_r,u_r^i)\cup P(a_r,v_r^i))$ is resolved by $\mathcal{S}'$. Let’s fix an arbitrary integer $i\in [n]$. Let $x_u\in P(a_r,u_r^i)$. Let $P(a_r,x_u)$ be the subpath of $P(a_r,u_r^i)$ from $a_r$ to $x_u$ and let $\ell _{x_u}=|P(a_r,x_u)|$. Since $\text {dist}(f(\pi _1^1,a_r),x_u)=2+\ell _{x_u}$, obviously two distinct vertices of $P(a_r,u_r^i)$ are distinguished by $f(\pi _1^1,a_r)$. Let $x_v\in P(a_r,v_r^i)$. Let $P(a_r,x_v)$ be the subpath of $P(a_r,v_r^i)$ from $a_r$ to $x_v$ and let $\ell _{x_v}=|P(a_r,x_v)|$. Since $\text {dist}(f(\pi _1^1,a_r),x_v)=2+\ell _{x_v}$, obviously two distinct vertices of $P(a_r,v_r^i)$ are distinguished by $f(\pi _1^1,a_r)$. For the pair $\{x_u,x_v\}$, if $\ell _{x_u}\ne \ell _{x_v}$, then it is resolved by $f(\pi _1^1,a_r)$. Otherwise, if $\ell _{x_u}=\ell _{x_v}<|P(a_r,u_r^i)|$, then $\text {dist}(f^1(u_r^i,v_r^i),x_u)=1+|P(a_r,u_r^i)|-\ell _{x_u}<\text {dist}(f^1(u_r^i,v_r^i),x_v)=2+|P(a_r,v_r^i)|-\ell _{x_v}$. By Claim 1, the vertex pair $\{u_r^i,v_r^i\}$ is resolved by $\mathcal{S}'$. Thus every pair $\{x_u,x_v\}$ is resolved by $\mathcal{S}'$. Let $x_u'\in P(a_r,u_r^{i'})$ and $x_v'\in P(a_r,v_r^{i'})$ for some integer $i'\in [n]$ such that $i'\ne i$. We define $\ell _{x_u'}$ and$\ell _{x_v'}$ in a similar way to that of $\ell _{x_u}$ and $\ell _{x_v}$. For a pair $\{x_u,x_u'\}$, $\text {dist}(f^1(u_r^i,v_r^i),x_u)=1+|P(a_r,u_r^i)|-\ell _{x_u}<\text {dist}(f^1(u_r^i,v_r^i),x_u')=1+|P(a_r,u_r^i)|+\ell _{x_u'}$. Thus every pair $\{x_u,x_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, we can show that every pair $\{x_u,x_v'\}$, $\{x_v,x_v'\}$ is resolved by $f^1(u_r^i,v_r^i)$.

Then we show that every pair of distinct vertices of $\bigcup _{i\in [n]}(P(c_r,u_r^i)\cup P(c_r,v_r^i))$ is resolved by $\mathcal{S}'$. Let’s fix arbitrary integers $i,i'\in [n]$ such that $i\ne i'$. Let $z_u\in P(c_r,u_r^i)$, $z_v\in P(c_r,v_r^i)$, $z_u'\in P(c_r,u_r^{i'})$ and $z_v'\in P(c_r,v_r^{i'})$. We define $\ell _{z_u}$, $\ell _{z_v}$, $\ell _{z_u'}$ and $\ell _{z_v'}$ in a similar way to that of $\ell _{x_u}$ and $\ell _{z_v}$ in last paragraph. Since $\text {dist}(f(\pi _1^1,c_r),z_u)=2+\ell _{z_u}$, obviously two distinct vertices of $P(c_r,u_r^i)$ are distinguished by $f(\pi _1^1,c_r)$. Since $\text {dist}(f(\pi _1^1,c_r),z_v)=2+\ell _{z_v}$, two distinct vertices of $P(c_r,v_r^i)$ are distinguished by $f(\pi _1^1,c_r)$. For a pair $\{z_u,z_v\}$, if $\ell _{z_u}\ne \ell _{z_v}$, then it is resolved by $f(\pi _1^1,c_r)$. Otherwise, if $\ell _{z_u}=\ell _{z_v}<|P(c_r,u_r^i)|$, then $\text {dist}(f^1(u_r^i,v_r^i),z_u)=1+|P(c_r,u_r^i)|-\ell _{z_u}<\text {dist}(f^1(u_r^i,v_r^i),z_v)=2+|P(c_r,v_r^i)|-\ell _{z_v}$. Thus every pair $\{z_u,z_v\}$ is resolved by $\mathcal{S}'$. For a pair $\{z_u,z_u'\}$, if $\ell _{z_u}\ne \ell _{z_u'}$, then it is resolved by $f(\pi _1^1,c_r)$. Otherwise if $\ell _{z_u}=\ell _{z_u'}$, then $\text {dist}(f^1(u_r^i,v_r^i),z_u')=\text {min }(1+|P(c_r,u_r^i)|+\ell _{z_u'},1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-\ell _{z_u'}-2)$ if $|P(c_r,u_r^{i'})|-\ell _{z_u'}\ge 2$. $\text {dist}(f^1(u_r^i,v_r^i),z_u')=1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-\ell _{z_u'}$ if $|P(c_r,u_r^{i'})|-\ell _{z_u'}<2$. If $\text {dist}(f^1(u_r^i,v_r^i),z_u')=1+|P(c_r,u_r^i)|+\ell _{z_u'}$, then $\{z_u,z_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Otherwise, if $\text {dist}(f^1(u_r^i,v_r^i),z_u')=1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-\ell _{z_u'}$, suppose that there is a pair $\{z_u,z_u'\}$ which is not resolved by $f^1(u_r^i,v_r^i)$. We get that $i=2(n+1)$, a contradiction. If $\text {dist}(f^1(u_r^i,v_r^i),z_u')=1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-\ell _{z_u'}-2$, suppose that there is a pair $\{z_u,z_u'\}$ which is not resolved by $f^1(u_r^i,v_r^i)$. We get that $20i=40(n+1)-2$, a contradiction. Thus every pair $\{z_u,z_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$ or $f(\pi _1^1,c_r)$. Similarly, we can show that every pair $\{z_u,z_v'\}$ and $\{z_v,z_v'\}$ is resolved by $f^1(u_r^i,v_r^i)$ or $f(\pi _1^1,c_r)$.

Next we show that every pair of distinct vertices of $\bigcup _{i\in [n]}(P(b_r,u_r^i)\cup P(b_r,v_r^i))$ is resolved by $\mathcal{S}'$. Let’s fix an arbitrary integer $i,i'\in [n]$ such that $i'\ne i$ Let $y_u\in P(b_r,u_r^i)$, $y_v\in P(b_r,v_r^i)$, $y_u'\in P(b_r,u_r^{i'})$ and $y_v'\in P(b_r,v_r^{i'})$. We define $\ell _{y_u}$, $\ell _{y_v}$, $\ell _{y_u'}$ and $\ell _{y_v'}$ in a similar way to that of $\ell _{x_u}$ and $\ell _{x_v}$ in the second paragraph. Since $(G,n,\chi ,\mathcal P)$ is a YES-instance, by Claim 1, the pair $\{u_r^i,v_r^i\}$ is resolved by some vertex of S, say $s_{\eta }^{\tau }$. Since $\text {dist}(s_{\eta }^{\tau },y_u)=|P(s_{\eta }^{\tau },b_r)|+\ell _{y_u}=20(n+1)+5i+1+\ell _{y_u}$, every vertex pair of $P(b_r,u_r^i)$ is resolved by $s_{\eta }^{\tau }$. Since $\text {dist}(s_{\eta }^{\tau },y_v)=|P(s_{\eta }^{\tau },b_r)|+\ell _{y_v}=20(n+1)+5i+1+\ell _{y_v}$, every vertex pair of $P(b_r,v_r^i)$ is resolved by $s_{\eta }^{\tau }$. For a pair $\{y_u,y_v\}$, if $\ell _{y_u}\ne \ell _{y_v}$, then it is resolved by $s_{\eta }^{\tau }$. For a pair $\{y_u,y_v\}$ such that $\ell _{y_u}=\ell _{y_v}$, $\text {dist}(f^1(u_r^i,v_r^i),y_u)=2+|P(b_r,u_r^i)|-\ell _{y_u}=1+20(n+1)-5i-\ell _{y_u}>\text {dist}(f^1(u_r^i,v_r^i),y_v)=2+|P(b_r,v_r^i)|-\ell _{y_v}=20(n+1)-5i-\ell _{y_v}$. Thus every pair $\{y_u,y_v\}$ is resolved by $s_{\eta }^{\tau }$ or $f^1(u_r^i,v_r^i)$. For a pair $\{y_u,y_u'\}$ such that $y_u\ne b_r$ and $y_u'\ne b_r$, $\text {dist}(f^1(u_r^i,v_r^i),y_u)=1+20(n+1)-5i-\ell _{y_u}\le 20(n+1)-5i$. $\text {dist}(f^1(u_r^i,v_r^i),y_u')=\text {min }(2+|P(b_r,v_r^i)|+\ell _{y_u'},1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(b_r,u_r^{i'})|-\ell _{y_u'})>20(n+1)-5i$. Thus every pair $\{y_u,y_u'\}$ such that $y_u\ne b_r$ and $y_u'\ne b_r$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{y_u,y_v'\}$ and $\{y_v,y_v'\}$ is resolved by $f^1(u_r^i,v_r^i)$.

Then we show that every pair of distinct vertices of $R_r$ is resolved by $\mathcal{S}'$. Let’s fix arbitrary integers $i,i'\in [n]$ such that $i'\ne i$. Let $x_u\in P(a_r,u_r^i), x_v\in P(a_r,v_r^i), y_u\in P(b_r,u_r^i), y_v\in P(b_r,v_r^i), z_u\in P(c_r,u_r^i)$ and $z_v\in P(c_r,v_r^i)$. Let $x_u'\in P(a_r,u_r^{i'}), x_v'\in P(a_r,v_r^{i'}), y_u'\in P(b_r,u_r^{i'}), y_v'\in P(b_r,v_r^{i'}), z_u'\in P(c_r,u_r^{i'})$ and $z_v'\in P(c_r,v_r^{i'})$. We define $\ell _{x_u},\ell _{x_v},\ell _{y_u},\ell _{y_v},\ell _{z_u},\ell _{z_v},\ell _{x_u'},\ell _{x_v'},\ell _{y_u'},\ell _{y_v'},\ell _{z_u'}$ and $\ell _{z_v'}$ in a similar way to that of $\ell _{x_u}$ and $\ell _{x_v}$ in the second paragraph. For a pair $\{x_u,y_u\}$, $\text {dist}(f(\pi _1^1,a_r),x_u)=2+\ell _{x_u}<\text {dist}(f(\pi _1^1,a_r),y_u)=2+|P(a_r,u_r^i)|+|P(b_r,u_r^i)|-\ell _{y_u}$. Thus every pair $\{x_u,y_u\}$ is resolved by $f(\pi _1^1,a_r)$. Similarly, every pair $\{x_u,y_v\}$, $\{x_v,y_v\}$ and $\{x_v,y_u\}$ are resolved by $f(\pi _1^1,a_r)$. For a pair $\{x_u,z_u\}$, $\text {dist}(f(\pi _1^1,a_r),x_u)=2+\ell _{x_u}$. $\text {dist}(f(\pi _1^1,a_r),z_u)=\text {min }(2+|P(a_r,u_r^i)|+|P(c_r,u_r^i)|-\ell _{z_u}-2,|P(\pi _1^1,a_r)|+|P(\pi _1^1,c_r)|+\ell _{z_u})$ if $|P(c_r,u_r^i)|-\ell _{z_u}\ge 2$. $\text {dist}(f(\pi _1^1,a_r),z_u)=2+|P(a_r,u_r^i)|+|P(c_r,u_r^i)|-\ell _{z_u}$ if $|P(c_r,u_r^i)|-\ell _{z_u}<2$. It follows that $\text {dist}(f(\pi _1^1,a_r),x_u)=2+\ell _{x_u}<\text {dist}(f(\pi _1^1,a_r),z_u)$. Thus every pair $\{x_u,z_u\}$ is resolved by $f(\pi _1^1,a_r)$. Similarly, every pair $\{x_u,z_v\}$, $\{x_v,z_v\}$ and $\{x_v,z_u\}$ are resolved by $f(\pi _1^1,a_r)$. For a pair $\{y_u,z_u\}$, $\text {dist}(f(\pi _1^1,c_r),z_u)=2+\ell _{z_u}$. $\text {dist}(f(\pi _1^1,c_r),b_r)=\text {min}_{j\in [m]}(|P(c_r,s_1^j)|+|P(s_1^j,b_r)|)=35n+41$. $\text {dist}(f(\pi _1^1,c_r),y_u)=\text {min }(2+|P(c_r,u_r^i)|+|P(b_r,u_r^i)|-\ell _{y_u},\text {dist}(f(\pi _1^1,c_r),b_r)+\ell _{y_u})>\text {dist}(f(\pi _1^1,c_r),z_u)$. Thus every pair $\{y_u,z_u\}$ is resolved by $f(\pi _1^1,a_r)$. Similarly, every pair $\{y_u,z_v\}$, $\{y_v,z_v\}$ and $\{y_v,z_u\}$ are resolved by $f(\pi _1^1,c_r)$. For a pair $\{x_u,y_u'\}$, $\text {dist}(f^1(u_r^i,v_r^i),x_u)=1+|P(a_r,u_r^i)|-\ell _{x_u}$ if $x_u\ne u_r^i$ and $\text {dist}(f^1(u_r^i,v_r^i),u_r^i)=2$. $\text {dist}(f^1(u_r^i,v_r^i),y_u')=\text {min }(1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(b_r,u_r^{i'})|-\ell _{y_u'},2+|P(b_r,v_r^i)|+\ell _{y_u'})>\text {dist}(f^1(u_r^i,v_r^i),x_u)$. Thus every pair $\{x_u,y_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{x_u,y_v'\}$, $\{x_v,y_v'\}$, $\{x_v,y_u'\}$, $\{x_u,z_u'\}$, $\{x_u,z_v'\}$, $\{x_v,z_v'\}$ and $\{x_v,z_u'\}$ are resolved by $f^1(u_r^i,v_r^i)$. For a pair $\{y_u,z_u'\}$, $\text {dist}(f^1(u_r^i,v_r^i),y_u)=2+|P(b_r,u_r^i)|-\ell _{y_u}$ if $y_u\ne b_r$ and $\text {dist}(f^1(u_r^i,v_r^i),y_u)=1+|P(b_r,u_r^i)|$ if $y_u=b_r$. $\text {dist}(f^1(u_r^i,v_r^i),z_u')=\text {min }(1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-2-\ell _{z_u'},1+|P(c_r,u_r^i)|+\ell _{z_u'})$ if $|P(c_r,u_r^{i'})|-\ell _{z_u'}\ge 2$. $\text {dist}(f^1(u_r^i,v_r^i),z_u')=\text {min }(1+|P(a_r,u_r^i)|+|P(a_r,u_r^{i'})|+|P(c_r,u_r^{i'})|-\ell _{z_u'},1+|P(c_r,u_r^i)|+\ell _{z_u'})$ if $|P(c_r,u_r^{i'})|-\ell _{z_u'}<2$. It follows that $\text {dist}(f^1(u_r^i,v_r^i),z_u')>20(n+1)>\text {dist}(f^1(u_r^i,v_r^i),y_u)$. Thus every pair $\{y_u,z_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{y_u,z_v'\}$, $\{y_v,z_v'\}$ and $\{y_v,z_u'\}$ are resolved by $f^1(u_r^i,v_r^i)$. As a result, every pair of distinct vertices of $R_r$ is resolved by $\mathcal{S}'$.

Finally, we show that every vertex pair of $R_r\times R_{r'}$ with $r'\in \{1,2,3\}$ and $r'\ne r$ is resolved by $\mathcal{S}'$. Let’s fix arbitrary integers $i,i'\in [n]$ and $r'\in \{1,2,3\}$ such that $r'\ne r$. Let $x_u\in P(a_r,u_r^i), x_v\in P(a_r,v_r^i), y_u\in P(b_r,u_r^i), y_v\in P(b_r,v_r^i), z_u\in P(c_r,u_r^i)$ and $z_v\in P(c_r,v_r^i)$. Let $x_u'\in P(a_{r'},u_{r'}^{i'}), x_v'\in P(a_{r'},v_{r'}^{i'}), y_u'\in P(b_{r'},u_{r'}^{i'}), y_v'\in P(b_{r'},v_{r'}^{i'}), z_u'\in P(c_{r'},u_{r'}^{i'})$ and $z_v'\in P(c_{r'},v_{r'}^{i'})$. We define $\ell _{x_u},\ell _{x_v},\ell _{y_u},\ell _{y_v}$, $\ell _{z_u},\ell _{z_v},\ell _{x_u'},\ell _{x_v'},\ell _{y_u'},\ell _{y_v'},\ell _{z_u'}$ and $\ell _{z_v'}$ in a similar way to that of $\ell _{x_u}$ and $\ell _{x_v}$ in the second paragraph. For a pair $\{x_u,x_u'\}$, $\text {dist}(f(s_1^1,a_r),x_u)=2+\ell _{x_u}<20(n+1)<\text {dist}(f(s_1^1,a_r),x_u')=2+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+\ell _{x_u'}$. Thus every pair $\{x_u,x_u'\}$ is resolved by $f(s_1^1,a_r)$. Similarly, every pair $\{x_u,x_v'\}$, $\{x_v,x_u'\}$ and $\{x_v,x_v'\}$ are resolved by $f(s_1^1,a_r)$. For a pair $\{x_u,z_u'\}$, $\text {dist}(f(s_1^1,a_r),x_u)=2+\ell _{x_u}<20(n+1)$. $\text {dist}(f(s_1^1,a_r),z_u')=\text {min }(2+|P(\pi _1^1,a_r)|+|P(\pi _1^1,c_{r'})|+\ell _{z_u'},2+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|-2+|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'})$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'}\ge 2$. $\text {dist}(f(s_1^1,a_r),z_u')=\text {min }(2+|P(\pi _1^1,a_r)|+|P(\pi _1^1,c_{r'})|+\ell _{z_u'},2+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'})$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'}<2$. It follows that $\text {dist}(f(s_1^1,a_r),z_u')>20(n+1)$. Thus every pair $\{x_u,z_u'\}$ is resolved by $f(s_1^1,a_r)$. Similarly, every pair $\{x_u,z_v'\}$, $\{x_v,z_u'\}$ and $\{x_v,z_v'\}$ are resolved by $f(s_1^1,a_r)$. For a pair $\{x_u,y_u'\}$ such that $y_u'\ne b_{r'}$, $\text {dist}(f(\pi _1^1,a_r),x_u)=2+\ell _{x_u}<20(n+1)$. $\text {dist}(f(\pi _1^1,a_r),b_{r'})=2+\text {min}_{j\in [m]}(|P(s_1^j,a_r)|+|P(s_1^j,b_{r'})|)$. $\text {dist}(f(\pi _1^1,a_r),y_u')=\text {min }(\text {dist}(f(\pi _1^1,a_r),b_{r'})+\ell _{z_u'},|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(b_{r'},u_{r'}^{i'})|-\ell _{y_u'})>20(n+1)$. Thus every pair $\{x_u,y_u'\}$ such that $y_u'\ne b_{r'}$ is resolved by $f(\pi _1^1,a_r)$. Similarly, every pair $\{x_v,y_u'\}$ such that $y_u'\ne b_{r'}$, every pair $\{x_v,y_v'\}$ and $\{x_u,y_v'\}$ are resolved by $f(\pi _1^1,a_r)$. For a pair $\{y_u,y_u'\}$ such that $y_u\ne b_r$, $\text {dist}(f^1(u_r^i,v_r^i),y_u)=2+|P(b_r,u_r^i)|-\ell _{y_u}<20(n+1)$. $\text {dist}(f^1(u_r^i,v_r^i),b_{r'})=\text {min }(2+|P(b_r,v_r^i)|+\text {min}_{j\in [m]}(|P(s_1^j,b_r)|+|P(s_1^j,b_{r'})|),1+|P(a_r,v_r^i)|+\text {min}_{j'\in [m]}(|P(s_1^{j'},a_r)|+|P(s_1^{j'},b_{r'})|))$. $\text {dist}(f^1(u_r^i,v_r^i),y_u')=\text {min }(\text {dist}(f^1(u_r^i,v_r^i),b_{r'})+\ell _{y_u'},1+|P(a_r,v_r^i)|+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(b_{r'},u_{r'}^{i'})|-\ell _{y_u'})>20(n+1)$. Thus every pair $\{y_u,y_u'\}$ such that $y_u\ne b_r$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{y_u,y_v'\}$ such that $y_u\ne b_r$, every pair $\{y_v,y_v'\}$ and $\{y_v,y_u'\}$ are resolved by $f^1(u_r^i,v_r^i)$. For a pair $\{y_u,z_u'\}$, $\text {dist}(f^1(u_r^i,v_r^i),y_u)<20(n+1)$. $\text {dist}(f^1(u_r^i,v_r^i),z_u')=\text {min }(1+|P(a_r,u_r^i)|+|P(\pi _1^1,a_r)|+|P(\pi _1^1,c_{r'})|+\ell _{z_u'}, 1+|P(a_r,u_r^i)|+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'}-2)$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'}\ge 2$. $\text {dist}(f^1(u_r^i,v_r^i),z_u')=\text {min }(1+|P(a_r,u_r^i)|+|P(\pi _1^1,a_r)|+|P(\pi _1^1,c_{r'})|+\ell _{z_u'}, 1+|P(a_r,u_r^i)|+|P(\pi _1^1,a_r)|+|P(\pi _1^1,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'})$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_u'}<2$. It follows that $\text {dist}(f^1(u_r^i,v_r^i),z_u')>30(n+1)$. Thus every pair $\{y_u,z_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{y_u,z_v'\}$, $\{y_v,z_u'\}$ and $\{y_v,z_v'\}$ are resolved by $f^1(u_r^i,v_r^i)$. For a pair $\{z_u,z_u'\}$, $\text {dist}(f^1(u_r^i,v_r^i),z_u)=1+|P(c_r,u_r^i)|-\ell _{z_u}$ if $z_u\ne u_r^i$ and $\text {dist}(f^1(u_r^i,v_r^i),z_u)=2$ if $z_u=u_r^i$. Thus $\text {dist}(f^1(u_r^i,v_r^i),z_u)<30(n+1)<\text {dist}(f^1(u_r^i,v_r^i),z_u')$ and every pair $\{z_u,z_u'\}$ is resolved by $f^1(u_r^i,v_r^i)$. Similarly, every pair $\{z_u,z_v'\}$, $\{z_v,z_u'\}$ and $\{z_v,z_v'\}$ are resolved by $f^1(u_r^i,v_r^i)$. As a result, every vertex pair of $R_r\times R_{r'}$ with $r'\in \{1,2,3\}$ and $r'\ne r$ is resolved by $\mathcal{S}'$. This completes the proof for the lemma. $\square$

5.2 Vertex Pairs Between Distinct Vertex Sets

In this subsection, we prove Lemmas 16 - 30 in Table 1.

Lemma 16

Every pair $\{x,y\}\in \bigcup _{i\in [n]}U_i\times \bigcup _{i\in [n]}\Pi _i$ is resolved by $\mathcal{S}'$.

Proof

First, we show that every pair $\{x,y\}\in U_i^h\times \bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^h(i,j,r)$ for $i\in [n],h\in \{1,2\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m]$, $h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P^h(i,j',a_r)$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(x,p_i^h)$ be the subpath of $P(s_i^j,p_i^h)$ from x to $p_i^h$ and $|P(x,p_i^h)|=\ell _x$. For a vertex $y\in P^h(i,j',a_r)$, let $P(y,\pi _i^h)$ be the subpath of $P^h(i,j',a_r)$ from y to $\pi _i^h$ and $|P(y,\pi _i^h)|=\ell _y$. Let $j^*\in [m]$ be an integer such that $j^*\ne j$ and $j^*\ne j'$. Then $\text {dist}(f^h(i,j^*,a_r),x)=3+\ell _x$ and $\text {dist}(f^h(i,j^*,a_r),y)=2+\ell _y$. Thus every pair $\{x,y\}$ is resolved by $f^h(i,j^*,a_r)$ unless $\ell _y-\ell _x=1$. For the pair $\{x,y\}$ such that $\ell _y-\ell _x=1$, there are two cases. Case 1: $j=j'$. Since $\text {dist}(f^h(i,j',a_r),x)=3+\ell _x$ if $x\ne s_i^j$, $\text {dist}(f^h(i,j',a_r),s_i^j)=20(n+1)+1$ and $\text {dist}(f^h(i,j',a_r),y)=\ell _y$ if $y\ne \pi _i^h$, $\text {dist}(f^h(i,j',a_r),\pi _i^h)=2$, every pair $\{x,y\}$ such that $\ell _y-\ell _x=1$ is resolved by $f^h(i,j',a_r)$. Case 2: $j\ne j'$. Since $\text {dist}(f^h(i,j',a_r),x)=3+\ell _x$, $\text {dist}(f^h(i,j',a_r),y)=\ell _y$ if $y\ne \pi _i^h$ and $\text {dist}(f^h(i,j',a_r),\pi _i^h)=2$, every pair $\{x,y\}$ such that $\ell _y-\ell _x=1$ is resolved by $f^h(i,j',a_r)$. It follows that every pair $\{x,y\}$ is resolved by $f^h(i,j^*,a_r)$ or $f^h(i,j',a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P^h(i,j',b_r)$, $P(s_i^j,p_i^h)\times P^h(i,j',c_r)$ and $P(s_i^j,p_i^h)\times P^h(i,j',p_i^{3-h})$ are resolved by $\mathcal{S}'$.

Next we show that every pair $\{x,y\}\in U_i^h\times \bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^{3-h}(i,j,r)$ for $i\in [n],h\in \{1,2\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m]$, $h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)\setminus \{s_i^j\}$ and $y\in P^{3-h}(i,j',a_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the first paragraph. There are two cases. Case 1: $j=j'$. $\text {dist}(f^{3-h}(i,j',a_r),y)=\ell _y$ if $y\ne \pi _i^h$, $\text {dist}(f^h(i,j',a_r),\pi _i^h)=2$. $\text {dist}(f^{3-h}(i,j',a_r),x)=\text {min }(|P^{3-h}(i,j,a_r)|+1+|P(s_i^j,p_i^h)|-\ell _x,3+|P(\pi _i^{3-h},c_r)|+|P(c_r,\pi _i^h)|+\ell _x)= \text {min }(40(n+1)+1-\ell _x,20(n+1)+3+\ell _x)\ge 20(n+1)+1>\text {dist}(f^{3-h}(i,j',a_r),y)$. Thus in this case, every pair $\{x,y\}$ is resolved by $f^{3-h}(i,j',a_r)$. Case 2: $j\ne j'$. $\text {dist}(f^{3-h}(i,j',a_r),y)=\ell _y$ if $y\ne \pi _i^h$, $\text {dist}(f^h(i,j',a_r),\pi _i^h)=2$. $\text {dist}(f^{3-h}(i,j',a_r),x)=\text {min }(3+|P(s_i^j,p_i^{3-h})|+|P(s_i^j,p_i^h)|-\ell _x,3+|P(\pi _i^{3-h},c_r)|+|P(c_r,\pi _i^h)|+\ell _x)= \text {min }(40(n+1)+3-\ell _x,20(n+1)+3+\ell _x)\ge 20(n+1)+3>\text {dist}(f^{3-h}(i,j',a_r),y)$. Thus in this case, every pair $\{x,y\}$ is resolved by $f^{3-h}(i,j',a_r)$. It follows that every pair $\{x,y\}$ is resolved by $f^{3-h}(i,j',a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P^{3-h}(i,j',b_r)$, $P(s_i^j,p_i^h)\times P^{3-h}(i,j',c_r)$ and $P(s_i^j,p_i^h)\times P^{3-h}(i,j',p_i^h)$ are resolved by $\mathcal{S}'$.

Finally we show that every pair $\{x,y\}\in U_i^h\times \bigcup _{j\in [m],r\in \{1,2,3\}}\Pi ^{h'}(i',j,r)$ for $i,i'\in [n],h,h'\in \{1,2\}$ such that $i\ne i'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m]$, $h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P^{h'}(i',j',a_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ in the first paragraph. Let $j^*\in [m]$ be an integer such that $j^*\ne j'$. Then $\text {dist}(f^{h'}(i',j^*,a_r),y)=2+\ell _y$. $\text {dist}(f^{h'}(i',j^*,a_r),s_i^j)=\text {min}_{r'\in \{1,2,3\}}(2+|P(\pi _{i'}^{h'},c_{r'})|+|P(s_i^j,c_{r'})|)$. $\text {dist}(f^{h'}(i',j^*,a_r),x)=\text {min }(\text {dist}(f^{h'}(i',j^*,a_r),s_i^j)+|P(s_i^j,\pi _i^h)|-\ell _x,3+|P(\pi _{i'}^{h'},c_r)|+|P(\pi _i^h,c_r)|+\ell _x)>2+20(n+1)\ge \text {dist}(f^{h'}(i',j^*,a_r),y)$. Thus every pair $\{x,y\}$ is resolved by $f^{h'}(i',j^*,a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P^{h'}(i',j',b_r)$, $P(s_i^j,p_i^h)\times P^{h'}(i',j',c_r)$ and $P(s_i^j,p_i^h)\times P^{h'}(i',j',p_{i'}^{3-h'})$ are resolved by $f^{h'}(i',j^*,a_r)$. This completes the proof for the lemma. $\square$

Lemma 17

Every pair $\{x,y\}\in \bigcup _{i\in [n]}U_i\times \bigcup _{i\in [n]}L_i$ is resolved by $\mathcal{S}'$.

Proof

First, we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ for $i\in [n],j\in [m]$ and $h\in \{1,2\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j\in [m]$ and $h\in \{1,2\}$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(x,p_i^h)$ be the subpath of $P(s_i^j,p_i^h)$ from x to $p_i^h$ and $|P(x,p_i^h)|=\ell _x$. For a vertex $y\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, let $P(y,q_i^h)$ be the subpath of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from y to $q_i^h$ and $|P(y,q_i^h)|=\ell _y$. Then $\text {dist}(f^h(i,j,a_1),x)=3+\ell _x$. $\text {dist}(f^h(i,j,a_1),y)=3+\ell _y$. Thus every pair $\{x,y\}$ is resolved by $f^h(i,j,a_1)$ unless $\ell _x=\ell _y$. Suppose that $\mathcal{S}'\cap X_i=\{s_i^{j^*}\}$. For the pair $\{x,y\}$ such that $\ell _x=\ell _y$, there are two cases. Case 1: $j^*=j$. Then $\text {dist}(s_i^{j^*},x)=|P(s_i^j,p_i^h)|-\ell _x=20(n+1)-\ell _x$. $\text {dist}(s_i^{j^*},y)=\text {min }(|P(s_i^j,p_i^h)|+2+\ell _y,1+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _y)= \text {min }(20(n+1)+2+\ell _y,40(n+1)-\ell _y)\ne 20(n+1)-\ell _y$. Thus in this case every pair $\{x,y\}$ such that $\ell _x=\ell _y$ is resolved by $s_i^{j^*}$. Case 2: $j^*\ne j$. $\text {dist}(s_i^{j^*},s_i^j)=\text {min}_{r\in \{1,2,3\}}(|P(s_i^{j^*},c_r)|+|P(s_i^j,c_r)|)=20(n+1)-10\lambda ^*+20(n+1)-10\lambda$ for some $\lambda ,\lambda ^*\in [n]$. Then $\text {dist}(s_i^{j^*},x)=\text {min}(|P(s_i^{j^*},p_i^h)|+\ell _x,\text {dist}(s_i^{j^*},s_i^j)+|P(s_i^j,p_i^h)|-\ell _x)=\text {min}(20(n+1)+\ell _x,60(n+1)-10\lambda -10\lambda ^*-\ell _x)$. $\text {dist}(s_i^{j^*},y)=\text {min }(|P(s_i^{j^*},p_i^h)|+2+\ell _y,|P(s_i^{j^*},p_i^{3-h})|+1+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _y)= \text {min }(20(n+1)+2+\ell _y,60(n+1)-\ell _y)$. Thus every pair $\{x,y\}$ such that $\ell _x=\ell _y$ is resolved by $s_i^{j^*}$. As a result, every pair $\{x,y\}$ is resolved by $f^h(i,j,a_1)$ or $s_i^{j^*}$.

Next we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))$ for $i\in [n],j,j'\in [m]$ and $h\in \{1,2\}$ such that $j\ne j'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m]$ and $h\in \{1,2\}$ such that $j\ne j'$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^h)))$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. $\text {dist}(f^{mid}(i,j',3-h),y)=1+|P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))|-\ell _y=30(n+1)-\ell _y$. $\text {dist}(f^{mid}(i,j',3-h),x)=\text {min }(1+|P^{3-h}(i,j',p_i^h)|/2+|P(s_i^{j'},p_i^h)|-1+\ell _x,2+|P^{3-h}(i,j',p_i^h)|/2+|P(s_i^{j'},p_i^{3-h})|+|P(s_i^{j'},p_i^h)|-\ell _x)= \text {min }(30(n+1)+\ell _x,2+50(n+1)-\ell _x)$. Thus every pair $\{x,y\}$ is resolved by $f^{mid}(i,j',3-h)$ unless $\ell _x=\ell _y=0$, i.e. except the pair $\{p_i^h,q_i^h\}$. According to Lemma 4, $\{p_i^h,q_i^h\}$ is resolved by $\mathcal{S}'$. Thus every pair $\{x,y\}$ is resolved by $\mathcal{S}'$.

Then we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times P(q_i^{3-h},\text {mid}(P^h(i,j',p_i^{3-h})))$ for $i\in [n],j,j'\in [m]$ and $h\in \{1,2\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m]$ and $h\in \{1,2\}$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(q_i^{3-h},\text {mid}(P^h(i,j',p_i^{3-h})))$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Let $j^*\in [m]$ be an integer such that $j^*\ne j$. Then $\text {dist}(f^{3-h}(i,j^*,a_1),y)=3+\ell _y$. $\text {dist}(f^{3-h}(i,j^*,a_1),x)=\text {min }(1+|P^{3-h}(i,j,a_1)|+|P(s_i^j,p_i^h)|-\ell _x,3+|P(\pi _i^{3-h},a_1)|+|P(\pi _i^h,a_1)|+\ell _x)= \text {min }(40(n+1)+1-\ell _x,20(n+1)+3+\ell _x)\ge 20(n+1)+2$ if $x\ne s_i^j$ and $\text {dist}(f^{3-h}(i,j^*,a_1),s_i^j)=3+20(n+1)$. Thus any pair $\{x,y\}$ such that $\ell _y<20(n+1)-1$ is resolved by $f^{3-h}(i,j^*,a_1)$. For the pair $\{x,y\}$ such that $20(n+1)-1\le \ell _y\le 30(n+1)-1$, $\text {dist}(f^{mid}(i,j',h),y)=1+|P(q_i^{3-h},\text {mid}(P^h(i,j',p_i^{3-h})))|-\ell _y=30(n+1)-\ell _y\le 10(n+1)+1$. If $j'=j$, then $\text {dist}(f^{mid}(i,j',h),x)=\text {min }(2+|P^h(i,j,p_i^{3-h})|/2+\ell _x,2+|P^h(i,j,p_i^{3-h})|/2+|P(s_i^j,p_i^h)|-\ell _x)= \text {min }(2+10(n+1)+\ell _x,2+30(n+1)-\ell _x)\ge 10(n+1)+2$. If $j'\ne j$, then $\text {dist}(f^{mid}(i,j',h),x)=2+|P^h(i,j,p_i^{3-h})|/2+\ell _x\ge 10(n+1)+2$. As a result, every pair $\{x,y\}$ is resolved by $f^{3-h}(i,j^*,a_1)$ or $f^{mid}(i,j',h)$.

Finally we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))$ for $i,i'\in [n],j,j'\in [m]$ and $h,h'\in \{1,2\}$ such that $i\ne i'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m]$ and $h,h'\in \{1,2\}$ such that $i\ne i'$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Then $\text {dist}(f^h(i,j,a_1),x)=3+\ell _x$ if $x\ne s_i^j$ and $\text {dist}(f^h(i,j,a_1),s_i^j)=2+20(n+1)$. $\text {dist}(f^h(i,j,a_1),y)=\text {min }(3+|P(\pi _i^h,a_1)|+|P(\pi _{i'}^{h'},a_1)|+\ell _y,2+|P(\pi _i^h,a_1)|+|P(\pi _{i'}^{3-h'},a_1)|+|P^{3-h'}(i',j',p_{i'}^{h'})|/2+|P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))|-\ell _y) =\text {min }(3+20(n+1)+\ell _y,1+60(n+1)-\ell _y)\ge 3+20(n+1)>\text {dist}(f^h(i,j,a_1),x)$. Thus every pair $\{x,y\}$ is resolved by $f^h(i,j,a_1)$. This completes the proof for the lemma. $\square$

Lemma 18

Every pair $\{x,y\}\in \bigcup _{i\in [n]}U_i\times \bigcup _{i\in [n]}S_i$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(\pi _{i'}^{h'},a_r)\cup P(\pi _{i'}^{h'},c_r))$ for $i,i'\in [n],j\in [m],h'\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m]$,$h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(\pi _{i'}^{h'},a_r)$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(x,p_i^h)$ be the subpath of $P(s_i^j,p_i^h)$ from x to $p_i^h$ and $|P(x,p_i^h)|=\ell _x$. For a vertex $y\in P(\pi _{i'}^{h'},a_r)$, let $P(y,\pi _{i'}^{h'})$ be the subpath of $P(\pi _{i'}^{h'},a_r)$ from y to $\pi _{i'}^{h'}$ and $|P(y,\pi _{i'}^{h'})|=\ell _y$. Then $\text {dist}(f(s_i^j,a_r),y)=2+|P(\pi _{i'}^{h'},a_r)|-\ell _y$. Suppose that $|P(s_i^j,a_r)|=20(n+1)+10p$ for some $p\in [n]$. $\text {dist}(f(s_i^j,a_r),x)=\text {min }(3+|P(\pi _i^h,a_r)|+\ell _x,|P(s_i^j,a_r)|+|P(s_i^j,p_i^h)|-\ell _x)=\text {min }(3+10(n+1)+\ell _x,40(n+1)+10p-\ell _x)\ge 3+10(n+1)>\text {dist}(f(s_i^j,a_r),y)$. Thus every pair $\{x,y\}$ is resolved by $f(s_i^j,a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(\pi _{i'}^{h'},c_r)$ for $i,i'\in [n],j\in [m],h'\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $f(s_i^j,c_r)$. This completes the proof for the lemma. $\square$

Lemma 19

Every pair $\{x,y\}\in \bigcup _{i\in [n]}U_i\times \bigcup _{i\in [n]}H_i$ is resolved by $\mathcal{S}'$.

Proof

First we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(s_i^j,a_r)\cup P(s_i^j,c_r))$ for $i\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(s_i^j,a_r)$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(s_i^j,x)$ be the subpath of $P(s_i^j,p_i^h)$ from $s_i^j$ to x and $|P(s_i^j,x)|=\ell _x$. For a vertex $y\in P(s_i^j,a_r)$, let $P(s_i^j,y)$ be the subpath of $P(s_i^j,a_r)$ from $s_i^j$ to y and $|P(s_i^j,y)|=\ell _y$. Let $|P(s_i^j,a_r)|=20(n+1)+10\lambda$ for some $\lambda \in [n]$. Then $\text {dist}(f(s_i^j,a_r),x)=\text {min }(3+|P(\pi _i^h,a_r)|+|P(s_i^j,p_i^h)|-\ell _x,|P(s_i^j,a_r)|+\ell _x)=\text {min }(3+30(n+1)-\ell _x,20(n+1)+10\lambda +\ell _x)$. $\text {dist}(f(s_i^j,a_r),y)=|P(s_i^j,a_r)|-\ell _y=20(n+1)+10\lambda -\ell _y$. $\text {dist}(f(\pi _i^h,a_r),x)=\text {min }(1+|P(\pi _i^h,a_r)|+|P(s_i^j,p_i^h)|-\ell _x,2+|P(s_i^j,a_r)|+\ell _x)=\text {min }(1+30(n+1)-\ell _x,2+20(n+1)+10\lambda +\ell _x)$. $\text {dist}(f(\pi _i^h,a_r),y)=2+|P(s_i^j,a_r)|-\ell _y=2+20(n+1)+10\lambda -\ell _y$. For the pair $\{x,y\}$ which is not resolved by $f(s_i^j,a_r)$, it satisfies that $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),y)=3+|P(\pi _i^h,a_r)|+|P(s_i^j,p_i^h)|-\ell _x$. Thus $\text {dist}(f(\pi _i^h,a_r),x)<\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),y)<\text {dist}(f(\pi _i^h,a_r),y)$. It follows that every pair $\{x,y\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(s_i^j,c_r)$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$.

Next we show that every vertex pair of $P(s_i^j,p_i^h)\times P(s_i^j,b_r)$ for $i\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)\setminus \{s_i^j\}$ and $y\in P(s_i^j,b_r)\setminus \{s_i^j\}$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Then $\text {dist}(f^{mid}(i,j,3-h),x)=|P^{3-h}(i,j,p_i^h)|/2+\ell _x=10(n+1)+\ell _x$ and $\text {dist}(f^{mid}(i,j,3-h),y)=2+|P^{3-h}(i,j,p_i^h)|/2+\ell _y=2+10(n+1)+\ell _y$. For the vertex pair $\{x,y\}$ which is not resolved by $f^{mid}(i,j,3-h)$, i.e. $\ell _x=2+\ell _y$, $\text {dist}(f^{mid}(i,j,h),x)=2+|P^h(i,j,p_i^{3-h})|/2+\ell _x=2+10(n+1)+\ell _x>\text {dist}(f^{mid}(i,j,h),y)=2+|P^h(i,j,p_i^{3-h})|/2+\ell _y=10(n+1)+2+\ell _y=10(n+1)+\ell _x$. Thus every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$ or $f^{mid}(i,j,h)$.

Then we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(s_{i'}^{j'},a_r)\cup P(s_{i'}^{j'},c_r))$ for $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$ or $j\ne j'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$ or $j\ne j'$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(s_{i'}^{j'},a_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Let $|P(s_i^j,a_r)|=20(n+1)+10\lambda$ and $|P(s_{i'}^{j'},a_r)|=20(n+1)+10\lambda '$ for some $\lambda ,\lambda '\in [n]$. Then $\text {dist}(f(s_{i'}^{j'},a_r),x)=\text {dist}(f(\pi _{i'}^{3-h},a_r),x)=\text {min }(3+|P(\pi _i^h,a_r)|+|P(s_i^j,p_i^h)|-\ell _x,2+|P(s_i^j,a_r)|+\ell _x)=\text {min }(3+30(n+1)-\ell _x,2+20(n+1)+10\lambda +\ell _x)$. $\text {dist}(f(s_{i'}^{j'},a_r),y)=\text {dist}(f(\pi _{i'}^{3-h},a_r),y)-2=|P(s_{i'}^{j'},a_r)|-\ell _y$ if $y\ne a_r$ and $\text {dist}(f(s_{i'}^{j'},a_r),a_r)=\text {dist}(f(\pi _{i'}^{3-h},a_r),a_r)=2$. It follows that every pair $\{x,y\}$ is resolved by $f(s_{i'}^{j'},a_r)$ or $f(\pi _{i'}^{3-h},a_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(s_{i'}^{j'},c_r)$ is resolved by $f(s_{i'}^{j'},c_r)$ or $f(\pi _{i'}^{3-h},c_r)$.

Finally we show that every vertex pair of $P(s_i^j,p_i^h)\times P(s_{i'}^{j'},b_r)$ for $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$ or $j\ne j'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$ or $j\ne j'$. Suppose that $x\in P(s_i^j,p_i^h)$ and $y\in P(s_{i'}^{j'},b_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Let $|P(s_i^j,b_r)|=20(n+1)+5\lambda +1$ and $|P(s_{i'}^{j'},b_r)|=20(n+1)+5\lambda '+1$ and for some $\lambda ,\lambda '\in [n]$. There are two cases. Case 1: $i=i'$ and $j\ne j'$. $\text {dist}(f^{mid}(i,j,3-h),x)=|P^{3-h}(i,j,p_i^h)|/2+\ell _x=10(n+1)+\ell _x$ if $x\ne s_i^j$ and $\text {dist}(f^{mid}(i,j,3-h),s_i^j)=2+10(n+1)$. $\text {dist}(f^{mid}(i,j,3-h),y)=\text {min }(2+|P^{3-h}(i,j,p_i^h)|/2+|P(s_{i'}^{j'},p_i^{3-h})|+\ell _y,2+|P^{3-h}(i,j,p_i^h)|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _y) =\text {min }(2+30(n+1)+\ell _y,4+50(n+1)+5\lambda +5\lambda '-\ell _y)\ge 2+30(n+1)>\text {dist}(f^{mid}(i,j,3-h),x)$. Thus in this case, every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$. Case 2: $i\ne i'$. $\text {dist}(f^{mid}(i,j,3-h),s_{i'}^{j'})=1+|P^{3-h}(i,j,p_i^h)|/2+\text {min}_{r\in \{1,2,3\}}(|P(\pi _i^{3-h},c_r)|+|P(s_{i'}^{j'},c_r)|)$. $\text {dist}(f^{mid}(i,j,3-h),y)=\text {min }(\text {dist}(f^{mid}(i,j,3-h),s_{i'}^{j'})+\ell _y,2+|P^{3-h}(i,j,p_i^h)|/2+|P(s_i^j,b_r)|+|P(s_{i'}^{j'},b_r)|-\ell _y) =\text {min }(1+40(n+1)-10\lambda '+\ell _y,4+50(n+1)+5\lambda +5\lambda '-\ell _y)>30(n+1)+5>\text {dist}(f^{mid}(i,j,3-h),x)$. Thus in this case, every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$. It follows that every pair $\{x,y\}$ is resolved by $f^{mid}(i,j,3-h)$. This completes the proof for the lemma. $\square$

Lemma 20

Every pair $\{x,y\}\in \bigcup _{i\in [n]}U_i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

First we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(u_r^{i'},a_r)\cup P(v_r^{i'},a_r))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$, $y\in P(u_r^{i'},a_r)$. For a vertex $x\in P(s_i^j,p_i^h)$, let $P(s_i^j,x)$ be the subpath of $P(s_i^j,p_i^h)$ from $s_i^j$ to x and $|P(s_i^j,x)|=\ell _x$. For a vertex $y\in P(a_r,u_r^{i'})$, let $P(u_r^{i'},y)$ be the subpath of $P(a_r,u_r^{i'})$ from $u_r^{i'}$ to y and $|P(u_r^{i'},y)|=\ell _{y}$. Let $|P(s_i^j,a_r)|=20(n+1)+10\lambda$ for some $\lambda \in [n]$ and $|P(u_r^{i'},a_r)|=20(n+1)-10i'$. There are two cases. Case 1: $\lambda \le i'$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {min }(1+|P(a_r,u_r^{i'})|+|P(s_i^j,a_r)|+\ell _x,1+|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)= \text {min }(40(n+1)-10(i'-\lambda )+1+\ell _x,50(n+1)+1-10i'-\ell _x)$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=1+\ell _{y}$ if $y\ne u_r^{i'}$ and $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=2$ if $y=u_r^{i'}$. Thus $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)\ge 30(n+1)-10i'+1>\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)$. Case 2: $\lambda >i'$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {min }(1+|P(c_r,u_r^{i'})|+|P(s_i^j,c_r)|+\ell _x,1+|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)= \text {min }(40(n+1)-10(\lambda -i')+1+\ell _x,50(n+1)+1-10i'-\ell _x)$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=1+\ell _{y}$ if $y\ne u_r^{i'}$ and $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=2$ if $y=u_r^{i'}$. Thus $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)\ge 30(n+1)-10i'+1>\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)$. Thus every pair $\{x,y\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(v_r^{i'},a_r)$ is resolved by $f^1(u_r^{i'},v_r^{i'})$.

Next we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(u_r^{i'},b_r)\cup P(v_r^{i'},b_r))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$, $y\in P(u_r^{i'},b_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Let $|P(s_i^j,a_r)|=20(n+1)+10\lambda$ for some $\lambda \in [n]$ and $|P(u_r^{i'},a_r)|=20(n+1)-10i'$. There are two cases. Case 1: $\lambda \le i'$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {min }(1+|P(a_r,u_r^{i'})|+|P(s_i^j,a_r)|+\ell _x,1+|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)$. $\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)=\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)-1=\text {min }(|P(a_r,u_r^{i'})|+|P(s_i^j,a_r)|+\ell _x,|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=\text {dist}(f^2(u_r^{i'},v_r^{i'}),y)=2+\ell _{y}$. In this case, for a pair $\{x,y\}$ which is not resolved by $f^1(u_r^{i'},v_r^{i'})$, $\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)=\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)-1<\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=\text {dist}(f^2(u_r^{i'},v_r^{i'}),y)$. Case 2: $\lambda >i'$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {min }(1+|P(c_r,u_r^{i'})|+|P(s_i^j,c_r)|+\ell _x,1+|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)$. $\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)=\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)-1=\text {min }(|P(c_r,u_r^{i'})|+|P(s_i^j,c_r)|+\ell _x,|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+|P(s_i^j,\pi _i^h)|-\ell _x)$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y)=\text {dist}(f^2(u_r^{i'},v_r^{i'}),y)=2+\ell _{y}$. Similar to Case 1, in this case, for a pair $\{x,y\}$ which is not resolved by $f^1(u_r^{i'},v_r^{i'})$, $\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)<\text {dist}(f^2(u_r^{i'},v_r^{i'}),y)$. Thus every pair $\{x,y\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$ or $f^2(u_r^{i'},v_r^{i'})$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(v_r^{i'},b_r)$ is resolved by $f^1(u_r^{i'},v_r^{i'})$ or $f^2(u_r^{i'},v_r^{i'})$.

Finally we show that every pair $\{x,y\}\in P(s_i^j,p_i^h)\times (P(u_r^{i'},c_r)\cup P(v_r^{i'},c_r))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,p_i^h)$, $y\in P(u_r^{i'},c_r)$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Let $|P(s_i^j,c_r)|=20(n+1)-10\lambda$ for some $\lambda \in [n]$ and $|P(u_r^{i'},c_r)|=20(n+1)+10i'$. Then $\text {dist}(f(s_i^j,c_r),x)=\text {min }(3+|P(\pi _i^h,c_r)|+|P(s_i^j,p_i^h)|-\ell _x,|P(s_i^j,c_r)|+\ell _x)=\text {min }(3+30(n+1)-\ell _x,20(n+1)-10\lambda +\ell _x)$. $\text {dist}(f(\pi _i^h,c_r),x)=\text {min }(1+|P(\pi _i^h,c_r)|+|P(s_i^j,p_i^h)|-\ell _x,2+|P(s_i^j,c_r)|+\ell _x)=\text {min }(1+30(n+1)-\ell _x,2+20(n+1)-10\lambda +\ell _x)$. $\text {dist}(f(\pi _i^{3-h},c_r),x)=\text {min }(3+|P(\pi _i^h,c_r)|+|P(s_i^j,p_i^h)|-\ell _x,2+|P(s_i^j,c_r)|+\ell _x)=\text {min }(3+30(n+1)-\ell _x,2+20(n+1)-10\lambda +\ell _x)$. $\text {dist}(f(s_i^j,c_r),y)=\text {dist}(f(\pi _i^h,c_r),y)=\text {dist}(f(\pi _i^{3-h},c_r),y)=2+|P(c_r,u_r^{i'})|-\ell _y=2+20(n+1)+10i'-\ell _y$. For a pair $\{x,y\}$ which is not resolved by $f(s_i^j,c_r)$, either $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$ resolves it. Thus every pair $\{x,y\}$ is resolved by $f(s_i^j,c_r)$, $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$. Similarly, we can show that every vertex pair of $P(s_i^j,p_i^h)\times P(v_r^{i'},c_r)$ is resolved by $f(s_i^j,c_r)$, $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$. This completes the proof for the lemma. $\square$

Lemma 21

Every pair $\{x,y\}\in \bigcup _{i\in [n]}\Pi _i\times \bigcup _{i\in [n]}H_i$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times (P(s_{i'}^{j'},a_{r'})\cup P(s_{i'}^{j'},b_{r'})\cup P(s_{i'}^{j'},c_{r'}))$ for $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $y_1\in P(s_{i'}^{j'},a_{r'})$, $y_2\in P(s_{i'}^{j'},b_{r'})$ and $y_3\in P(s_{i'}^{j'},c_{r'})$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex $y_{\nu }$ for $\nu \in \{1,2,3\}$, let $\ell _{y_{\nu }}=\text {dist}(s_i^j,y_{\nu })$. Let $|P(s_i^j,a_{r'})|=20(n+1)+10\lambda$ and $|P(s_{i'}^{j'},a_{r'})|=20(n+1)+10\lambda '$ for some $\lambda ,\lambda '\in [n]$. There are three cases. Case 1: $s_i^j=s_{i'}^{j'}$ and $r'=r$. Then $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_r)|+\ell _{x_1},|P(s_i^j,a_r)|+|P^{h}(i,j,a_r)|-1-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda -1-\ell _{x_1})$. $\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=|P(s_i^j,a_r)|-\ell _{y_1}=20(n+1)+10\lambda -\ell _{y_1}$ if $y_1\ne a_r$ and $\text {dist}(f(s_{i'}^{j'},a_{r'}),a_r)=2$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_r)|+\ell _{x_1},1+|P(s_i^j,a_r)|+|P^{h}(i,j,a_r)|-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +1-\ell _{x_1})$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)=2+|P(s_i^j,a_r)|-\ell _{y_1}=20(n+1)+10\lambda +2-\ell _{y_1}$. Let $\gamma \in P^h(i,j,a_r)$ be the vertex such that $\text {dist}(\gamma ,\pi _i^h)=20(n+1)-1$. Obviously the pair $\{s_i^j,\gamma \}$ is resolved by $f^h(i,j,a_r)$. For the pair $\{x_1,y_1\}$ which is not resolved by $f(s_{i'}^{j'},a_{r'})$ and $y_1\ne s_i^j$, it satisfies that $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)<\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)$. Thus in this case, every pair $\{x_1,y_1\}$ is resolved by $f(s_{i'}^{j'},a_{r'})$, $f(\pi _i^{3-h},a_{r'})$ or $f^h(i,j,a_r)$. Case 2: $s_i^j\ne s_{i'}^{j'}$ and $r'=r$. Then $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},1+|P(s_i^j,a_{r'})|+|P^{h}(i,j,a_{r'})|-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +1-\ell _{x_1})$. $\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=|P(s_{i'}^{j'},a_{r'})|-\ell _{y_1}=20(n+1)+10\lambda '-\ell _{y_1}$ if $y_1\ne a_{r'}$ and $\text {dist}(f(s_{i'}^{j'},a_{r'}),a_{r'})=2$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},|P(s_i^j,a_{r'})|+|P^{h}(i,j,a_{r'})|+1-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +1-\ell _{x_1})$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)=2+|P(s_{i'}^{j'},a_{r'})|-\ell _{y_1}=20(n+1)+10\lambda '+2-\ell _{y_1}$. For the pair $\{x_1,y_1\}$ which is not resolved by $f(s_{i'}^{j'},a_{r'})$, it satisfies that $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)<\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)$. Thus in this case, every pair $\{x_1,y_1\}$ is resolved by $f(s_{i'}^{j'},a_{r'})$ or $f(\pi _i^{3-h},a_{r'})$. Case 3: $s_i^j\ne s_{i'}^{j'}$ and $r'\ne r$. Then $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},2+|P(s_i^j,a_{r'})|+1+|P^{h}(i,j,a_{r'})|-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +3-\ell _{x_1})$. $\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=|P(s_{i'}^{j'},a_{r'})|-\ell _{y_1}=20(n+1)+10\lambda '-\ell _{y_1}$ if $y_1\ne a_{r'}$ and $\text {dist}(f(s_{i'}^{j'},a_{r'}),a_{r'})=2$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},2+|P(s_i^j,a_{r'})|+1+|P^{h}(i,j,a_{r'})|-\ell _{x_1})=\text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +3-\ell _{x_1})$. $\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)=2+|P(s_{i'}^{j'},a_{r'})|-\ell _{y_1}=20(n+1)+10\lambda '+2-\ell _{y_1}$. For the pair $\{x_1,y_1\}$ which is not resolved by $f(s_{i'}^{j'},a_{r'})$, it satisfies that $\text {dist}(f(s_{i'}^{j'},a_{r'}),x_1)=\text {dist}(f(s_{i'}^{j'},a_{r'}),y_1)=\text {dist}(f(\pi _i^{3-h},a_{r'}),x_1)<\text {dist}(f(\pi _i^{3-h},a_{r'}),y_1)$. Thus in this case, every pair $\{x_1,y_1\}$ is resolved by $f(s_{i'}^{j'},a_{r'})$ or $f(\pi _i^{3-h},a_{r'})$. It follows that every pair $\{x_1,y_1\}$ is resolved by $f^h(i,j,a_r)$, $f(s_{i'}^{j'},a_{r'})$ or $f(\pi _i^{3-h},a_{r'})$. In a similar way, we can show that every vertex pair $\{x_2,y_1\}$, $\{x_3,y_1\}$ and $\{x_4,y_1\}$ are resolved by $\mathcal{S}'$. Also in a similar way, we can show that every vertex pair $\{x_1,y_3\}$, $\{x_2,y_3\}$, $\{x_3,y_3\}$ and $\{x_4,y_3\}$ are resolved by $f(s_{i'}^{j'},c_{r'})$, $f(\pi _i^{3-h},c_{r'})$ or $f^h(i,j,c_r)$. For a pair $\{x_1,y_2\}$, $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ if $x_1\ne \pi _i^h$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),b_{r'})=2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},v_{r'}^n)|+|P(b_{r'},v_{r'}^n)|+|P(s_{i'}^{j'},b_{r'})|-\ell _{y_2}$. There are three cases. Case 1: $i=i'$ and $j=j'$. $\text {dist}(f^h(i,j,a_r),y_2)=\text {min }(|P^h(i,j,a_r)|+1+\ell _{y_2},\text {dist}(f^h(i,j,a_r),b_{r'})+|P(s_{i'}^{j'},b_{r'})|-\ell _{y_2})= \text {min }(20(n+1)+1+\ell _{y_2},55n+5\lambda +71-\ell _{y_2})>\text {dist}(f^h(i,j,a_r),x_1)$. Thus in this case, every pair $\{x_1,y_2\}$ is resolved by $f^h(i,j,a_r)$. Case 2: $i'=i$ and $j\ne j'$. Then $\text {dist}(f^h(i,j,a_r),y_2)=\text {min }(2+|P^h(i,j,b_{r'})|+\ell _{y_2}-1,\text {dist}(f^h(i,j,a_r),b_{r'})+|P(s_{i'}^{j'},b_{r'})|-\ell _{y_2})= \text {min }(20(n+1)+1+\ell _{y_2},55n+5\lambda +71-\ell _{y_2})$ if $y_2\ne s_{i'}^{j'}$ and $\text {dist}(f^h(i,j,a_r),s_{i'}^{j'})=3+20(n+1)$. Thus $\text {dist}(f^h(i,j,a_r),y_2)\ge 20(n+1)+2>\text {dist}(f^h(i,j,a_r),x_1)$. In this case, every pair $\{x_1,y_2\}$ is resolved by $f^h(i,j,a_r)$. Case 3: $i'\ne i$. $\text {dist}(f^h(i,j,a_r),s_{i'}^{j'})=\text {min}_{d\in \{1,2,3\}}(2+|P(\pi _i^h,c_d)|+|P(s_{i'}^{j'},c_d)|)$. $\text {dist}(f^h(i,j,a_r),y_2)=\text {min }(\text {dist}(f^h(i,j,a_r),s_{i'}^{j'})+\ell _{y_2},\text {dist}(f^h(i,j,a_r),b_{r'})+|P(s_{i'}^{j'},b_{r'})|-\ell _{y_2})> 20(n+1)\ge \text {dist}(f^h(i,j,a_r),x_1)$. Thus in this case, every pair $\{x_1,y_2\}$ is resolved by $f^h(i,j,a_r)$. In a similar way, we can show that every vertex pair $\{x_2,y_2\}$, $\{x_3,y_2\}$ and $\{x_4,y_2\}$ are resolved by $\mathcal{S}'$. This completes the proof for the lemma. $\square$

Lemma 22

Every pair $\{x,y\}\in \bigcup _{i\in [n]}\Pi _i\times \bigcup _{i\in [n]}L_i$ is resolved by $\mathcal{S}'$.

Proof

First we show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))$ for $i\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $y\in P(q_i^h,\text {mid}(P^{3-h}(i,j',p_i^{h})))$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex y, let $\ell _y=\text {dist}(q_i^h,y)$. Then $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ if $x_1\ne \pi _i^h$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),y)=\text {dist}(f^h(i,j,b_r),y)=\text {dist}(f^h(i,j,c_r),y)=\text {dist}(f^h(i,j,p_i^{3-h}),y)=3+\ell _y$. For the pair $\{x_1,y\}$ that is not resolved by $f^h(i,j,a_r)$, $\text {dist}(f^h(i,j,b_r),y)=\text {dist}(f^h(i,j,a_r),y)=\text {dist}(f^h(i,j,a_r),x_1)=\text {dist}(f^h(i,j,b_r),x_1)-2<\text {dist}(f^h(i,j,b_r),x_1)$. Thus every pair $\{x_1,y\}$ is resolved by $f^h(i,j,a_r)$ or $f^h(i,j,b_r)$. In a similar way, we can show that every vertex pair $\{x_2,y\}$, $\{x_3,y\}$ and $\{x_4,y\}$ are resolved by $\mathcal{S}'$.

Next we show that every pair $\{x,y\}\in P(q_i^{3-h},\text {mid}(P^{h}(i,j',p_i^{3-h})))\times (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))$ for $i\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ $x_4\in P^{h}(i,j,p_i^{3-h})$ and $y\in P(q_i^{3-h},\text {mid}(P^{h}(i,j',p_i^{3-h})))$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex y, let $\ell _y=\text {dist}(q_i^{3-h},y)$. Then $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ if $x_1\ne \pi _i^h$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),y)=\text {dist}(f^h(i,j,b_r),y)=\text {dist}(f^h(i,j,c_r),y)= \text {min }(2+|P^h(i,j',p_i^{3-h})|/2+|P(q_i^{3-h},\text {mid}(P^{h}(i,j',p_i^{3-h})))|-\ell _y,2+|P(\pi _i^h,a_r)|+|P(\pi _i^{3-h},a_r)|+1+\ell _y)= \text {min }(1+40(n+1)-\ell _y,3+20(n+1)+\ell _y)$. For the pair $\{x_1,y\}$ that is not resolved by $f^h(i,j,a_r)$, $\text {dist}(f^h(i,j,b_r),y)=\text {dist}(f^h(i,j,a_r),y)=\text {dist}(f^h(i,j,a_r),x_1)=\text {dist}(f^h(i,j,b_r),x_1)-2<\text {dist}(f^h(i,j,b_r),x_1)$. Thus every pair $\{x_1,y\}$ is resolved by $f^h(i,j,a_r)$ or $f^h(i,j,b_r)$. In a similar way, we can show that every vertex pair $\{x_2,y\}$ and $\{x_3,y\}$ are resolved by $\mathcal{S}'$. For the pair $\{x_4,y\}$, there are two cases. Case 1: $j'\ne j$. In this case, the analysis is similar to that of $\{x_1,y\}$ above and every pair $\{x_4,y\}$ is resolved by $f^h(i,j,p_i^{3-h})$ or $f^h(i,j,a_r)$. Case 2: $j'=j$. $\text {dist}(f^h(i,j,p_i^{3-h}),x_4)=\ell _{x_4}$ if $x_4\ne \pi _i^h$ and $\text {dist}(f^h(i,j,p_i^{3-h}),\pi _i^h)=2$. $\text {dist}(f^h(i,j,p_i^{3-h}),y)= \text {min }(|P^h(i,j',p_i^{3-h})|/2+|P(q_i^{3-h},\text {mid}(P^{h}(i,j',p_i^{3-h})))|-\ell _y,2+|P(\pi _i^h,a_r)|+|P(\pi _i^{3-h},a_r)|+1+\ell _y)= \text {min }(40(n+1)-1-\ell _y,3+20(n+1)+\ell _y)$. For the pair $\{x_4,y\}$ which is not resolved by $f^h(i,j,p_i^{3-h})$, it satisfies that $\text {dist}(f^h(i,j,p_i^{3-h}),x_4)=\text {dist}(f^h(i,j,p_i^{3-h}),y)=40(n+1)-1-\ell _y=\ell _{x_4}$, i.e. $\text {dist}(f^{mid}(i,j,h),x_4)=\text {dist}(f^{mid}(i,j,h),y)$ and $10(n+1)<\ell _{x_4}\le 20(n+1), 20(n+1)-1\le \ell _y<30(n+1)-1$. For such pairs, $\text {dist}(f^{ecc}(i,j,3-h,r),x_4)=2+30(n+1)-\ell _{x_4}<2+20(n+1)<\text {dist}(f^{ecc}(i,j,3-h,r),y)=50(n+1)+1-\ell _y$. Thus in this case, every pair $\{x_4,y\}$ is resolved by $f^h(i,j,p_i^{3-h})$ or $f^{ecc}(i,j,3-h,r)$.

Finally we show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))$ for $i,i'\in [n],j,j'\in [m],h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$ such that $i\ne i'$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $y\in P(q_{i'}^{3-h'},\text {mid}(P^{h'}(i',j',p_{i'}^{3-h'})))$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex y, let $\ell _y=\text {dist}(q_{i'}^{3-h'},y)$. For the pair $\{x_1,y\}$, $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ if $x_1\ne \pi _i^h$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),y)=\text {min }(2+|P(\pi _i^h,a_r)|+|P(\pi _{i'}^{h'},a_r)|+1+\ell _y,2+|P(\pi _i^h,a_r)|+|P(\pi _{i'}^{3-h'},a_r)|+|P^{3-h'}(i',j',p_{i'}^{h'})|/2+|P(q_{i'}^{h'},\text {mid}(P^{3-h'}(i',j',p_{i'}^{h'})))|-\ell _y)= \text {min }(3+20(n+1)+\ell _y,1+60(n+1)-\ell _y)\ge 3+20(n+1)>\text {dist}(f^h(i,j,a_r),x_1)$. Thus every pair $\{x_1,y\}$ is resolved by $f^h(i,j,a_r)$. Similarly, we can show that every pair $\{x_2,y\}$, $\{x_3,y\}$ and $\{x_4,y\}$ are resolved by $f^h(i,j,b_r)$, $f^h(i,j,c_r)$ and $f^h(i,j,p_i^{3-h})$ respectively. This completes the proof for the lemma. $\square$

Lemma 23

Every pair $\{x,y\}\in \bigcup _{i\in [n]}\Pi _i\times \bigcup _{i\in [n]}S_i$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times (P(\pi _{i'}^{h'},a_{r'})\cup P(\pi _{i'}^{h'},c_{r'}))$ for $i,i'\in [n],j\in [m],h,h'\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h,h'\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $y_1\in P(\pi _{i'}^{h'},a_{r'})$ and $y_2\in P(\pi _{i'}^{h'},c_{r'})$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex $y_1$, let $\ell _{y_1}=\text {dist}(a_{r'},y_1)$. For a vertex $y_2$, let $\ell _{y_2}=\text {dist}(c_{r'},y_2)$. Let $|P(s_i^j,a_{r'})|=20(n+1)+10\lambda$ for some $\lambda \in [n]$. For a pair $\{x_1,y_1\}$, $\text {dist}(f(s_i^j,a_{r'}),y_1)=2+\ell _{y_1}$. $\text {dist}(f(s_i^j,a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},|P(s_i^j,a_{r'})|-1+|P^{h}(i,j,a_r)|-\ell _{x_1})= \text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda -1-\ell _{x_1})$ if $r=r'$ and $\text {dist}(f(s_i^j,a_{r'}),x_1)=\text {min }(2+|P(\pi _i^h,a_{r'})|+\ell _{x_1},|P(s_i^j,a_{r'})|+1+|P^{h}(i,j,a_r)|-\ell _{x_1})= \text {min }(2+10(n+1)+\ell _{x_1},40(n+1)+10\lambda +1-\ell _{x_1})\ge 2+10(n+1)\ge \text {dist}(f(s_i^j,a_{r'}),y_1)$ if $r\ne r'$. It follows that $\text {dist}(f(s_i^j,a_{r'}),x_1)\ge 2+10(n+1)\ge \text {dist}(f(s_i^j,a_{r'}),y_1)$. $\text {dist}(f(s_i^j,a_{r'}),x_1)=\text {dist}(f(s_i^j,a_{r'}),y_1)$ only when $x_1=\pi _i^h$ and $y_1=\pi _{i'}^{h'}$. If $i'\ne i$ or $h'\ne h$, obviously the pair $\{\pi _i^h,\pi _{i'}^{h'}\}$ is resolved by $f^h(i,j,a_r)$. Thus every pair $\{x_1,y_1\}$ is resolved by $f(s_i^j,a_{r'})$ or $f^h(i,j,a_r)$. In a similar way, we can show that every vertex pair $\{x_2,y_1\}$, $\{x_3,y_1\}$ and $\{x_4,y_1\}$ are resolved by $f(s_i^j,a_{r'})$ or $f^h(i,j,a_r)$. Also in a similar way, we can show that every vertex pair $\{x_1,y_2\}$, $\{x_2,y_2\}$, $\{x_3,y_2\}$ and $\{x_4,y_2\}$ are resolved by $f(s_i^j,c_{r'})$ or $f^h(i,j,a_r)$. This completes the proof for the lemma. $\square$

Lemma 24

Every pair $\{x,y\}\in \bigcup _{i\in [n]}\Pi _i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times (P(u_{r'}^{i'},a_{r'})\cup P(v_{r'}^{i'},a_{r'})\cup P(u_{r'}^{i'},c_{r'})\cup P(v_{r'}^{i'},c_{r'}))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $y_1\in P(u_{r'}^{i'},a_{r'})$, $y_2\in P(v_{r'}^{i'},a_{r'})$, $z_1\in P(u_{r'}^{i'},c_{r'})$ and $z_2\in P(v_{r'}^{i'},c_{r'})$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex $y_{\nu }$ for $\nu \in \{1,2\}$, let $\ell _{y_{\nu }}=\text {dist}(a_{r'},y_{\nu })$. For a vertex $z_{\eta }$ for $\eta \in \{1,2\}$, let $\ell _{y_{\eta }}=\text {dist}(c_{r'},z_{\eta })$. Then $|P(u_{r'}^{i'},a_{r'})|=|P(v_{r'}^{i'},a_{r'})|=20(n+1)-10i'$ and $|P(u_{r'}^{i'},c_{r'})|=|P(v_{r'}^{i'},c_{r'})|=20(n+1)+10i'$. For a pair $\{x_1,y_1\}$, $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),y_1)=\text {dist}(f^h(i,j,b_r),y_1)=\text {dist}(f^h(i,j,c_r),y_1)=\text {dist}(f^h(i,j,p_i^{3-h}),y_1)=2+|P(\pi _i^h,a_{r'})|+\ell _{y_1}=2+10(n+1)+\ell _{y_1}$. For the pair $\{x_1,y_1\}$ that is not resolved by $f^h(i,j,a_r)$, $\text {dist}(f^h(i,j,a_r),x_1)=\text {dist}(f^h(i,j,a_r),y_1)=\text {dist}(f^h(i,j,b_r),y_1)=\text {dist}(f^h(i,j,b_r),x_1)-2$. Thus every pair $\{x_1,y_1\}$ is resolved by $f^h(i,j,a_r)$ or $f^h(i,j,b_r)$. In a similar way, we can show that every vertex pair $\{x_{\mu },y_{\nu }\}$ for $\mu \in \{1,2,3,4\},\nu \in \{1,2\}$ is resolved by $\mathcal{S}'$. For a pair $\{x_1,z_1\}$, $\text {dist}(f^h(i,j,a_r),x_1)=\ell _{x_1}$ and $\text {dist}(f^h(i,j,a_r),\pi _i^h)=2$. $\text {dist}(f^h(i,j,a_r),z_1)=\text {dist}(f^h(i,j,b_r),z_1)= \text {min }(2+|P(\pi _i^h,c_{r'})|+\ell _{z_1},2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(c_{r'},u_{r'}^{i'})|-2-\ell _{z_1})= \text {min }(2+10(n+1)+\ell _{z_1},50(n+1)-\ell _{z_1})$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_1}\ge 2$. $\text {dist}(f^h(i,j,a_r),z_1)=\text {dist}(f^h(i,j,b_r),z_1)=2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},u_{r'}^{i'})|+|P(c_{r'},u_{r'}^{i'})|-\ell _{z_1}$ if $|P(c_{r'},u_{r'}^{i'})|-\ell _{z_1}<2$. For the pair $\{x_1,z_1\}$ that is not resolved by $f^h(i,j,a_r)$, $\text {dist}(f^h(i,j,a_r),x_1)=\text {dist}(f^h(i,j,a_r),z_1)=\text {dist}(f^h(i,j,b_r),z_1)=\text {dist}(f^h(i,j,b_r),x_1)-2$. Thus every pair $\{x_1,z_1\}$ is resolved by $f^h(i,j,a_r)$ or $f^h(i,j,b_r)$. In a similar way, we can show that every vertex pair $\{x_{\mu },z_{\nu }\}$ for $\mu \in \{1,2,3,4\},\nu \in \{1,2\}$ is resolved by $\mathcal{S}'$.

Then we show that every pair $\{x,y\}\in (P^{h}(i,j,a_r)\cup P^{h}(i,j,b_r)\cup P^{h}(i,j,c_r)\cup P^{h}(i,j,p_i^{3-h}))\times (P(u_{r'}^{i'},b_{r'})\cup P(v_{r'}^{i'},b_{r'}))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P^{h}(i,j,a_r)$, $x_2\in P^{h}(i,j,b_r)$, $x_3\in P^{h}(i,j,c_r)$ and $x_4\in P^{h}(i,j,p_i^{3-h})$. Suppose that $w_1\in P(u_{r'}^{i'},b_{r'})$ and $w_2\in P(v_{r'}^{i'},b_{r'})$. For a vertex $x_{\mu }$ for $\mu \in \{1,2,3,4\}$, let $\ell _{x_{\mu }}=\text {dist}(\pi _i^h,x_{\mu })$. For a vertex $w_{\nu }$ for $\nu \in \{1,2\}$, let $\ell _{w_{\nu }}=\text {dist}(b_{r'},w_{\nu })$. Then let $|P(s_i^j,a_{r'})|=20(n+1)+10\lambda$ for some $\lambda \in [n]$, $|P(u_{r'}^{i'},b_{r'})|=20(n+1)-5i'-1$ and $|P(v_{r'}^{i'},b_{r'})|=20(n+1)-5i'-2$. For a pair $\{x_1,w_1\}$, $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),w_1)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),w_1)=2+|P(u_{r'}^{i'},b_{r'})|-\ell _{w_1}$. For the distance between $f^{\eta }(u_{r'}^{i'},v_{r'}^{i'})$ and $x_1$ for $\eta \in \{1,2\}$, there are two cases. Case 1: $\lambda \le i'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x_1)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),x_1)+1=\text {min }(1+|P(a_{r'},u_{r'}^{i'})|+|P(s_i^j,a_{r'})|-1+|P^h(i,j,a_r)|-\ell _{x_1},1+|P(a_{r'},u_{r'}^{i'})|+|P(\pi _i^h,a_{r'})|+\ell _{x_1})$ if $r=r'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x_1)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),x_1)+1=\text {min }(1+|P(a_{r'},u_{r'}^{i'})|+|P(s_i^j,a_{r'})|+1+|P^h(i,j,a_r)|-\ell _{x_1},1+|P(a_{r'},u_{r'}^{i'})|+|P(\pi _i^h,a_{r'})|+\ell _{x_1})$ if $r\ne r'$. In this case, for the pair $\{x_1,w_1\}$ which is not resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$, $\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),x_1)=\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x_1)-1<\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),y)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),y)$. Case 2: $\lambda >i'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x_1)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),x_1)+1=\text {min }(1+|P(c_{r'},u_{r'}^{i'})|+|P(s_i^j,c_{r'})|+1+|P^h(i,j,a_r)|-\ell _{x_1},1+|P(a_{r'},u_{r'}^{i'})|+|P(\pi _i^h,a_{r'})|+\ell _{x_1})$. In this case, for the pair $\{x_1,w_1\}$ which is not resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$, $\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),x_1)=\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x_1)-1<\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),y)=\text {dist}(f^2(u_{r'}^{i'},v_{r'}^{i'}),y)$. In a similar way, we can show that every vertex pair $\{x_{\mu },w_{\nu }\}$ for $\mu \in \{1,2,3,4\},\nu \in \{1,2\}$ is resolved by $\mathcal{S}'$. This completes the proof for the lemma. $\square$

Lemma 25

Every pair $\{x,y\}\in \bigcup _{i\in [n]}L_i\times \bigcup _{i\in [n]}H_i$ is resolved by $\mathcal{S}'$.

Proof

First we show that every pair $\{x,y\}\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times (P(s_{i'}^{j'},a_r)\cup P(s_{i'}^{j'},c_r))$ for $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ and $y\in P(s_{i'}^{j'},a_r)$. For a vertex $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, let $P(q_i^h,x)$ be the subpath of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from $q_i^h$ to x and $|P(q_i^h,x)|=\ell _x$. For a vertex $y\in P(s_{i'}^{j'},a_r)$, let $P(a_r,y)$ be the subpath of $P(s_{i'}^{j'},a_r)$ from $a_r$ to y and $|P(a_r,y)|=\ell _y$. Then $\text {dist}(f(\pi _i^h,a_r),x)=\text {min }(|P(\pi _i^h,a_r)|+1+\ell _x,2+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+1+\ell _x,50(n+1)+1-\ell _x)$. $\text {dist}(f(\pi _i^{3-h},a_r),x)=\text {min }(2+|P(\pi _i^h,a_r)|+1+\ell _x,|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+3+\ell _x,50(n+1)-1-\ell _x)$. $\text {dist}(f(\pi _i^h,a_r),y)=\text {dist}(f(\pi _i^{3-h},a_r),y)=2+\ell _y$. For a pair $\{x,y\}$ which is not resolved by $f(\pi _i^h,a_r)$, there are two cases. Case 1: $\text {dist}(f(\pi _i^{3-h},a_r),x)=\text {dist}(f(\pi _i^{3-h},a_r),y)=10(n+1)+1+\ell _x=2+\ell _y$. In this case, $\text {dist}(f(\pi _i^{3-h},a_r),x)=10(n+1)+3+\ell _x>2+\ell _y=\text {dist}(f(\pi _i^{3-h},a_r),y)$. Case 2: $\text {dist}(f(\pi _i^{3-h},a_r),x)=\text {dist}(f(\pi _i^{3-h},a_r),y)=50(n+1)+1-\ell _x=2+\ell _y$. In this case, $\text {dist}(f(\pi _i^{3-h},a_r),x)=50(n+1)-1-\ell _x<2+\ell _y=\text {dist}(f(\pi _i^{3-h},a_r),y)$. It follows that every pair $\{x,y\}$ is resolved by $f(\pi _i^h,a_r)$ or $f(\pi _i^{3-h},a_r)$. Similarly we can show that every pair of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times P(s_{i'}^{j'},c_r)$ is resolved by $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$.

Then we show that every pair $\{x,y\}\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times (P(s_{i'}^{j'},b_r)\setminus \{s_{i'}^{j'}\})$ for $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j,j'\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ and $y\in P(s_{i'}^{j'},b_r)\setminus \{s_{i'}^{j'}\}$. We define $\ell _x$ and $\ell _y$ in a similar way to that of $\ell _x$ and $\ell _y$ in the first paragraph. Suppose that $s_{i'}^{j'}$ resolves the pair $\{u_r^{i_r},v_r^{i_r}\}$ for some $i_r\in [n]$, i.e. $|P(a_r,u_r^{i_r})|=20(n+1)-10i_r$. Then $\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),x)=\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),x)+1=\text {min }(1+|P(a_r,u_r^{i_r})|+|P(\pi _i^h,a_r)|+1+\ell _x,1+|P(a_r,u_r^{i_r})|+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(2+30(n+1)-10i_r+\ell _x,70(n+1)-10i_r-\ell _x)$. $\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),y)=\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),y)=2+|P(b_r,v_r^{i_r})|+\ell _y=20(n+1)-5i_r+\ell _y$. Thus for a vertex pair $\{x,y\}$ which is not resolved by $f^1(u_r^{i_r},v_r^{i_r})$, $\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),x)=\text {dist}(f^1(u_r^{i_r},v_r^{i_r}),y)=\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),y)>\text {dist}(f^2(u_r^{i_r},v_r^{i_r}),x)$. It follows that every pair $\{x,y\}$ is resolved by $f^1(u_r^{i_r},v_r^{i_r})$ or $f^2(u_r^{i_r},v_r^{i_r})$. This completes the proof for the lemma. $\square$

Lemma 26

Every pair $\{x,y\}\in \bigcup _{i\in [n]}L_i\times \bigcup _{i\in [n]}S_i$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times (P(\pi _{i'}^{h'},a_r)\cup P(\pi _{i'}^{h'},c_r))$ for $i,i'\in [n],j\in [m],h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h,h'\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ and $y\in P(\pi _{i'}^{h'},a_r)$. For a vertex $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, let $P(q_i^h,x)$ be the subpath of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from $q_i^h$ to x and $|P(q_i^h,x)|=\ell _x$. For a vertex $y\in P(\pi _{i'}^{h'},a_r)$, let $P(a_r,y)$ be the subpath of $P(\pi _{i'}^{h'},a_r)$ from $a_r$ to y and $|P(a_r,y)|=\ell _y$. Then $\text {dist}(f(s_i^j,a_r),y)=2+\ell _y\le 2+10(n+1)$. $\text {dist}(f(s_i^j,a_r),x)=\text {min }(2+|P(\pi _i^h,a_r)|+1+\ell _x,2+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+3+\ell _x,50(n+1)+1-\ell _x)\ge 3+10(n+1)> \text {dist}(f(s_i^j,a_r),x)$. Thus every pair $\{x,y\}$ is resolved by $f(s_i^j,a_r)$. Similarly we can show that every pair of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times P(\pi _{i'}^{h'},c_r)$ is resolved by $f(s_i^j,c_r)$. This completes the proof for the lemma. $\square$

Lemma 27

Every pair $\{x,y\}\in \bigcup _{i\in [n]}L_i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))\times (P(u_r^{i'},a_r)\cup P(v_r^{i'},a_r)\cup P(u_r^{i'},b_r)\cup P(v_r^{i'},b_r)\cup P(u_r^{i'},c_r)\cup P(v_r^{i'},c_r))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r\in \{1,2,3\}$. Suppose that $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, $y_1\in P(u_r^{i'},a_r)$, $y_2\in P(v_r^{i'},a_r)$, $z_1\in P(u_r^{i'},b_r)$, $z_2\in P(v_r^{i'},b_r)$, $w_1\in P(u_r^{i'},c_r)$, $w_2\in P(v_r^{i'},c_r)$. For a vertex $x\in P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$, let $P(q_i^h,x)$ be the subpath of $P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))$ from $q_i^h$ to x and $|P(q_i^h,x)|=\ell _x$. For a vertex $y_1\in P(u_r^{i'},a_r)$, let $P(y_1,u_r^{i'})$ be the subpath of $P(u_r^{i'},a_r)$ from $y_1$ to $u_r^{i'}$ and let $|P(y_1,u_r^{i'})|=\ell _{y_1}$. For a vertex $y_2\in P(v_r^{i'},a_r)$, let $P(y_2,v_r^{i'})$ be the subpath of $P(v_r^{i'},a_r)$ from $y_2$ to $v_r^{i'}$ and let $|P(y_2,v_r^{i'})|=\ell _{y_2}$. For a vertex $z_1\in P(u_r^{i'},b_r)$, let $P(z_1,u_r^{i'})$ be the subpath of $P(u_r^{i'},b_r)$ from $z_1$ to $u_r^{i'}$ and let $|P(z_1,u_r^{i'})|=\ell _{z_1}$. For a vertex $z_2\in P(v_r^{i'},b_r)$, let $P(z_2,v_r^{i'})$ be the subpath of $P(v_r^{i'},b_r)$ from $z_2$ to $v_r^{i'}$ and let $|P(z_2,v_r^{i'})|=\ell _{z_2}$. For a vertex $w_1\in P(u_r^{i'},c_r)$, let $P(w_1,u_r^{i'})$ be the subpath of $P(u_r^{i'},c_r)$ from $w_1$ to $u_r^{i'}$ and let $|P(w_1,u_r^{i'})|=\ell _{w_1}$. For a vertex $w_2\in P(v_r^{i'},c_r)$, let $P(w_2,v_r^{i'})$ be the subpath of $P(v_r^{i'},c_r)$ from $w_2$ to $v_r^{i'}$ and let $|P(w_2,v_r^{i'})|=\ell _{w_2}$. For a pair $\{x,y_1\}$, $\text {dist}(f^1(u_r^{i'},v_r^{i'}),y_1)=1+\ell _{y_1}$ if $y_1\ne u_r^{i'}$ and $\text {dist}(f^1(u_r^{i'},v_r^{i'}),u_r^{i'})=2$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {min }(1+|P(a_r,u_r^{i'})|+|P(\pi _i^h,a_r)|+1+\ell _x,1+|P(a_r,u_r^{i'})|+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(2+30(n+1)-10i'+\ell _x,70(n+1)-10i'-\ell _x)>1+20(n+1)-10i'\ge \text {dist}(f^1(u_r^{i'},v_r^{i'}),y_1)$. Thus every pair $\{x,y_1\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$. Similarly, every pair $\{x,y_2\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$. For a pair $\{x,z_1\}$, $\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)=\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)-1$. $\text {dist}(f^1(u_r^{i'},v_r^{i'}),z_1)=\text {dist}(f^2(u_r^{i'},v_r^{i'}),z_1)=2+\ell _{z_1}$. Thus for a pair $\{x,z_1\}$ that is not resolved by $f^1(u_r^{i'},v_r^{i'})$, $\text {dist}(f^1(u_r^{i'},v_r^{i'}),x)=\text {dist}(f^1(u_r^{i'},v_r^{i'}),z_1)=\text {dist}(f^2(u_r^{i'},v_r^{i'}),z_1)>\text {dist}(f^2(u_r^{i'},v_r^{i'}),x)$. It follows that every pair $\{x,z_1\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$ or $f^2(u_r^{i'},v_r^{i'})$. Similarly, every pair $\{x,z_2\}$ is resolved by $f^1(u_r^{i'},v_r^{i'})$ or $f^2(u_r^{i'},v_r^{i'})$. For a pair $\{x,w_1\}$, $\text {dist}(f(\pi _i^h,c_r),w_1)=\text {dist}(f(\pi _i^{3-h},c_r),w_1)=\text {dist}(f(s_i^j,c_r),w_1)=2+|P(c_r,u_r^{i'})|-\ell _{w_1}=2+20(n+1)+10i'-\ell _{w_1}$. $\text {dist}(f(\pi _i^h,c_r),x)=\text {min }(|P(\pi _i^h,a_r)|+1+\ell _x,2+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+1+\ell _x,50(n+1)+1-\ell _x)$. $\text {dist}(f(\pi _i^{3-h},c_r),x)=\text {min }(2+|P(\pi _i^h,a_r)|+1+\ell _x,|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+3+\ell _x,50(n+1)-1-\ell _x)$. $\text {dist}(f(s_i^j,c_r),x)=\text {min }(2+|P(\pi _i^h,a_r)|+1+\ell _x,2+|P(\pi _i^{3-h},a_r)|+|P^{3-h}(i,j,p_i^h)|/2+|P(q_i^h,\text {mid}(P^{3-h}(i,j,p_i^{h})))|-\ell _x)= \text {min }(10(n+1)+3+\ell _x,50(n+1)+1-\ell _x)$. For a pair $\{x,w_1\}$ which is not resolved by $f(s_i^j,c_r)$, either $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$ resolves it. Thus every pair $\{x,w_1\}$ is resolved by $f(s_i^j,c_r)$, $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$. Similarly, we can show that every pair $\{x,w_2\}$ is resolved by $f(s_i^j,c_r)$, $f(\pi _i^h,c_r)$ or $f(\pi _i^{3-h},c_r)$. This completes the proof for the lemma. $\square$

Lemma 28

Every pair $\{x,y\}\in \bigcup _{i\in [n]}S_i\times \bigcup _{i\in [n]}H_i$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in (P(\pi _{i'}^h,a_{r'})\cup P(\pi _{i'}^h,c_{r'}))\times (P(s_i^j,a_r)\cup P(s_i^j,b_r)\cup P(s_i^j,c_r))$ for $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P(\pi _{i'}^h,a_{r'})$, $x_2\in P(\pi _{i'}^h,c_{r'})$, $y_1\in P(s_i^j,a_r)$, $y_2\in P(s_i^j,a_r)$ and $y_3\in P(s_i^j,c_r)$. For a vertex $x_1\in P(\pi _{i'}^h,a_{r'})$, let $P(\pi _{i'}^h,x_1)$ be the subpath of $P(\pi _{i'}^h,a_{r'})$ from $\pi _{i'}^h$ to $x_1$ and let $|P(\pi _{i'}^h,x_1)|=\ell _{x_1}$. For a vertex $x_2\in P(\pi _{i'}^h,c_{r'})$, let $P(\pi _{i'}^h,x_2)$ be the subpath of $P(\pi _{i'}^h,c_{r'})$ from $\pi _{i'}^h$ to $x_2$ and let $|P(\pi _{i'}^h,x_2)|=\ell _{x_2}$. For a vertex $y_1\in P(s_i^j,a_r)$, let $P(s_i^j,y_1)$ be the subpath of $P(s_i^j,a_r)$, from $s_i^j$ to $y_1$ and let $|P(s_i^j,y_1)|=\ell _{y_1}$. For a vertex $y_2\in P(s_i^j,b_r)\setminus \{s_i^j\}$, let $P(s_i^j,y_2)$ be the subpath of $P(s_i^j,b_r)$, from $s_i^j$ to $y_2$ and let $|P(s_i^j,y_2)|=\ell _{y_2}$. For a vertex $y_3\in P(s_i^j,c_r)$, let $P(s_i^j,y_3)$ be the subpath of $P(s_i^j,c_r)$, from $s_i^j$ to $y_3$ and let $|P(s_i^j,y_3)|=\ell _{y_3}$. Let $|P(s_i^j,a_r)|=20(n+1)+10\lambda$ for some $\lambda \in [n]$. For a vertex pair $\{x_1,y_1\}$, $\text {dist}(f^h(i',j,a_r),x_1)=2+\ell _{x_1}$. For the distance between $f^h(i',j,a_r)$ and $y_1$, there are two cases. Case 1: $i'=i$. Then $\text {dist}(f^h(i',j,a_r),y_1)=\text {min }(|P^h(i,j,a_r)|+\ell _{y_1}-1,2+|P(\pi _i^h,a_r)|+|P(s_i^j,a_r)|-\ell _{y_1})=\text {min }(20(n+1)+\ell _{y_1}-1,30(n+1)+10\lambda +2-\ell _{y_1})$ if $y_1\ne s_i^j$ and $\text {dist}(f^h(i',j,a_r),s_i^j)=20(n+1)+1$. Thus $\text {dist}(f^h(i',j,a_r),y_1)\ge 2+10(n+1)\ge \text {dist}(f^h(i',j,a_r),x_1)$. $f^h(i',j,a_r)$ does not resolve $\{x_1,y_1\}$ only when $x_1=a_{r'}$ and $y_1=a_r$ with $r\ne r'$. The pair $\{a_{r'},a_r\}$ is resolved by $f(\pi _{i'}^h,a_{r'})$. Thus in this case, every pair $\{x_1,y_1\}$ is resolved by $f^h(i',j,a_r)$ or $f(\pi _{i'}^h,a_{r'})$. Case 2: $i'\ne i$. Then $\text {dist}(f^h(i',j,a_r),s_i^j)=\text {min}_{d\in \{1,2,3\}}(2+|P(\pi _{i'}^h,c_{d})|+|P(s_i^j,c_{d})|)$. $\text {dist}(f^h(i',j,a_r),y_1)=\text {min }(\text {dist}(f^h(i',j,a_r),s_i^j)+\ell _{y_1},2+|P(\pi _{i'}^h,a_r)|+|P(s_i^j,a_r)|-\ell _{y_1})\ge 2+10(n+1)\ge \text {dist}(f^h(i',j,a_r),x_1)$. $f^h(i',j,a_r)$ does not resolve $\{x_1,y_1\}$ only when $x_1=a_{r'}$ and $y_1=a_r$ with $r\ne r'$.. The pair $\{a_{r'},a_r\}$ is resolved by $f(\pi _{i'}^h,a_{r'})$. It follows that every pair $\{x_1,y_1\}$ is resolved by $f^h(i',j,a_r)$ or $f(\pi _{i'}^h,a_{r'})$. In a similar way, we can show that every pair $\{x_2,y_1\}$, $\{x_1,y_3\}$ and $\{x_2,y_3\}$ are resolved by $\mathcal{S}'$. For a vertex pair $\{x_1,y_2\}$, $\text {dist}(f^h(i',j,b_r),x_1)=2+\ell _{x_1}$. For the distance between $f^h(i',j,b_r)$ and $y_2$, there are two cases. Case 1: $i'=i$. Then $\text {dist}(f^h(i',j,b_r),y_2)=\text {min }(|P^h(i',j,b_r)|+\ell _{y_2}-1,2+|P(\pi _i^h,a_r)|+|P(a_r,v_r^n)|+|P(b_r,v_r^n)|+|P(s_i^j,b_r)|-\ell _{y_2})\ge 20(n+1)>\text {dist}(f^h(i',j,b_r),x_1)$. Case 2: $i'\ne i$. Then $\text {dist}(f^h(i',j,b_r),s_i^j)=\text {min}_{d\in \{1,2,3\}}(2+|P(\pi _{i'}^h,c_{d})|+|P(s_i^j,c_{d})|)$. $\text {dist}(f^h(i',j,b_r),y_2)=\text {min }(\text {dist}(f^h(i',j,b_r),s_i^j)+\ell _{y_2},2+|P(\pi _{i'}^h,a_r)|+|P(a_r,v_r^n)|+|P(b_r,v_r^n)|+|P(s_i^j,b_r)|-\ell _{y_2})>20(n+1)>\text {dist}(f^h(i',j,b_r),x_1)$. Thus in both cases, every pair $\{x_1,y_2\}$ is resolved by $f^h(i',j,b_r)$. In a similar way, we can show that every pair $\{x_2,y_2\}$ is resolved by $f^h(i',j,b_r)$. This completes the proof for the lemma. $\square$

Lemma 29

Every pair $\{x,y\}\in \bigcup _{i\in [n]}S_i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

We show that every pair $\{x,y\}\in (P(\pi _i^h,a_r)\cup P(\pi _i^h,c_r))\times (P(u_{r'}^{i'},a_{r'})\cup P(v_{r'}^{i'},a_{r'})\cup P(u_{r'}^{i'},b_{r'})\cup P(v_{r'}^{i'},b_{r'})\cup P(u_{r'}^{i'},c_{r'})\cup P(v_{r'}^{i'},c_{r'}))$ for $i,i'\in [n],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n],j\in [m],h\in \{1,2\}$ and $r,r'\in \{1,2,3\}$. Suppose that $x_1\in P(\pi _i^h,a_r)$, $x_2\in P(\pi _i^h,c_r)$, $y_1\in P(u_{r'}^{i'},a_{r'})$, $y_2\in P(v_{r'}^{i'},a_{r'})$, $z_1\in P(u_{r'}^{i'},b_{r'})$, $z_2\in P(v_{r'}^{i'},b_{r'})$, $w_1\in P(u_{r'}^{i'},c_{r'})$, $w_2\in P(v_{r'}^{i'},c_{r'})$. For a vertex $x_1\in P(\pi _i^h,a_r)$, let $P(\pi _i^h,x_1)$ be the subpath of $P(\pi _i^h,a_r)$ from $\pi _i^h$ to $x_1$ and let $|P(\pi _i^h,x_1)|=\ell _{x_1}$. For a vertex $x_2\in P(\pi _i^h,c_r)$, let $P(\pi _i^h,x_2)$ be the subpath of $P(\pi _i^h,c_r)$ from $\pi _i^h$ to $x_2$ and let $|P(\pi _i^h,x_2)|=\ell _{x_2}$. Then $\text {dist}(f^h(i,j,a_r),x_1)=2+\ell _{x_1}\le 2+10(n+1)$ and $\text {dist}(f^h(i,j,a_r),x_2)=2+\ell _{x_2}\le 2+10(n+1)$. $\text {dist}(f^h(i,j,a_r),a_{r'})=\text {dist}(f^h(i,j,a_r),c_{r'})=2+10(n+1)$. $\text {dist}(f^h(i,j,a_r),b_{r'})=2+|P(\pi _i^h,a_{r'})|+|P(a_{r'},v_{r'}^n)|+|P(b_{r'},v_{r'}^n)|>2+10(n+1)$. We see that any shortest path from $f^h(i,j,a_r)$ to a vertex of $\{y_1,y_2,z_1,z_2,w_1,w_2\}$ goes through $a_{r'},b_{r'}$ or $c_{r'}$. Thus the distance from $f^h(i,j,a_r)$ to any vertex of $\{y_1,y_2,z_1,z_2,w_1,w_2\}$ is at least $2+10(n+1)$ and the equality holds only when $y_1=y_2=a_{r'}$ or $w_1=w_2=c_{r'}$. Obviously $f(\pi _i^h,a_r)$ resolves the pairs $\{a_r,a_{r'}\}$ and $\{a_r,c_{r'}\}$ and $f(\pi _i^h,c_r)$ resolves the pairs $\{c_r,a_{r'}\}$ and $\{c_r,c_{r'}\}$ with $r\ne r'$. As a result, every vertex pair of $\bigcup _{i\in [n]}S_i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $f^h(i,j,a_r)$, $f(\pi _i^h,a_r)$ or $f(\pi _i^h,c_r)$. This completes the proof for the lemma. $\square$

Lemma 30

Every pair $\{x,y\}\in \bigcup _{i\in [n]}H_i\times \bigcup _{r\in \{1,2,3\}}R_r$ is resolved by $\mathcal{S}'$.

Proof

First we show that every pair $\{x,y\}\in P(s_i^j,a_r)\times (P(u_{r'}^{i'},a_{r'})\cup P(v_{r'}^{i'},a_{r'})\cup P(u_{r'}^{i'},b_{r'})\cup P(v_{r'}^{i'},b_{r'})\cup P(u_{r'}^{i'},c_{r'})\cup P(v_{r'}^{i'},c_{r'}))$ for $i,i'\in [n], j\in [m]$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n], h\in \{1,2\}, j\in [m]$ and $r,r'\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,a_r)$, $y_1\in P(u_{r'}^{i'},a_{r'})$, $y_2\in P(v_{r'}^{i'},a_{r'})$, $z_1\in P(u_{r'}^{i'},b_{r'})$, $z_2\in P(v_{r'}^{i'},b_{r'})$, $w_1\in P(u_{r'}^{i'},c_{r'})$, $w_2\in P(v_{r'}^{i'},c_{r'})$. For a vertex $x\in P(s_i^j,a_r)$, let $P(x,a_r)$ be the subpath of $P(s_i^j,a_r)$ from $a_r$ to x and let $|P(x,a_r)|=\ell _x$. For a vertex $y_1\in P(u_{r'}^{i'},a_{r'})$, let $P(y_1,u_{r'}^{i'})$ be the subpath of $P(u_{r'}^{i'},a_{r'})$ from $y_1$ to $u_{r'}^{i'}$ and let $|P(y_1,u_{r'}^{i'})|=\ell _{y_1}$. For a vertex $y_2\in P(v_{r'}^{i'},a_{r'})$, let $P(y_2,v_{r'}^{i'})$ be the subpath of $P(v_{r'}^{i'},a_{r'})$ from $y_2$ to $v_{r'}^{i'}$ and let $|P(y_2,v_{r'}^{i'})|=\ell _{y_2}$. For a vertex $z_1\in P(u_{r'}^{i'},b_{r'})$, let $P(z_1,u_{r'}^{i'})$ be the subpath of $P(u_{r'}^{i'},b_{r'})$ from $z_1$ to $u_{r'}^{i'}$ and let $|P(z_1,u_{r'}^{i'})|=\ell _{z_1}$. For a vertex $z_2\in P(v_{r'}^{i'},b_{r'})$, let $P(z_2,v_{r'}^{i'})$ be the subpath of $P(v_{r'}^{i'},b_{r'})$ from $z_2$ to $v_{r'}^{i'}$ and let $|P(z_2,v_{r'}^{i'})|=\ell _{z_2}$. For a vertex $w_1\in P(u_{r'}^{i'},c_{r'})$, let $P(w_1,u_{r'}^{i'})$ be the subpath of $P(u_{r'}^{i'},c_{r'})$ from $w_1$ to $u_{r'}^{i'}$ and let $|P(w_1,u_{r'}^{i'})|=\ell _{w_1}$. For a vertex $w_2\in P(v_{r'}^{i'},c_{r'})$, let $P(w_2,v_{r'}^{i'})$ be the subpath of $P(v_{r'}^{i'},c_{r'})$ from $w_2$ to $v_{r'}^{i'}$ and let $|P(w_2,v_{r'}^{i'})|=\ell _{w_2}$. Then $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(\pi _i^h,a_r),x)-2=\ell _x$ if $x\ne a_r$ and $\text {dist}(f(s_i^j,a_r),a_r)=\text {dist}(f(\pi _i^h,a_r),a_r)=2$. For a vertex pair $\{x,y_1\}$, there are two cases. Case 1: $r'=r$. $\text {dist}(f(s_i^j,a_r),y_1)=\text {dist}(f(\pi _i^h,a_r),y_1)=2+|P(u_{r'}^{i'},a_{r'})|-\ell _{y_1}$. For a vertex pair $\{x,y_1\}$ that is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),y_1)=\text {dist}(f(\pi _i^h,a_r),y_1)<\text {dist}(f(\pi _i^h,a_r),x)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Case 2: $r'\ne r$. $\text {dist}(f(s_i^j,a_r),y_1)=\text {dist}(f(\pi _i^h,a_r),y_1)+2=2+|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|-\ell _{y_1}$. For a vertex pair $\{x,y_1\}$ that is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(\pi _i^h,a_r),x)>\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),y_1)>\text {dist}(f(\pi _i^h,a_r),y_1)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Similarly, every pair $\{x,y_2\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. For a vertex pair $\{x,z_1\}$, there are two cases. Case 1: $r'=r$. $\text {dist}(f(s_i^j,a_r),z_1)=\text {dist}(f(\pi _i^h,a_r),z_1)=\text {min }(2+|P(u_{r'}^{i'},a_{r'})|+\ell _{z_1},2+|P(u_{r'}^{n},a_{r'})|+|P(u_{r'}^{n},b_{r'})|+|P(u_{r'}^{i'},b_{r'})|-\ell _{z_1})$. For a vertex pair $\{x,z_1\}$ that is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),z_1)=\text {dist}(f(\pi _i^h,a_r),z_1)<\text {dist}(f(\pi _i^h,a_r),x)$. Thus in this case, every pair $\{x,z_1\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Case 2: $r'\ne r$. $\text {dist}(f(\pi _i^h,a_r),b_{r'})=\text {min}_{\alpha \in [m]}(2+|P(s_i^{\alpha },a_r)|+|P(s_i^{\alpha },b_{r'})|)$. Then $\text {dist}(f(\pi _i^h,a_r),z_1)=\text {min }(|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{z_1},\text {dist}(f(\pi _i^h,a_r),b_{r'})+|P(u_{r'}^{i'},b_{r'})|-\ell _{z_1})>30(n+1)>\text {dist}(f(\pi _i^h,a_r),x)$. Thus in this case, every pair $\{x,z_1\}$ is resolved by $f(\pi _i^h,a_r)$. Similarly, every pair $\{x,z_2\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. For a vertex pair $\{x,w_1\}$, there are two cases. Case 1: $r'=r$. $\text {dist}(f(s_i^j,a_r),w_1)=\text {min }(2+|P(u_r^{i'},a_{r'})|-2+\ell _{w_1},2+|P(\pi _i^h,a_r)|+|P(\pi _i^h,c_r)|+|P(u_r^{i'},c_r)|-\ell _{w_1})$ if $\ell _{w_1}\ge 2$. $\text {dist}(f(s_i^j,a_r),w_1)=2+|P(u_r^{i'},a_{r'})|+\ell _{w_1}$ if $\ell _{w_1}<2$. $\text {dist}(f(\pi _i^h,a_r),w_1)=\text {min }(2+|P(u_r^{i'},a_{r'})|-2+\ell _{w_1},|P(\pi _i^h,a_r)|+|P(\pi _i^h,c_r)|+|P(u_r^{i'},c_r)|-\ell _{w_1})$ if $\ell _{w_1}\ge 2$. $\text {dist}(f(\pi _i^h,a_r),w_1)=2+|P(u_r^{i'},a_{r'})|+\ell _{w_1}$ if $\ell _{w_1}<2$. It follows that $\text {dist}(f(s_i^j,a_r),w_1)\ge \text {dist}(f(\pi _i^h,a_r),w_1)$. For a pair $\{x,w_1\}$ that is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(\pi _i^h,a_r),x)>\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),w_1)\ge \text {dist}(f(\pi _i^h,a_r),w_1)$. Thus in this case, every pair $\{x,w_1\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Case 2: $r'\ne r$. $\text {dist}(f(s_i^j,a_r),w_1)=\text {min }(2+|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|-2+\ell _{w_1},2+|P(\pi _i^h,a_r)|+|P(\pi _i^h,c_{r'})|+|P(u_{r'}^{i'},c_{r'})|-\ell _{w_1})$ if $\ell _{w_1}\ge 2$. $\text {dist}(f(s_i^j,a_r),w_1)=2+|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{w_1}$ if $\ell _{w_1}<2$. $\text {dist}(f(\pi _i^h,a_r),w_1)=\text {min }(|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{w_1}-2,|P(\pi _i^h,a_r)|+|P(\pi _i^h,c_{r'})|+|P(u_{r'}^{i'},c_{r'})|-\ell _{w_1})$ if $\ell _{w_1}\ge 2$. $\text {dist}(f(\pi _i^h,a_r),w_1)=|P(\pi _i^h,a_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{w_1}$ if $\ell _{w_1}<2$. It follows that $\text {dist}(f(s_i^j,a_r),w_1)>\text {dist}(f(\pi _i^h,a_r),w_1)$. For a pair $\{x,w_1\}$ that is not resolved by $f(s_i^j,a_r)$, $\text {dist}(f(\pi _i^h,a_r),x)>\text {dist}(f(s_i^j,a_r),x)=\text {dist}(f(s_i^j,a_r),w_1)>\text {dist}(f(\pi _i^h,a_r),w_1)$. Thus in this case, every pair $\{x,w_1\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$. Similarly, every pair $\{x,w_2\}$ is resolved by $f(s_i^j,a_r)$ or $f(\pi _i^h,a_r)$.

Then we show that every pair $\{x,y\}\in P(s_i^j,c_r)\times (P(u_{r'}^{i'},a_{r'})\cup P(v_{r'}^{i'},a_{r'})\cup P(u_{r'}^{i'},b_{r'})\cup P(v_{r'}^{i'},b_{r'})\cup P(u_{r'}^{i'},c_{r'})\cup P(v_{r'}^{i'},c_{r'}))$ for $i,i'\in [n], j\in [m]$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n], h\in \{1,2\}, j\in [m]$ and $r,r'\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,c_r)$, $y_1\in P(u_{r'}^{i'},a_{r'})$, $y_2\in P(v_{r'}^{i'},a_{r'})$, $z_1\in P(u_{r'}^{i'},b_{r'})$, $z_2\in P(v_{r'}^{i'},b_{r'})$, $w_1\in P(u_{r'}^{i'},c_{r'})$, $w_2\in P(v_{r'}^{i'},c_{r'})$. We define $\ell _x,\ell _{y_1},\ell _{y_2},\ell _{z_1},\ell _{z_2},\ell _{w_1}$ and $\ell _{w_2}$ in a similar way to that of $\ell _x,\ell _{y_1}$ in the first paragraph. Then $\text {dist}(f(s_i^j,c_r),x)=\text {dist}(f(\pi _i^h,c_r),x)-2=\ell _x$ if $x\ne c_r$ and $\text {dist}(f(s_i^j,c_r),c_r)=\text {dist}(f(\pi _i^h,c_r),c_r)=2$. For a pair $\{x,y_1\}$, there are two cases. Case 1: $r'=r$. $\text {dist}(f(s_i^j,c_r),y_1)=\text {min }(2+|P(u_r^{i'},c_{r'})|-2+\ell _{y_1},2+|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_r)|+|P(u_r^{i'},a_r)|-\ell _{y_1})$ if $\ell _{y_1}\ge 2$. $\text {dist}(f(s_i^j,c_r),y_1)=2+|P(u_r^{i'},c_{r'})|+\ell _{y_1}$ if $\ell _{y_1}<2$. $\text {dist}(f(\pi _i^h,c_r),y_1)=\text {min }(2+|P(u_r^{i'},c_{r'})|-2+\ell _{y_1},|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_r)|+|P(u_r^{i'},a_r)|-\ell _{y_1})$ if $\ell _{y_1}\ge 2$. $\text {dist}(f(\pi _i^h,c_r),y_1)=2+|P(u_r^{i'},c_{r'})|+\ell _{y_1}$ if $\ell _{y_1}<2$. It follows that $\text {dist}(f(s_i^j,c_r),y_1)\ge \text {dist}(f(\pi _i^h,c_r),y_1)$. For a pair $\{x,y_1\}$ that is not resolved by $f(s_i^j,c_r)$, $\text {dist}(f(\pi _i^h,c_r),x)>\text {dist}(f(s_i^j,c_r),x)=\text {dist}(f(s_i^j,c_r),y_1)\ge \text {dist}(f(\pi _i^h,c_r),y_1)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$. Case 2: $r'\ne r$. $\text {dist}(f(s_i^j,c_r),y_1)=\text {dist}(f(\pi _i^h,c_r),y_1)+2=2+|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|-\ell _{y_1}$. It follows that $\text {dist}(f(s_i^j,c_r),y_1)>\text {dist}(f(\pi _i^h,c_r),y_1)$. For a pair $\{x,y_1\}$ that is not resolved by $f(s_i^j,c_r)$, $\text {dist}(f(\pi _i^h,c_r),x)>\text {dist}(f(s_i^j,c_r),x)=\text {dist}(f(s_i^j,c_r),y_1)>\text {dist}(f(\pi _i^h,c_r),y_1)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$. Similarly, every pair $\{x,y_2\}$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$. For a pair $\{x,z_1\}$, there are two cases. Case 1: $r'=r$. Let $s_i^{j^*}$ be a vertex which resolves the pair $\{u_r^n,v_r^n\}$. Then $|P(s_i^{j^*},c_r)|+|P(s_i^{j^*},b_r)|=40(n+1)-5n+1$. $\text {dist}(f(\pi _i^h,c_r),b_r)=2+|P(s_i^{j^*},c_r)|+|P(s_i^{j^*},b_r)|=40(n+1)-5n+3$. $\text {dist}(f(\pi _i^h,c_r),z_1)=\text {min }(2+|P(u_r^{i'},c_{r'})|+\ell _{z_1},\text {dist}(f(\pi _i^h,c_r),b_r)+|P(u_r^{i'},b_r)|-\ell _{z_1})>20(n+1)>\text {dist}(f(\pi _i^h,c_r),x)$. Thus in this case, every pair $\{x,z_1\}$ is resolved by $f(\pi _i^h,c_r)$. Case 2: $r'\ne r$. $\text {dist}(f(\pi _i^h,c_r),b_{r'})=\text {min}_{\alpha \in [m]}(2+|P(s_i^{\alpha },c_r)|+|P(s_i^{\alpha },b_{r'})|)$. Then $\text {dist}(f(\pi _i^h,c_r),z_1)=\text {min }(|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{z_1},\text {dist}(f(\pi _i^h,c_r),b_{r'})+|P(u_{r'}^{i'},b_{r'})|-\ell _{z_1})>20(n+1)>\text {dist}(f(\pi _i^h,c_r),x)$. Thus in this case, every pair $\{x,z_1\}$ is resolved by $f(\pi _i^h,c_r)$. Similarly, every pair $\{x,z_2\}$ is resolved by $f(\pi _i^h,c_r)$. For a pair $\{x,w_1\}$, there are two cases. Case 1: $r'=r$. $\text {dist}(f(s_i^j,c_r),w_1)=\text {dist}(f(\pi _i^h,c_r),w_1)=2+|P(u_{r'}^{i'},c_{r'})|-\ell _{w_1}$. For a vertex pair $\{x,w_1\}$ that is not resolved by $f(s_i^j,c_r)$, $\text {dist}(f(s_i^j,c_r),x)=\text {dist}(f(s_i^j,c_r),w_1)=\text {dist}(f(\pi _i^h,c_r),w_1)<\text {dist}(f(\pi _i^h,c_r),x)$. Thus in this case, every pair $\{x,w_1\}$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$. Case 2: $r'\ne r$. $\text {dist}(f(\pi _i^h,c_r),w_1)=\text {min }(|P(\pi _i^h,c_r)|+|P(\pi _i^h,c_{r'})|+|P(u_{r'}^{i'},c_{r'})|-\ell _{w_1},|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{w_1}-2)$ if $\ell _{w_1}\ge 2$. $\text {dist}(f(\pi _i^h,c_r),w_1)=|P(\pi _i^h,c_r)|+|P(\pi _i^h,a_{r'})|+|P(u_{r'}^{i'},a_{r'})|+\ell _{w_1}$ if $\ell _{w_1}<2$. Thus $\text {dist}(f(\pi _i^h,c_r),w_1)\ge 20(n+1)>\text {dist}(f(\pi _i^h,c_r),x)$. Similarly, every pair $\{x,w_2\}$ is resolved by $f(s_i^j,c_r)$ or $f(\pi _i^h,c_r)$.

Finally we show that every pair $\{x,y\}\in P(s_i^j,b_r)\times (P(u_{r'}^{i'},a_{r'})\cup P(v_{r'}^{i'},a_{r'})\cup P(u_{r'}^{i'},b_{r'})\cup P(v_{r'}^{i'},b_{r'})\cup P(u_{r'}^{i'},c_{r'})\cup P(v_{r'}^{i'},c_{r'}))$ for $i,i'\in [n], j\in [m]$ and $r,r'\in \{1,2,3\}$ is resolved by $\mathcal{S}'$. We fix arbitrary integers $i,i'\in [n], h\in \{1,2\},j\in [m]$ and $r,r'\in \{1,2,3\}$. Suppose that $x\in P(s_i^j,b_r)$, $y_1\in P(u_{r'}^{i'},a_{r'})$, $y_2\in P(v_{r'}^{i'},a_{r'})$, $z_1\in P(u_{r'}^{i'},b_{r'})$, $z_2\in P(v_{r'}^{i'},b_{r'})$, $w_1\in P(u_{r'}^{i'},c_{r'})$, $w_2\in P(v_{r'}^{i'},c_{r'})$. We define $\ell _x,\ell _{y_1},\ell _{y_2},\ell _{z_1},\ell _{z_2},\ell _{w_1}$ and $\ell _{w_2}$ in a similar way to that of $\ell _x,\ell _{y_1}$ in the first paragraph. For a pair $\{x,y_1\}$, there are two cases. Case 1: $r=r'$. $\text {dist}(f(\pi _i^h,a_r),x)=\text {min }(2+|P(s_i^j,a_r)|+|P(s_i^j,b_r)|-\ell _x,2+|P(a_r,u_r^n)|+|P(b_r,u_r^n)|+\ell _x)>20(n+1)$. $\text {dist}(f(\pi _i^h,a_r),y_1)=|P(a_r,u_r^{i'})|-\ell _{y_1}<20(n+1)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f(\pi _i^h,a_r)$. Similarly, every pair $\{x,y_2\}$ is resolved by $f(\pi _i^h,a_r)$. Case 2: $r\ne r'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),y_1)=1+\ell _{y_1}$ if $y_1\ne u_{r'}^{i'}$ and $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),u_{r'}^{i'})=2$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x)=\text {min }(\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),s_i^j)+|P(s_i^j,b_r)|-\ell _{x},\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),b_r)+\ell _{x})>20(n+1)>\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),y_1)$. Thus in this case, every pair $\{x,y_1\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. Similarly, every pair $\{x,y_2\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. For a pair $\{x,z_1\}$, there are two cases. Suppose that $P(s_i^j,b_r)=20(n+1)+5\lambda +1$ for some $\lambda \in [n]$. Case 1: $r=r'$. $\text {dist}(f^{mid}(i,j,h),x)=|P^h(i,j,p_i^{3-h})|/2+2+|P(s_i^j,b_r)|-\ell _x=30(n+1)+5\lambda +3-\ell _x$. $\text {dist}(f^{mid}(i,j,h),z_1)=\text {min }(2+|P^h(i,j,p_i^{3-h})|/2+|P(s_i^j,b_r)|+|P(b_r,u_r^{i'})|-\ell _{z_1},1+|P^h(i,j,p_i^{3-h})|/2+|P(\pi _i^h,a_r)|+|P(a_r,u_r^{i'})|+\ell _{z_1})=\text {min }(50(n+1)+5\lambda +2-5i'-\ell _{z_1},40(n+1)+1-10i'+\ell _{z_1})$. $\text {dist}(f^{ecc}(i,j,h,r),x)=|P^h(i,j,a_r)|/2+1+|P(s_i^j,b_r)|-\ell _x=\text {dist}(f^{mid}(i,j,h),x)-1$. $\text {dist}(f^{ecc}(i,j,h,r),z_1)=\text {min }(1+|P^h(i,j,a_r)|/2+|P(s_i^j,b_r)|+|P(b_r,u_r^{i'})|-\ell _{z_1},2+|P^h(i,j,a_r)|/2+|P(\pi _i^h,a_r)|+|P(a_r,u_r^{i'})|+\ell _{z_1})=\text {min }(50(n+1)+5\lambda +1-5i'-\ell _{z_1},40(n+1)+2-10i'+\ell _{z_1})$. For a vertex pair $\{x,z_1\}$ that is not resolved by $f^{mid}(i,j,h)$, $\text {dist}(f^{mid}(i,j,h),x)=\text {dist}(f^{mid}(i,j,h),z_1)=1+|P^h(i,j,p_i^{3-h})|/2+|P(\pi _i^h,a_r)|+|P(a_r,u_r^{i'})|+\ell _{z_1}>\text {dist}(f^{ecc}(i,j,h,r),x)$. If $\text {dist}(f^{ecc}(i,j,h,r),z_1)=1+|P^h(i,j,a_r)|/2+|P(s_i^j,b_r)|+|P(b_r,u_r^{i'})|-\ell _{z_1}$, then obviously $f^{ecc}(i,j,h,r)$ resolves this pair. Otherwise, $\text {dist}(f^{ecc}(i,j,h,r),z_1)=40(n+1)+2-10i'+\ell _{z_1}>\text {dist}(f^{mid}(i,j,h),z_1)>\text {dist}(f^{ecc}(i,j,h,r),x)$. It follows that every pair $\{x,z_1\}$ is resolved by $f^{mid}(i,j,h)$ or $f^{ecc}(i,j,h,r)$. Similarly, every pair $\{x,z_2\}$ is resolved by $f^{mid}(i,j,h)$ or $f^{ecc}(i,j,h,r)$. Case 2: $r\ne r'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),z_1)=2+\ell _{z_1}<20(n+1)$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x)=\text {min }(\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),s_i^j)+|P(s_i^j,b_r)|-\ell _{x},\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),b_r)+\ell _{x})>20(n+1)>\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),z_1)$. Thus in this case, every pair $\{x,z_1\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. Similarly, every pair $\{x,z_2\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. For a pair $\{x,w_1\}$, there are two cases. Case 1: $r=r'$. $\text {dist}(f(\pi _i^h,c_r),b_r)=\text {min}_{\alpha \in [m]}(2+|P(s_i^{\alpha },c_r)|+|P(s_i^{\alpha },b_r)|)=3+40(n+1)-5n>30(n+1)$. $\text {dist}(f(\pi _i^h,c_r),x)=\text {min }(2+|P(s_i^j,c_r)|+|P(s_i^j,b_r)|-\ell _x,\text {dist}(f(\pi _i^h,c_r),b_r)+\ell _x)$. $\text {dist}(f(s_i^j,c_r),x)=\text {min }(|P(s_i^j,c_r)|+|P(s_i^j,b_r)|-\ell _x,\text {dist}(f(\pi _i^h,c_r),b_r)+\ell _x)$. $\text {dist}(f(\pi _i^h,c_r),w_1)=\text {dist}(f(s_i^j,c_r),w_1)=2+|P(c_r,u_{r'}^{i'})|-\ell _{w_1}=2+20(n+1)+10i'-\ell _{w_1}<30(n+1)$. For a pair $\{x,w_1\}$ that is not resolved by $f(\pi _i^h,c_r)$, $\text {dist}(f(\pi _i^h,c_r),x)=\text {dist}(f(\pi _i^h,c_r),w_1)=2+|P(s_i^j,c_r)|+|P(s_i^j,b_r)|-\ell _x=\text {dist}(f(s_i^j,c_r),w_1)>\text {dist}(f(s_i^j,c_r),x)=|P(s_i^j,c_r)|+|P(s_i^j,b_r)|-\ell _x$. Thus in this case, every pair $\{x,w_1\}$ is resolved by $f(\pi _i^h,c_r)$ or $f(s_i^j,c_r)$. Case 2: $r\ne r'$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),w_1)=1+\ell _{w_1}$ if $w_1\ne u_{r'}^{i'}$ and $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),u_{r'}^{i'})=2$. $\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),x)=\text {min }(\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),s_i^j)+|P(s_i^j,b_r)|-\ell _{x},\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),b_r)+\ell _{x})>30(n+1)>\text {dist}(f^1(u_{r'}^{i'},v_{r'}^{i'}),w_1)$. Thus in this case, every pair $\{x,w_1\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. Similarly, every pair $\{x,w_2\}$ is resolved by $f^1(u_{r'}^{i'},v_{r'}^{i'})$. This completes the proof for the lemma. $\square$

With Lemmas 9 - 30, we show that every pair of distinct vertices of $G'$ is resolved by some vertex of $\mathcal{S}'$. It follows that Lemma 8 is true and this proves the completeness of the reduction.

Finally, with Lemmas 2, 6, 8 and 7 in hand, we can prove the correctness of Theorem 1.

6 Conclusion

In this paper, we show that metric dimension is NP-hard on graphs of treewidth at most 24. One of the key points in bounding the treewidth of $G'$ is to maintain a vertex separation of constant size. In the first step of our construction, we need 9 vertices to be the vertex separation and convey the choice of the vertices in each color class $X_i$ ($i\in [n]$). It seems hard to show NP-hardness of this problem on graphs of treewidth bounded by a constant $c<9$ using the techniques in this paper, so we mention this open problem again: is metric dimension polynomial-time solvable on graphs of treewidth 2 or series-parallel graphs [1]? Another direction is about the parameterized complexity of metric dimension. We ask the following two questions. Is metric dimension FPT parameterized by the size of the resolving set on constant treewidth graph? Is metric dimension FPT parameterized by both the size of the resolving set and the treewidth of the input graph?