Proof. Assume that for all \(y \in A\), \(d(u,y) = d_u\) and for all \(y \in B\), \(d(v,y) = d_v\) for some integers \(d_u\), \(d_v\) and let \(x \in X\). We distinguish the following two cases. See Figure 2 for an illustration.

1. \(A \cap B\neq\emptyset\). Let \(y\) be some vertex in \(A\cap B\). First, observe that \(d(u,v) \leq d(u,y)+d(v,y) = d_u + d_v\) and \(d(u,v) \geq d_u+d_v\) as any shorter path would contradict the definition of \(A\) and \(B\). Thus \(d(u,v) = d_u+d_v\). If \(x \in A \cap B\), then \(d(u,x) + d(x,v) = d_u + d_v\), and hence, \(x \in I(u,v)\). Conversely, if \(x \notin A \cap B\), then observe that \(d(u,x) + d(x,v) \geq d_u + d_v +1\) since every \(u\) to \(v\) path contains an edge entirely contained in \(G[X]\), and hence, \(x \notin I(u,v)\).

2. \(A \cap B = \emptyset\). First, observe that \(d(u,v) \geq d_u + d_v + 1\), as any shorter path would imply the existence of a vertex \(y \in X\) such that \(d(u,y) + d(y,v) \leq d_u + d_v\), which would contradict \(A \cap B = \emptyset\). Since there is some vertex \(y\in A\), \(d(u,v) \leq d_u + d_v + 1\) as \(d(u,y) + d(y,v) \leq d_u + d_v +1\). Hence, \(d(u,v) = d_u + d_v + 1\). Now, if \(x\in A \cup B\), then \(d(u,x) + d(x,v) = d_u + d_v +1\), and hence \(x \in I(u,v)\). Conversely, if \(x \notin A \cup B\), then \(d(u,x) + d(x,v) = d_u + d_v +2\), and hence \(x \notin I(u,v)\).

This completes the proof. ◻

Proof. We construct \(\tau\) from \(D\) as follows. Define \(\tau^{bag}= D\cap \beta(v)\). For each vertex \(u\in D\cap V(G_{\leq v})\) we find the set \(Z_u\subseteq \beta(v)\) such that \(u\) is close to \(Z_u\) with respect to \(\beta(v)\) and put \(\tau^{int}[Z_u]=1\). For each \(u\in D\cap V(G_{>v})\) we find the set \(Z_u\subseteq \beta(v)\) such that \(u\) is close to \(Z_u\) with respect to \(\beta(v)\) and put \(\tau^{ext}[Z_u]=1\). Similarly, let us construct \(H^{\tau}_v\), and let \(X= S^{\tau}_v \cup (D\cap G_{\leq v})\). Now, for each vertex \(w\in \beta(v)\setminus D\), if \(w\in I(w_1,w_2)\) such that \(w_1,w_2\in X\) and \(w_1\in X\setminus S^{\tau}_v\), then we put \(w\) in \(\tau^{cov}\). Finally, we put \(\tau^{uncov}=\beta(v) \setminus (\tau^{bag}\cup \tau^{cov})\). Observe that \(D \cap V(G_{\leq v})\) is a certificate of \((v,\tau)\) and \(\tau\) is a type associated with \(v\). ◻

Proof. The proof of (a) follows from the fact that for a clique cutset \(X\) and a vertex \(u\in X\), \(u\) is close to \(\left\{u\right\}\) with respect to \(X\). The proof of (b) follows from the fact that there can be no vertex close to \(\emptyset\) with respect to \(\beta(v)\). The proof of (c) follows directly from Lemma 1. ◻

Proof. Let \(\beta(v)=\beta(u) \cup \left\{x\right\}\). Define \(\tau^{bag}_1 = D \cap \beta(u)\), and \(\tau^{int}_1[A] = 1\) if and only if there exists \(y \in D \setminus \left\{x\right\}\) such that \(y\) is close to \(A\) with respect to \(\beta(u)\). Finally, define \(\tau^{cov}_1\) and \(\tau^{uncov}_1\) according to Definitions 5[it:intro-bnew] and 5[it:intro-bnew1], and define \(\tau^{ext}_1\) according to Definitions 5[it:intro-c] and 5[it:intro-d]. To complete our proof, we will establish that the set \(D'=D\setminus \left\{x\right\}\) satisfies all of the conditions in Definition 4 for \((u,\tau_1)\) and the pair \((\tau,\tau_1)\) satisfies all conditions in Definition 5. Observe that all of the conditions are trivially satisfied if \(\beta(u) =\emptyset\), thus we assume that \(\beta(u) \neq \emptyset\) for the rest of the proof.

To begin with, we establish that \(\tau_1\) is a type associated with \(u\) satisfying all of the conditions in Definition 4. Since \(\tau\) is a type associated with \(v\) and \(D\) is a (minimal) certificate, we have that there exists a set of vertices \(X\subseteq V(H^{\tau}_v)\) such that \(X=D \cup S^{\tau}_v\) and (i) \(S^{\tau}_v \subseteq X\) and \(\tau^{bag}=X\cap \beta(v)\), (ii) for each vertex \(w\in (V(G_{\leq v})\setminus \beta(v)) \cup \tau^{cov}\), \(\exists w_1,w_2\in X\) such that \(w\in I(w_1,w_2)\) and \(w_1\in X\setminus S^\tau_v\), and (iii) for each \(A\subseteq \beta(v)\), we have \(\tau^{int}[A]=1\) if and only if \(X\cap V(G_{\leq v})\) contains a vertex which is close to \(A\) with respect to \(\beta(v)\). Now, let \(X'= (X\cap V(G_{\leq u}) \cup S^{\tau_1}_u = D'\cup S^{\tau_1}_u\) . By definition of \(\tau^{bag}_1\) and \(X'\), we have that \(\tau^{bag}_1 = D\cap \beta(u) = (D' \cup \left\{x\right\}) \cap \beta(u) = D' \cap \beta(u)\) (since \(x\notin \beta(u)\)), and \(S^{\tau_1}_v \subseteq X'\). Since Definition 4[it:type-1] and 4[it:type-3] are trivially satisfied, to complete our proof we will show that for each vertex \(w\in V(G_{< v}) \cup \tau^{cov}\), \(\exists w_1,w_2\in X\) such that \(w\in I(w_1,w_2)\) and \(w_1\in X\setminus S^\tau_v\). Targeting a contradiction, let there be some vertex \(w'\in V(G_{< u})\cup \tau^{cov}_1\) such that there is no \(w'_1,w'_2 \in X'\) such that \(w'\in I(w'_1,w'_2)\) and \(w'_1\in X'\setminus S^{\tau_1}_v\). Since, \(\tau^{cov}_1\subseteq \tau^{cov}\) and \(V(G_{\leq u})\setminus \beta(u) = V(G_{\leq v})\setminus \beta(v)\), we have that \(w'\in (V(G_{\leq v})\setminus \beta(v)) \cup \tau^{cov}\). Therefore, \(\exists w_1,w_2\in X\) such that \(w'\in I(w_1,w_2)\) and \(w_1\in X\setminus S^\tau_v \subseteq (X'\setminus S^{\tau_1}_u)\cup \left\{x\right\}\). We distinguish two cases depending on whether \(x\in \tau^{bag}\) or not.

1. \(x\notin \tau^{bag}\): Then, \(w_1 \neq x\) and \(w_2\neq x\). In this case \(w_1\in X'\setminus S^{\tau_1}_u\). Here, if \(w_2\in X'\setminus S^{\tau_1}_u\), then we reach a contradiction since \(w'\in I(w_1,w_2)\), \(w_1,w_2\in X'\) and \(w_1\in X'\setminus S^{\tau_1}_v\). If \(w_2\notin X'\setminus S^{\tau_1}_u\), then \(w_2\in S^{\tau}_v\). Thus, \(\exists A\subseteq \beta(v)\) such that \(\tau^{ext}[A]=1\). Now, as per Definition 5[it:intro-c]-[it:intro-d], if \(A\subsetneq \beta(v)\), then \(\tau^{ext}_1[A]=1\) and else, \(\tau^{ext}[\beta(u)]\)=1. In both cases, there is a vertex \(w'_2\in S^{\tau_1}_u\) whose impact on the bag is same as \(w_2\), leading us to a contradiction.

2. \(x\in \tau^{bag}\). If \(w_1\neq x\) and \(w_2\neq x\), then our proof is identical to the above case. Therefore, without loss of generality, let us assume that \(w_1= x\). Since \(x\in \tau^{bag}\), due to Definition 5[it:intro-d], we have that \(\tau^{ext}_1[\beta(u)]=1\), i.e., \(\exists z\in S^{\tau_1}_{u}\) such that \(N_{H^{\tau_1}_{u}}(z)=\beta(u)\). Therefore, if \(w_2\notin S^{\tau}_v\) (i.e, \(w_2\in D\cap (V(G_{\leq v})\setminus \{x\}) = D\cap V(G_{\leq u})\)), then \(w'\in I(w_2,z)\), a contradiction.

   Thus, let us assume that \(w_2\in S^{\tau}_v\). Therefore, \(\exists A\subseteq \beta(v)\setminus \{x\} =\beta(u)\) with \(w'\in A\) such that \(\tau^{ext}[A] = \tau^{ext}_1[A]=1\) (Definition 5[it:intro-h]). We will establish that \(w'\) satisfies all three conditions of Definition 5[it:intro-bnew1]. Moreover, if \(\exists B \subseteq \beta(u)\) with \(w'\in B\) such that \(\tau^{int}_1[B]=1\), then \(w'\) is covered due to Lemma 3(c). Therefore, we have that \(\forall B\subseteq \beta(u)\) with \(w'\in \beta(u)\), \(\tau^{int}_1[B]=0\). Next, if \(\exists B\subseteq \beta(u)\) with \(w'\in B\) such that \(\tau^{ext}_1[B]=1\) and \(\tau^{bag}_1\) contains a vertex \(z\in \beta(u) \setminus (B \setminus \left\{w'\right\})\), then observe that \(w'\in I(z,B_v)\). Therefore, we have that \(\forall B\subseteq \beta(u)\) with \(w'\in \beta(u)\) such that \(\tau^{ext}_1[B] =1\), \(\tau^{bag}_1\subseteq B \setminus \left\{w'\right\}\). Observe that \(w'\) satisfies all three conditions of Definition 5[it:intro-bnew1], implying \(w'\in Cov(v)\). Since \(\tau^{cov}_1 = \tau^{cov}\setminus Cov(v)\) (recall that \(x\in \tau^{bag}\) and hence Definition 5[it:intro-bnew1] is applied) and \(w'\in Cov(v)\), we have that \(w'\notin \tau^{cov}_1(u)\). This is a contradiction to our assumption that \(w'\in \tau^{cov}_1\). This completes our proof.

Finally, we establish that the pair \((\tau,\tau_1)\) satisfies all conditions in Definition 5. Observe that the conditions in Definition 5[it:intro-a], 5[it:intro-bnew], 5[it:intro-bnew1], 5[it:intro-c],5[it:intro-d] follow directly from our construction of \(\tau_1\). Next, we establish other conditions of Definition 5. Since \(\beta(u)\) is a clique cutset that separates \(x\) from \(V(G_{<u})\), we have that \(\tau^{int}[\left\{x\right\}]=1\) if and only if \(x\in \tau^{bag}\) and for all non-empty \(A\subseteq \beta(u)\), \(\tau^{int}[A\cup \{x\}]=0\) (Definition 5[it:intro-f] and 5[it:intro-g]). Definition 5[it:intro-h] follows from the fact that \(D'=D\setminus \{x\}\) and for each \(A\subseteq \beta(u)\), \(\tau^{int}[A]\) and \(\tau^{int}_1[A]\) depend on \(D'\). Finally, to complete our proof, we establish Definition 5[it:intro-e]. First, observe that no two vertices \(y,z\in \beta(v)\setminus \{x\}\) can cover \(x\) since \(G[\beta(v)]\) is a clique. Since \(\beta(u) = \beta(v)\setminus \left\{x\right\}\) separates \(\{x\}\) from \(V(G_{<v})\), we have that for each vertex \(y\in V(G_{<v})\), \(d(y,\beta(v))+1 \leq d(y,x)\). Therefore, in \(H^{\tau}_v\), for any two vertices \(y,z \in V(G_{\leq v})\setminus \{x\}\), it is not possible that \(x\in I(y,z)\). Thus, if \(\exists y,z\in H^{\tau}_v\) such that \(x\in I(y,z)\), then exactly one of \(\left\{y,z\right\}\) must be from \(S^{\tau}_v\) (recall that one of \(\left\{y,z\right\}\) must be from \(V(G_{\leq v})\setminus \{x\}\)). Without loss of generality, let us assume that \(y\in S^{\tau}_v\) and \(z\in V(G_{\leq v})\setminus \{x\}\). Since \(z\in \beta(v)\cap \tau^{bag}\), we have that \(\tau^{int}_1[\{z\}] = 1\) (Lemma 3(a)). Let \(y\) correspond to a vertex of \(S^{\tau}_v\) that is close to \(B\subseteq \beta(v)\), implying \(\tau^{ext}[B]=1\). Since \(x\in I(y,z)\) and \(\beta(v)\) induces a clique, we have that \(z\notin B\) (\(yz\notin E(H^{\tau}_v)\)) and that \(x\in B\). Therefore, \(\tau^{ext}[B\cup \{x\}]=1\). This completes our proof. ◻

Proof. Let \(\beta(v) = \beta(u) \setminus \left\{x\right\}\). Define \(\tau^{bag}_1 = D \cap \beta(u)\). Moreover, define \(\tau^{uncov}_1\) and \(\tau^{cov}_1\) as per Definition 6[it:forget-f], and \(\tau^{ext}_1\) according to Definition 6[it:forget-b] and 6[it:forget-c]. Finally, \(\tau^{int}_1[A] = 1\) if and only if there exists \(y \in D\) such that \(y\) is close to \(A\) with respect to \(\beta(u)\). First, we establish that \(\tau_1\) and \(D\) satisfy all of the conditions in Definition 4, and thus \(\tau_1\) is a type associated with \(u\). Consider the graphs \(H^\tau_v\) and \(H^{\tau_1}_u\). Observe that due to the definition of \(\tau^{ext}_1\), we have that \(S^{\tau}_v = S^{\tau_1}_u\). We claim that \(D\) is a certificate of \((u,\tau_1)\) as well. Clearly, \(S^{\tau_1}_v \subseteq D\) and \(\tau^{bag}_1 = D\cap \beta(u)\), satisfying Definition 4[it:type-1]. To see that Definition 4[it:type-2] is satisfied, observe that \(V(G_{< u})\cup \tau^{cov}_1 \subseteq V(G_{<v}) \cup \tau^{cov}\). Finally, Definition 4[it:type-3] is trivially satisfied since we define \(\tau^{int}_1\) to satisfy this definition. Moreover, Definition 6[it:forget-f] enforces that \(\tau_1\) is compatible with \(\tau\) only if \(x\in \tau^{bag}_1 \cup \tau^{cov}_1\), i.e., \(x\notin \tau^{uncov}_1\).

Next, we establish that \((\tau,\tau_1)\) is a compatible pair. Definition 6[it:forget-a] is trivially satisfied, and we define \(\tau_1\) according to Definitions 6[it:forget-b], 6[it:forget-c], and 6[it:forget-f]. Therefore, to complete our proof, we only need to establish that \((\tau,\tau_1)\) also satisfy Definition 6[it:forget-d] and 6[it:forget-e]. To see that Definition 6[it:forget-d] is satisfied, let \(A\subsetneq \beta(v)\) be an arbitrary subset or \(\beta(v)\). In one direction, if \(\tau^{int}[A] = 1\), then there exists a vertex \(w\in V(G_{<v})\cap D\) such that \(w\) is close to \(A\) with respect to \(\beta(v)\). Since \(A\neq \beta(v)\), clearly \(w\neq x\) as \(G[x\cup \beta(v)]\) is a clique. Because \(\beta(u) = \beta(v) \cup \{x\}\), we have that either \(w\) is close to \(A\) or \(A\cup \left\{x\right\}\) in \(\beta(u)\), implying either \(\tau^{int}_1[A]=1\) or \(\tau^{int}_1[A\cup \left\{x\right\}] = 1\). In the other direction, let \(\tau^{int}_1[A]=1\) or \(\tau^{int}_1[A\cup \left\{x\right\}] = 1\). Then, there is a vertex \(w\in D\) such that \(w\) is close to either \(A\) or \(A\cup \left\{x\right\}\) with respect to \(\beta(u)\), and hence clearly, \(w\) is close to \(A\) with respect to \(\beta(v) = \beta(u)\setminus \{x\}\), implying \(\tau^{int}[A]=1\). Finally, we prove that Definition 6[it:forget-e] is satisfied. In one direction, let \(\tau^{int}[\beta(v)] =1\), implying that there is a vertex \(w\in D\cap G_{<v}\) that is close to \(\beta(v)\) (with respect to \(\beta(v)\)). If \(w=x\), then \(x\in \tau^{bag}_1\), and the claim is vacuously true. Thus, we assume that \(w\neq x\). Since each vertex \(y\in \beta(u)\setminus \{x\}\) is at the same distance from \(w\), say \(t\), we have that \(d(w,x) \in \{ t-1,t,t+1\}\). If \(d(w,x)=t-1\), then \(\tau^{int}_1[\left\{x\right\}]=1\), if \(d(w,x)=t\), then \(\tau^{int}_1[\beta(u)]=1\), and if \(d(w,x)=t+1\), then \(\tau^{int}_1[\beta(v)]=1\). In the other direction, let \(\tau^{int}_1[\beta(u)] = 1\), \(\tau^{int}_1[\beta(v)] = 1\), \(\tau^{int}_1[\left\{x\right\}] = 1\), or \(x\in \tau^{bag}_1\). If \(\tau^{int}_1[\beta(u)] = 1\), \(\tau^{int}_1[\beta(v)] = 1\) or \(\tau^{int}_1[\left\{x\right\}]=1\), then using similar arguments as above, we have that \(\tau^{int}[\beta(v)]=1\). If \(x\in \tau^{bag}_1\), then \(x\in D\cap V(G_{<v})\) such that \(x\) is close to \(\beta(v)\) with respect to \(\beta(v)\), implying \(\tau^{int}[\beta(v)]=1\). This completes our proof. ◻

Proof. For each \(i\in \left\{1,2\right\}\) define \(\tau^{bag}_i = \tau^{bag}\) and \(\tau^{int}_i[A] = 1\) if and only if there exists \(y \in D \cap G_{\leq u_i}\) such that \(y\) is close to \(A\) with respect to \(\beta(u_i)\). Define \(\tau^{ext}_i\) according to Definition 7[it:join-b]. Define \(\tau^{cov}_i\) in the following manner: Let \(D_i = D\cap V(G_{\leq u_i})\). Recall the definition of the graph \(H^{\tau_i}_{u_i}\) and \(S^{\tau_i}_{u_i}\) (from beginning of the Section 3.2). Then, let \(\tau^{cov}_i = \left\{w~|~w\in I(x,y)\cap \beta(v), x\in D_i~ \& ~(y\in D_i\cup S^{\tau_i}_{u_i} )\right\}\). Observe that for each \(i\in \left\{1,2\right\}\) the sets \(D_i\) satisfies all of the conditions in Definition 4 for \((u_i,\tau_i)\).

We establish that the triplet \((\tau,\tau_1,\tau_2)\) is compatible. Observe that Definition 7[it:join-a] and 7[it:join-b] are trivially satisfied by construction. Consider \(A\subseteq \beta(v)\) and let \(\left\{i,j\right\} = \left\{1,2\right\}\). If \(\tau^{int}_i[A]=1\), then there is a vertex \(w\in D\cap V(G_{<u_i})\) such that \(w\) is close to \(A\) with respect to \(\beta(u_i)=\beta(v)= \beta(u_j)\), implying \(\tau^{int}[A] =1\), and since \(w\in V(G_{>u_j})\), \(\tau^{ext}_j[A]=1\). Thus, Definition 7[it:join-d] is satisfied. The proof of Definition 7[it:join-e] follows from the fact that \(\beta(u_i)=\beta(u_j) = \beta(v)\) and \(D\cap V(G_{<v}) = D\cap (V(G_{<u_i}) \cup V(G_{<u_j}))\). Finally, to see the Definition 7[it:join-c], observe that, due to Lemma 1, each vertex of \(Cov(u_1,u_2)\) is covered by vertices in \(D\cap (V(G_{<u_i}) \cup V(G_{<u_j}))\), and hence \(\tau^{cov}= \tau^{cov}_1 \cup \tau^{cov}_2 \cup Cov(u_1,u_2)\) and \(\tau^{uncov}= (\tau^{uncov}_1 \cap \tau^{uncov}_2) \setminus Cov(u_1,u_2)\). Therefore, the triplet \((\tau,\tau_1,\tau_2)\) is compatible. ◻

Proof. The statement of the lemma is trivially true when \(v\) is a leaf node. By induction we assume the lemma to be true for all nodes of the subtree rooted at \(v\).

1. Assume that \(v\) is an introduce node. Let \(u\) be the child of \(v\) and \(\beta(v) = \beta(u) \cup \left\{x\right\}\). First, we show that \(sol\left[v , \tau\right]\) is a certificate of \((v,\tau)\). Let \(\tau_1\) be a type associated with \(u\) such that \(sol\left[v , \tau\right] = sol\left[u , \tau_1\right] \cup \tau^{bag}\) and consider the set \(D = sol\left[u , \tau_1\right] \cup \tau^{bag}\cup S^{\tau}_{v}\). By Definition 5[it:intro-a] we have that \(\tau^{bag}_1 = \tau^{bag}\setminus \left\{x\right\}\). Hence, \(D\cap \beta(v) = sol\left[v , \tau\right] \cap \beta(v) = (sol\left[u , \tau_1\right] \cup \tau^{bag}) \cap \beta(v) = (sol\left[u , \tau_1\right] \cap \beta(v)) \cup (\tau^{bag}\cap \beta(v)) = (sol\left[u , \tau_1\right] \cap (\beta(u)\cup \left\{x\right\})) \cup \tau^{bag}= (sol\left[u , \tau_1\right] \cap \beta(u)) \cup \tau^{bag}= \tau^{bag}_1 \cup \tau^{bag}= \tau^{bag}\). Hence, \(D\) satisfies Definition 4[it:type-1].

   Now, consider any vertex \(w\in (V(G_{\leq v}) \setminus \beta(v)) \cup \tau^{cov}\) which is distinct from \(x\). Then \(w\in (V(G_{\leq u}) \setminus \beta(u)) \cup (\tau^{cov}\cap \beta(u))\). Definition 5[it:intro-bnew] and Definition 5[it:intro-bnew1] dictate \(\tau^{cov}_1\). If \(x\notin \tau^{bag}\), then Definition 5[it:intro-bnew] ensures that \(\tau^{cov}_1= \tau^{cov}\cap \beta(u)\) and hence \(w\in (V(G_{\leq u}) \setminus \beta(u)) \cup \tau^{cov}_1\). Now, due to our induction hypothesis, we have that there exists \(w_1,w_2\in sol\left[u , \tau_1\right] \cup S^{\tau_1}_{u}\) such that \(w\in I(w_1,w_2)\) and \(w_1\in sol\left[u , \tau_1\right]\). If \(w_2\in sol\left[u , \tau_1\right]\) then \(w_1,w_2\in sol\left[v , \tau\right]\) and therefore \(w_1,w_2\in D\). Hence, Definition 4[it:type-2] is satisfied in this case. Else, \(w_2\in S^{\tau_1}_{u}\); then, there is a set \(A\subseteq \beta(u)\) such that \(w_2=A\) and \(\tau^{ext}_1[A] = 1\). If \(A\neq \beta(u)\), then, due to Definition 5[it:intro-c], we know that there is a set \(B\supseteq A\) such that \(\tau^{ext}[B]=1\). Hence, there is a vertex \(b\in S^{\tau}_{v}\) such that \(b=B\) and is adjacent to all vertices of \(A\). Observe that \(w\in I(w_1,b)\). If \(A=\beta(u)\), then again, due to Definition 5[it:intro-d] and similar arguments as above, we have a vertex \(b'\in S^{\tau}_{v}\) such that \(w\in I(w_1,b')\). Hence, Definition 4[it:type-2] is satisfied. Now, consider the vertex \(x\). Since \(x\notin \tau^{bag}\), due to Definition 5[it:intro-e], we have sets \(A\subseteq \beta(u)\), \(B\subseteq \beta(v)\setminus A\) such that \(\tau^{int}_1[A]=1\) and \(\tau^{ext}[B\cup \left\{x\right\}]=1\). Hence, \(sol\left[u , \tau_1\right]\) contains a vertex, say \(a\), which is close to \(A\) with respect to \(\beta(u)\). There also exists a vertex, say \(b\in S^{\tau}_{v}\), such that \(b=B\). By Lemma 1, \(x\in I(a,b)\). Therefore, Definition 4[it:type-2] is satisfied in this case. Now, consider the case when \(x\in \tau^{bag}\). Recall the definition of \(Cov(v)\) from Definition 5[it:intro-bnew1], and now, \(\tau^{bag}=\tau^{bag}_1\cup Cov(v)\). We can cover the vertices from \(V(G_{<v})\cup \tau^{cov}_1\) as discussed above. To complete the proof of the fact that Definition 4[it:type-2] is satisfied in this case, we only need to show that for each vertex \(w\in Cov(v)\), there exist vertices \(S^{\tau}_v \cup D\) such that \(w\in I(w_1,w_2)\). Since \(w\in Cov(v)\), we have that \(\exists A\subseteq \beta(v)\setminus \{x\}\) such that \(\tau^{ext}[A]=1\) and since \(x\in \tau^{bag}\), \(\tau^{int}[\{x\}]=1\). Finally, as \(w\in A\cup \{x\}\) and \(A\cap \{x\} =\emptyset\), \(w\) is covered due to Lemma 3(c). Therefore, Definition 4[it:type-2] is satisfied.

   Consider \(A\subseteq \beta(v)\) such that \(\tau^{int}[A]=1\). If \(A=\left\{x\right\}\), then, due to Definition 5[it:intro-f], we have \(x\in \tau^{bag}\) and therefore \(x\in D\). Due to Definition 5[it:intro-g], we have \(A\subseteq \beta(u)\). By Definition 5[it:intro-h], \(\tau^{int}_1[A]=1\) and therefore, \(sol\left[u , \tau_1\right]\) contains a vertex \(w\) such that \(w\in V(G_{\leq u})\) and \(w\) is close to \(A\) with respect to \(\beta(u)\). Since \(v\) is an introduce node with \(\beta(v)=\beta(u)\cup \left\{x\right\}\), \(w\) must be close to \(A\) with respect to \(\beta(v)\). Hence, Definition 4[it:type-3] is satisfied. Hence, \(sol\left[v , \tau\right]\) is a certificate of \((v,\tau)\). Now, Lemma 4 implies that \(sol\left[v , \tau\right]\) is minimum.

2. Now, assume that \(v\) is a forget node. Let \(u\) be the child of \(v\) and \(\beta(v) = \beta(u) \setminus \left\{x\right\}\). First, we show that \(sol\left[v , \tau\right]\) is a certificate of \((v,\tau)\). Let \(\tau_1\) be a type associated with \(u\) such that \(sol\left[v , \tau\right] = sol\left[u , \tau_1\right]\) and consider the set \(D = sol\left[u , \tau_1\right] \cup S^{\tau}_{v}\). By Definition 6[it:forget-a], we have that \(\tau^{bag}= \tau^{bag}_1 \setminus \left\{x\right\}\). Hence, \(D\cap \beta(v) = sol\left[v , \tau\right] \cap \beta(v) = sol\left[u , \tau_1\right] \cap (\beta(u) \setminus \left\{x\right\}) = (sol\left[u , \tau_1\right] \cap \beta(u)) \setminus \left\{x\right\} = \tau^{bag}_1 \setminus \left\{x\right\} = \tau^{bag}\). Hence \(D\) satisfies Definition 4[it:type-1].

   Now, consider any vertex \(w\in (V(G_{\leq v}) \setminus \beta(v)) \cup \tau^{cov}\). Observe that \(V(G_{\leq v}) = V(G_{\leq u})\), \(\beta(v) \subset \beta(u)\). Moreover, due to Definitions 6[it:forget-b] and 6[it:forget-c], we have that \(\tau^{ext}=\tau^{ext}_1\). Therefore, for any \(w\in (V(G_{\leq u}) \setminus \beta(u)) \cup \tau^{cov}_1\), there exist \(w_1,w_2 \in sol\left[u , \tau_1\right] =sol\left[v , \tau\right]\) such that \(w\) is covered by \(w_1,w_2\) in \(H^{\tau}_{v}\). Hence, Definition 4[it:type-2] is satisfied.

   By Definition 6[it:forget-d], for \(A\subsetneq \beta(v)\), \(\tau^{int}[A] = 1\) if and only if \(\tau^{int}_1[A] = 1\) or \(\tau^{int}_1[A \cup \left\{x\right\}] = 1\). Indeed, if some \(y \in G_{\leq v}\) is close to \(A\) or \(A \cup \left\{x\right\}\) with respect to \(\beta(u)\), then it is close to \(A\) with respect to \(\beta(v)\). Conversely, if there exists some \(y \in G_{\leq v}\) close to \(A\) with respect to \(\beta(v)\), then \(A\) is \(B \cap \beta(v)\) where \(B\) is the set to which \(y\) is close to with respect to \(\beta(u)\). The only possibilities for \(B\) are \(A\) and \(A \cup \left\{x\right\}\). By Definition 6[it:forget-e], \(\tau^{int}[\beta(v)] = 1\) if and only if \(\tau^{int}_1[\beta(u)] = 1\), \(\tau^{int}_1[\beta(v)] = 1\), \(x\in \tau^{bag}_1\), or \(\tau^{int}_1[\left\{x\right\}] = 1\). Indeed, if some \(y \in G_{\leq v}\) is close to \(\beta(u)\), \(\beta(v)\) or \(\left\{x\right\}\) with respect to \(\beta(u)\), then it is close to \(\beta(v)\) with respect to \(\beta(v)\). Conversely, if there exists some \(y \in G_{\leq v}\) close to \(\beta(v)\) with respect to \(\beta(v)\), then \(\beta(v)\) is included in \(A\) or \(\beta(u) \setminus A\), where \(A\) is the set to which \(y\) is close to with respect to \(\beta(u)\). The only possibilities for \(A\) are \(\beta(u)\), \(\beta(v)\) or \(\left\{x\right\}\). Hence Definition 4[it:type-3] is satisfied. Hence, \(sol\left[v , \tau\right]\) is a certificate of \((v,\tau)\). Finally, Lemma 5 implies that \(sol\left[v , \tau\right]\) is minimum.

3. Assume \(v\) to be a join node. Let \(u_1,u_2\) be the children of \(v\). Let \(\tau_1,\tau_2\) be types associated with \(u_1,u_2\) such that \(sol\left[v , \tau\right] = sol\left[u_1 , \tau_1\right] \cup sol\left[u_2 , \tau_2\right]\). Consider the set \(D=sol\left[v , \tau\right] \cup S^{\tau}_{v}\). Due to Definition 7[it:join-a] we have \(\tau^{bag}= \tau^{bag}_1=\tau^{bag}_2\). This implies \(sol\left[v , \tau^{bag}\right] \cap \beta(v) = (sol\left[u , \tau_1\right] \cap \tau^{bag}_1) \cup (sol\left[u_2 , \tau_2\right] \cap \tau^{bag}_2) = \tau^{bag}\).

   Consider \(y \in (V(G_{\leq v}) \setminus \beta(v)) \cup \tau^{cov}\). If \(y \in (V(G_{\leq u_1}) \setminus \beta(u_1)) \cup \tau^{cov}_1\), then \(y\) is covered by a pair of vertices \(y_1\) and \(y_2\) in \(sol\left[u , \tau_1\right] \cup S^{\tau_1}_{u_1}\). If \(y_1,y_2\in sol\left[u_1 , \tau_1\right]\) then \(y_1,y_2\in D\) and we are done. Otherwise, assume without loss of generality that \(y_2 \in S^{\tau_1}_{u_1} \setminus S^{\tau}_{v}\). There must be a set \(A\subseteq \beta(u_1)\) such that \(\tau^{ext}_1[A]=1\) and \(y_2=A\). By Definition 7[it:join-b], either \(\tau^{ext}[A]=1\) or \(\tau^{int}_2[A]=1\). If the first case is true, then there exists a vertex \(y'_2\in S^{\tau}_{v}\) such that \(y\) is covered by \(y_1\) and \(y'_2\) is in \(G_{\leq v}\). If the second case is true, then there exists a vertex \(y'_2\in sol\left[u_2 , \tau_2\right]\) such that \(y'_2\) is close to \(A\) with respect to \(\beta(u_2)\). Due to Lemma 1, we have that \(y\) is covered by \(y_1\) and \(y'_2\). The case where \(y \in (V(G_{\leq u_2}) \setminus \beta(u_2)) \cup \tau^{cov}_2\) is symmetrical. If \(y \in Cov(u_1,u_2)\), by its definition in Definition 7[it:join-c] and Lemma 1, \(y\) is covered by vertices in \(sol\left[v , \tau\right]\). Hence, Definition 4[it:type-2] is satisfied.

   By Definitions 7[it:join-d] and 7[it:join-e], we have that for any \(A\subseteq \beta(v)\), \(\tau^{int}[A] = 1\) if and only if \(\tau^{int}_1[A] = 1\) or \(\tau^{int}_2[A] = 1\). Therefore by induction Definition 4[it:type-3] is satisfied. The minimality follows from Lemma 6.

4. When \(v\) is the root node, the statement follows easily from Definition 8 and Lemma 7.

This completes the proof. ◻

Proof. If \(v \in X\), then \(A = \left\{v\right\}\). Without loss of generality, assume now that \(\min(v) < \min(X)\) (where \(\min(v)\) denotes the left endpoint of the interval associated to \(v\), and \(\min(X)\), the leftmost left endpoint of an interval of \(X\)). If \(u \in X\) such that \(d(v,u) = d\), then for every \(w \in X\) such that \(\min(w) \leq \min(u)\), \(d(v,w) \leq d\). Indeed, take a shortest path from \(v\) to \(u\) and let \(z\) be the neighbour of \(u\) in this path. Then, \(z\) is also a neighbour of \(w\). This implies that \(v\) is close to a set \(A\) with respect to \(X\) which belongs to one of the following sets: \(\bigcup\limits_{u \in X} \left\{\left\{w \in X| \min(w) \leq \min(u)\right\}\right\}\). Hence, \[\mathcal{A} = \bigcup\limits_{u \in X} \left\{\left\{w \in X| \min(w) \leq \min(u)\right\}, \left\{w \in X| \max(w) \geq \max(u)\right\}, \left\{u\right\}\right\}\] Observe that \(\left|\mathcal{A}\right|\) is \(O(|X|)\). ◻

Proof. Recall that the construction of the start gadget consists of creating two point intervals and two tracks. The construction of one implication gadget consists of creating one point interval and two new tracks. The construction of one AND gadget consists of creating two point intervals (one of which is due to the creation of the insert gadget) and four new tracks. The construction of one covering gadget consists of creating two point intervals and five new tracks. Recall that each variable gadget consists of two implication gadgets, and one clause gadget contains three implication gadgets. Thus, the total number of implication gadgets created is \(2n+3m\). Each clause gadget contains six AND gadgets. Hence, the total number of AND gadgets created is \(6m\). The total number of covering gadgets created is \(m\). So, the total number of tracks created is \(2+4n+35m\). The end gadget contains one distinct point interval for each track. Hence, the total number of point intervals is \(4+ 6n + 52m\). Thus, the total number of intervals in \(D\) is \(O((n+m)^2)\). ◻

Proof. Let \(P = \boldsymbol{u_0} \boldsymbol{u_1} \dots \boldsymbol{u_k} \boldsymbol{v}\) and \(P'\) be a shortest path from \(\boldsymbol{u}\) to \(\boldsymbol{v}\) which starts by the longest common subpath with \(P\). Hence \(P'= \boldsymbol{u_0} \boldsymbol{u_1} \dots \boldsymbol{u_i} \boldsymbol{z} \dots \boldsymbol{v}\) with \(\boldsymbol{z} \notin P\). If \(i=k\) then \(P\) and \(P'\) have the same length. Otherwise, replace \(\boldsymbol{z}\) in \(P'\) by \(\boldsymbol{u_{i+1}}\) to obtain a path \(P''\). It is indeed a path as \(\max(\boldsymbol{z}) < \max(\boldsymbol{u_{i+1}})\). Moreover \(P'\) and \(P''\) have the same length, a contradiction with the definition of \(P'\). ◻

Proof. Let \(P=\boldsymbol{u_0} \ldots \boldsymbol{u_k} \boldsymbol{v} \boldsymbol{u_{k+1}} \ldots \boldsymbol{w}\) be a shortest path between \(\boldsymbol{u_0} = \boldsymbol{u}\) and \(\boldsymbol{w}\) that contains \(\boldsymbol{v}\). Now consider the path \(Q = \boldsymbol{u'_0} \ldots \boldsymbol{u'_k}\) such that \(\boldsymbol{u'_0}=\boldsymbol{u}\) and for \(0\leq i \leq k-1\), \(\boldsymbol{u'_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{u'_i}\). Observe that \(\boldsymbol{u'_k}\) intersects \(\boldsymbol{v}\) and \(\boldsymbol{u'_k}\) does not intersect \(\boldsymbol{u_{k+1}}\) (else, it contradicts the fact that \(P\) is a shortest path). Therefore, \(\boldsymbol{u'_0} \ldots \boldsymbol{u'_k} \boldsymbol{v} \boldsymbol{u_{k+1}} \ldots \boldsymbol{w}\) is a semi-good shortest path containing \(v\). ◻

Proof. Let \(T = \left\{\boldsymbol{a_1},\dots,\boldsymbol{a_j}\right\}\) be the set of intervals of \(T\) such that \(max(\boldsymbol{a_i})=min(\boldsymbol{a_{i+1}})\) for \(i\in [j-1]\). Let \(T({\boldsymbol{o}}) = \left\{\boldsymbol{b_1},\dots,\boldsymbol{b_k}\right\}\) such that \(max(\boldsymbol{b_i})=min(\boldsymbol{b_{i+1}})\) for \(i\in [k-1]\). By Lemma 11, the path induced by the set \(\{{\boldsymbol{o}}, \boldsymbol{b_1},\dots,\boldsymbol{b_k},\boldsymbol{z},\boldsymbol{e_{T}}\}\) is a good shortest path from \({\boldsymbol{o}}\) to \(\boldsymbol{e_{T}}\) where \(z\) is the rightmost neighbour of \(\boldsymbol{b_k}\). Hence the distance between \({\boldsymbol{o}}\) and \(\boldsymbol{e_{T}}\) is \(k+3\).

Observe that both \(\boldsymbol{b_k}\) and \(\boldsymbol{a_j}\) belong to the end gadget and therefore they are adjacent with \(\max(\boldsymbol{b_k}) < \max(\boldsymbol{a_j})\). From the construction it implies that \(\min(\boldsymbol{b_{k}}) < \min(\boldsymbol{a_{j}})\). Since \(\max(\boldsymbol{b_{k-1}}) = \min(\boldsymbol{b_{k}})\), it follows that \(\boldsymbol{b_{k-1}}\) is not adjacent with \(\boldsymbol{a_j}\). Hence the path induced by the set \(\{{\boldsymbol{o}}, \boldsymbol{b_1},\dots,\boldsymbol{b_k},\boldsymbol{a_j},\boldsymbol{e_{T}}\}\) has length \(k+3\) and therefore is a shortest path.

Now, using an inductive argument on \(i\) (from \(i=j\) to \(i=1\)), it follows that \(\boldsymbol{a_i}\) and \(\boldsymbol{b_{k-j+i}}\) are neighbours. Hence, the path induced by the set \(\{{\boldsymbol{o}}, \boldsymbol{b_1},\dots,\boldsymbol{b_{k-j+1}},\boldsymbol{a_1},\dots,\boldsymbol{a_j},\boldsymbol{e_{T}}\}\) induces a shortest path \(P'\) from \({\boldsymbol{o}}\) to \(\boldsymbol{e_{T}}\) such that \(V(T)\subseteq V(P')\). Hence, \(T \subseteq I({\boldsymbol{o}}, \boldsymbol{e_{T}})\). ◻

Proof. Consider the track \(T(\boldsymbol{p})\). Observe from the construction of \(IMP\left[\neg \boldsymbol{\boldsymbol{p}} \rightarrow \boldsymbol{\boldsymbol{q}}\right]\) that there exists a subset \(\left\{\boldsymbol{v_1}, \boldsymbol{v_2}, \ldots, \boldsymbol{v_{k+2}}\right\} \subseteq T(\boldsymbol{p})\) such that \(\boldsymbol{p}\) and \(\boldsymbol{v_1}\) are adjacent, \(\boldsymbol{v_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{v_{i}}\) for \(1 \leq i \leq k+1\) and \(\boldsymbol{v_k}\) is the leftmost neighbour of \(\boldsymbol{q}\). By Lemma 11, \(\left\{\boldsymbol{p},\boldsymbol{v_1},\boldsymbol{v_2}, \ldots, \boldsymbol{v_k}, \boldsymbol{v_{k+1}}, \boldsymbol{v_{k+2}}, \boldsymbol{s_q}\right\}\) induces a good shortest path between \(\boldsymbol{p}\) and \(\boldsymbol{s_q}\). Hence, the path induced by \(\left\{\boldsymbol{p},\boldsymbol{v_1},\boldsymbol{v_2}, \ldots, \boldsymbol{v_k}, \boldsymbol{q}, \boldsymbol{r_q}, \boldsymbol{s_q}\right\}\) is also a shortest path between \(\boldsymbol{p}\) and \(\boldsymbol{s_q}\).

Now consider the track \(T({\boldsymbol{o}})\). Observe from the construction of \(IMP\left[\neg \boldsymbol{\boldsymbol{p}} \rightarrow \boldsymbol{\boldsymbol{q}}\right]\) that there exists a subset \(\left\{\boldsymbol{w_1}, \boldsymbol{w_2}, \ldots, \boldsymbol{w_{t}}\right\} \subseteq T({\boldsymbol{o}})\) such that \(\boldsymbol{w_1}\) is the rightmost neighbour of \({\boldsymbol{o}}\), \(\boldsymbol{w_{i+1}}\) is the leftmost neighbour of \(\boldsymbol{v_{i}}\) for \(1 \leq i \leq t-1\), \(\boldsymbol{s_q}\cap \boldsymbol{w}_{t-1}=\emptyset\), and \(\boldsymbol{s_q}\subset \boldsymbol{w}_t\). By Lemma 11, the set \(\left\{{\boldsymbol{o}},\boldsymbol{w_1},\boldsymbol{w_2}, \ldots, \boldsymbol{w_{t-1}}, \boldsymbol{w_t}, \boldsymbol{s_q}\right\}\) is a shortest path between \({\boldsymbol{o}}\) and \(\boldsymbol{s_q}\) of length \(t+1\). Also observe from the construction that \(\boldsymbol{w}_{t-1}\) is adjacent to \(\boldsymbol{r}_q\). Hence, the path induced by the set \(\left\{{\boldsymbol{o}},\boldsymbol{w_1},\boldsymbol{w_2}, \ldots, \boldsymbol{w_{t-1}}, \boldsymbol{r_q}, \boldsymbol{s_q}\right\}\) is a shortest path between \({\boldsymbol{o}}\) and \(\boldsymbol{s_q}\). ◻

Proof. Let \(T\) denote the track \(T(\boldsymbol{z})\) and let \(T=\left\{\boldsymbol{u_1},\boldsymbol{u_2},\ldots,\boldsymbol{u_{k}}\right\}\) such that \(\boldsymbol{u_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{u_{i}}\) for all \(1\leq j\leq k-1\). Observe from the construction that the path induced by the set \(\left\{\boldsymbol{d_{i}},\boldsymbol{z},\boldsymbol{u_1},\boldsymbol{u_2},\ldots,\boldsymbol{u_{k}},\boldsymbol{e_{T}}\right\}\) is a shortest path between \(\boldsymbol{d_{i}}\) and \(\boldsymbol{e_{T}}\). This proves the first part of the proposition. For the second part, consider the path \(P\) induced by the set \(\left\{\boldsymbol{z},\boldsymbol{u_1},\boldsymbol{u_2},\boldsymbol{cov_{i}},\boldsymbol{f_{i}}\right\}\). Clearly, \(P\) is a shortest path between \(\boldsymbol{z}\) and \(\boldsymbol{f_{i}}\). ◻

Proof. First, we prove (a). Consider the track \(T(\boldsymbol{\sigma(p,q)})\). Observe from the construction that \(T(\boldsymbol{\sigma(p,q)})\) can be partitioned into two sets \(P_a=\left\{\boldsymbol{u_1},\boldsymbol{u_2},\ldots,\boldsymbol{u_j}\right\}\) and \(P'_a = \left\{\boldsymbol{u_{j+1}},\boldsymbol{u_{j+2}},\ldots,\boldsymbol{u_k}\right\}\) where \(\boldsymbol{u_1}\) is the rightmost neighbour of \(\boldsymbol{\sigma(p,q)}\), \(\boldsymbol{u_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{u_i}\) for all \(1\leq i\leq k-1\), and \(\boldsymbol{u_j}\) is the interval of \(T(\boldsymbol{\sigma(p,q)})\) with minimal index which intersects \(\boldsymbol{\boldsymbol{\gamma\left(p,q\right)}}\). Let \(\boldsymbol{z_a}\) be the rightmost neighbour of \(\boldsymbol{u_k}\). Since \(\boldsymbol{u_k}\in \mathscr{E}\), either \(\boldsymbol{z_a} = \boldsymbol{u_{T_2}}\) or \(\max(\boldsymbol{z_a})\geq \max(\boldsymbol{e_{T_2}})\). Therefore \(\boldsymbol{e_{T_2}}\) is adjacent to \(\boldsymbol{z_a}\). Hence, by Lemma 11, the path induced by \(Q_a=\left\{\boldsymbol{\sigma(p,q)}\right\} \cup P_a \cup P'_a \cup \left\{\boldsymbol{z_a},\boldsymbol{e_{T_2}}\right\}\) is a good shortest path between \(\boldsymbol{\sigma(p,q)}\) and \(\boldsymbol{e_{T_2}}\). Observe from the construction that \(|T_2| = |P'|\). Therefore, the set \(Q'_a=\left\{\boldsymbol{\sigma(p,q)}\right\} \cup P_a \cup \left\{\boldsymbol{\gamma\left(p,q\right)}\right\} \cup T_2 \cup \{ \boldsymbol{e_{T_2}}\}\) has the same cardinality as \(Q_a\). Moreover, \(Q'_a\) induces a path. This implies \(Q'_a\) induces a shortest path between \(\boldsymbol{\sigma(p,q)}\) and \(\boldsymbol{e_{T_2}}\).

Second, we prove (b). Consider the track \(T(\boldsymbol{p})\). Observe from the construction that \(T(\boldsymbol{p})\) can be partitioned into two sets \(P_b=\left\{\boldsymbol{v_1},\boldsymbol{v_2},\ldots,\boldsymbol{v_{j'}}\right\}\) and \(P'_b = \left\{\boldsymbol{v_{j'+1}},\boldsymbol{v_{j'+2}},\ldots,\boldsymbol{v_{k'}}\right\}\) where \(\boldsymbol{v_1}\) is the rightmost neighbour of \(\boldsymbol{p}\), \(\boldsymbol{v_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{v_i}\) for all \(1\leq i\leq k'-1\), and \(\boldsymbol{v_{j'}}\) is the interval of \(T(\boldsymbol{p})\) with minimal index which intersects \(\boldsymbol{\boldsymbol{\alpha\left(p,q\right)}}\). Let \(\boldsymbol{z_b}\) be the rightmost neighbour of \(\boldsymbol{v_{k'}}\). Since \(\boldsymbol{v_{}k'}\in \mathscr{E}\), either \(\boldsymbol{z_b} = \boldsymbol{u_{T_1}}\) or \(\max(\boldsymbol{z_b})\geq \max(\boldsymbol{e_{T_1}})\). Therefore \(\boldsymbol{e_{T_1}}\) is adjacent to \(\boldsymbol{z_b}\). Hence, by Lemma 11, the path induced by \(Q_b=\left\{\boldsymbol{p}\right\} \cup P_b \cup P'_b \cup \left\{\boldsymbol{z_b},\boldsymbol{e_{T_1}}\right\}\) is a good shortest path between \(\boldsymbol{p}\) and \(\boldsymbol{e_{T_1}}\). Observe from the construction that \(|T_1| = |P'_b|\). Therefore, the set \(Q'_b=\left\{\boldsymbol{p}\right\} \cup P_b \cup \left\{\boldsymbol{\alpha\left(p,q\right)}\right\} \cup T_1 \cup \{ \boldsymbol{e_{T_1}}\}\) has the same cardinality as \(Q_b\). Moreover, \(Q'_b\) induces a path. This implies \(Q'_b\) induces a shortest path between \(\boldsymbol{p}{q}\) and \(\boldsymbol{e_{T_1}}\). Using similar arguments, we can show that \(\boldsymbol{\delta\left(p,q\right)} \in I(\boldsymbol{q}, \boldsymbol{e_{T_3}})\).

Finally, we prove \((c)\). Observe from the construction that the distance between \(\boldsymbol{\beta\left(p,q\right)}\) and \(\boldsymbol{\delta\left(p,q\right)}\) is two and therefore \(\boldsymbol{\alpha\left(p,q\right)} \in I(\boldsymbol{\beta\left(p,q\right)} , \boldsymbol{\gamma\left(p,q\right)})\). Let \(T_3 = \left\{\boldsymbol{w_1},\boldsymbol{w_2},\ldots,\boldsymbol{w_{k''}}\right\}\) such that \(\boldsymbol{w_1}\) is the rightmost neighbour of \(\boldsymbol{\delta\left(p,q\right)}\), \(\boldsymbol{w_{i+1}}\) is the rightmost neighbour of \(\boldsymbol{w_i}\) for all \(1\leq i\leq k''-1\). Hence, by Lemma 11, the path induced by \(\left\{\boldsymbol{\delta\left(p,q\right)}, \boldsymbol{w_1},\boldsymbol{w_2},\ldots,\boldsymbol{w_{k''}}, \boldsymbol{e_{T_3}}\right\}\) is a good shortest path. Now observe from the construction that the distance between \(\boldsymbol{w_1}\) and \(\boldsymbol{\gamma\left(p,q\right)}\) is two and no neighbour of \(\boldsymbol{\gamma\left(p,q\right)}\) is adjacent to \(\boldsymbol{w_i}\) for \(2\leq i \leq k''\). This implies that the path induced by the set \(\left\{ \boldsymbol{\gamma\left(p,q\right)}, \boldsymbol{\delta\left(p,q\right)}, \boldsymbol{w_1},\boldsymbol{w_2},\ldots,\boldsymbol{w_{k''}}, \boldsymbol{e_{T_3}}\right\}\) is a shortest path between \(\boldsymbol{\gamma\left(p,q\right)}\) and \(\boldsymbol{e_{T_3}}\). This completes the proof. ◻

Proof. We shall show that if \(F\) is satisfiable, then \(D\) has a geodetic set of cardinality \(4 + 7n + 58m= n_{point} + n + 6m\). Let \(S_p\) denote the set of point intervals in \(D\). Note that the point intervals are the only simplicial vertices in \(D\). Hence, they must all belong to any geodetic set of \(D\). Let \(\phi \colon \{ x_1,x_2,\ldots,x_n \} \rightarrow \{1,0\}\) be a satisfying assignment of \(F\). Now, define the following sets. Let \(S_1=\{ \boldsymbol{x_i} \colon \phi(x_i)=1 \} \cup \{ \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu} \colon \phi(x_i)=0 \}\). Let \(S_2=\emptyset\). Now, for each clause \(C_i=(\ell_i^1, \ell_i^2, \ell_i^3)\), do the following.

1. If \(\phi(\ell_i^1) = 1\), then put \(S_2=S_2 \cup \left\{\boldsymbol{a_{i}},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^1\mkern-1.5mu}\mkern 1.5mu}\right)}\right\}\) and if \(\phi(\ell_i^1) = 0\) then put \(S_2=S_2 \cup \left\{\boldsymbol{a'_{i}},\boldsymbol{\gamma\left(\boldsymbol{a_{i}},\boldsymbol{\ell_i^1}\right)}\right\}\).

2. If \(\phi(\ell_i^2) = 1\), then put \(S_2=S_2 \cup \left\{\boldsymbol{b_{i}},\boldsymbol{\gamma\left(\boldsymbol{b'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^2\mkern-1.5mu}\mkern 1.5mu}\right)}\right\}\) and if \(\phi(\ell_i^2) = 0\) then put \(S_2=S_2 \cup \left\{\boldsymbol{b'_{i}},\boldsymbol{\gamma\left(\boldsymbol{b_{i}},\boldsymbol{\ell_i^2}\right)}\right\}\).

3. If \(\phi(\ell_i^3) = 1\), then put \(S_2=S_2 \cup \left\{\boldsymbol{c_{i}},\boldsymbol{\gamma\left(\boldsymbol{c'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^3\mkern-1.5mu}\mkern 1.5mu}\right)}\right\}\) and if \(\phi(\ell_i^3) = 0\) then put \(S_2=S_2 \cup \left\{\boldsymbol{c'_{i}},\boldsymbol{\gamma\left(\boldsymbol{c_{i}},\boldsymbol{\ell_i^3}\right)}\right\}\).

Let \(S=S_1\cup S_2 \cup S_p\). We shall show that \(S\) is a geodetic set of \(D\). Due to Lemma 10, we have that \(|S_1 \cup S_2 \cup S_p| = 4 + 7n + 58m\).

As \(S_p \subseteq S\), observe that \({\boldsymbol{o}}\in S\) and for each track \(T\in \mathcal{T}\), the point interval \(\boldsymbol{e_{T}}\in S\). Hence, due to Lemma 13, we have that each track \(T\in \mathcal{T}\) is covered by \(S\).

Consider any variable gadget \(\mathscr{X}_i\) corresponding to the variable \(x_i\). Recall that from the construction, \(\mathscr{X}_i = IMP\left[\neg \boldsymbol{\top} \rightarrow \boldsymbol{x_i}\right] \cup IMP\left[\neg \boldsymbol{x_i} \rightarrow \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\right]\). Due to Lemma 14, we have that \(\boldsymbol{x_i} \in I({\boldsymbol{\top}},\boldsymbol{s_{x_i}})\) and \(\boldsymbol{r_{x_i}} \in I({\boldsymbol{o}},\boldsymbol{s_{x_i}})\). Hence, \(IMP\left[\neg \boldsymbol{\top} \rightarrow \boldsymbol{x_i}\right] \subseteq I(S)\). Now, consider the implication gadget \(IMP\left[\neg \boldsymbol{x_i} \rightarrow \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\right]\). Due to Lemma 14, we have that \(\overline{x_i} \in I({\boldsymbol{o}},\boldsymbol{s_{\overline{x_i}}})\). Since \(\phi\) is a satisfying assignment, then either \(\boldsymbol{\overline{x_i}} \in S\) or \(\boldsymbol{x_i} \in S\). In the latter case, due to Lemma 14, \(\boldsymbol{r_{\overline{x_i}}} \in I(\boldsymbol{x_i}, \boldsymbol{s_{\overline{x_i}}})\). Hence, \(IMP\left[\neg \boldsymbol{x_i} \rightarrow \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\right] \subseteq S\), and therefore \(\mathscr{X}_i \subseteq I(S)\).

Now, consider any clause \(C_i = (\ell_i^1,\ell_i^2,\ell_i^3 )\) and recall the construction of \(\mathscr{C}_i\). Since \(\phi\) is a satisfying assignment, observe that, there exists at least one interval \(\boldsymbol{z} \in \left\{\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}\right\} \cap S\). Now due to Lemma 15, \(\boldsymbol{z}\in I(\boldsymbol{d_{i}}, \boldsymbol{e_{T(\boldsymbol{z})}})\) and \(\boldsymbol{cov_{i}}\in I(\boldsymbol{z},\boldsymbol{f_{i}})\). Hence \(\mathrm{\small COV}[i] \subseteq I(S)\). Now, consider the implication gadget \(IMP\left[\neg \boldsymbol{\boldsymbol{a_{i}}} \rightarrow \boldsymbol{\boldsymbol{a'_{i}}}\right]\). From our definition of \(S_2\), it follows that \(\left\{\boldsymbol{a_{i}},\boldsymbol{a'_{i}}\right\}\cap S \neq \emptyset\). Now due to Lemma 14, \(\boldsymbol{\boldsymbol{a'_{i}}} \in I(S)\) and \(\boldsymbol{r_{\boldsymbol{a'_{i}}}} \in I(S)\). Hence, \(IMP\left[\neg \boldsymbol{\boldsymbol{a_{i}}} \rightarrow \boldsymbol{\boldsymbol{a'_{i}}}\right] \subseteq I(S)\). Repeating the above arguments for \(IMP\left[\neg \boldsymbol{\boldsymbol{b_{i}}} \rightarrow \boldsymbol{\boldsymbol{b'_{i}}}\right]\) and \(IMP\left[\neg \boldsymbol{\boldsymbol{c_{i}}} \rightarrow \boldsymbol{\boldsymbol{c'_{i}}}\right]\), we infer that \[IMP\left[\neg \boldsymbol{\boldsymbol{a_{i}}} \rightarrow \boldsymbol{\boldsymbol{a'_{i}}}\right] \cup IMP\left[\neg \boldsymbol{\boldsymbol{b_{i}}} \rightarrow \boldsymbol{\boldsymbol{b'_{i}}}\right] \cup IMP\left[\neg \boldsymbol{\boldsymbol{c_{i}}} \rightarrow \boldsymbol{\boldsymbol{c'_{i}}}\right] \subseteq I(S)\]

Now, consider the AND gadgets \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\ell_i^1}\right]\) and \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a'_{i}}} , \boldsymbol{\overline{\ell_i^1}}\right]\). From our definition of \(S_2\), it follows that either \(\left\{\boldsymbol{a_{i}},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^1\mkern-1.5mu}\mkern 1.5mu}\right)}\right\} \subseteq S\) or \(\left\{\boldsymbol{a'_{i}},\boldsymbol{\gamma\left(\boldsymbol{a_{i}},\boldsymbol{\ell_i^1}\right)}\right\} \subseteq S\). First consider the case when \(\left\{\boldsymbol{a_{i}},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^1\mkern-1.5mu}\mkern 1.5mu}\right)}\right\} \subseteq S\). This means \(\phi(\ell_i^1)=1\) and therefore \(\boldsymbol{\ell_i^1} \in S\). Now invoking Lemma 16[it:and-cover-1] and [it:and-cover-2] (with \(\boldsymbol{p}=\boldsymbol{\boldsymbol{a_{i}}}\) and \(\boldsymbol{q}=\boldsymbol{\ell_i^1}\)), we have that \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\boldsymbol{\ell_i^1}}\right] \subseteq I(S)\). Also, invoking Lemma 16[it:and-cover-1] and [it:and-cover-3] (\(\boldsymbol{p}=\boldsymbol{a'_{i}}\) and \(\boldsymbol{q} = \boldsymbol{\overline{\ell_i^1}}\)) we have that \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a'_{i}}} , \boldsymbol{\boldsymbol{\overline{\ell_i^1}}}\right] \subseteq I(S)\). The above arguments imply that when \(\left\{\boldsymbol{a_{i}},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^1\mkern-1.5mu}\mkern 1.5mu}\right)}\right\} \subseteq S\), we have \[\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\ell_i^1}\right] \cup \mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a'_{i}}} , \boldsymbol{\overline{\ell_i^1}}\right] \subseteq I(S)\]

Similarly when \(\left\{\boldsymbol{a'_{i}},\boldsymbol{\gamma\left(\boldsymbol{a_{i}},\boldsymbol{\ell_i^1}\right)}\right\} \subseteq S\) using similar arguments we have \(\left(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\ell_i^1}\right] \cup \mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a'_{i}}} , \boldsymbol{\overline{\ell_i^1}}\right]\right) \subseteq I(S)\). Now arguing similarly for \(\left(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{b_{i}}} , \boldsymbol{\ell_i^2}\right] \cup \mathrm{\small AND}\left[\boldsymbol{\boldsymbol{b'_{i}}} , \boldsymbol{\overline{\ell_i^2}}\right] \right)\) and \(\left(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{c_{i}}} , \boldsymbol{\ell_i^3}\right] \cup \mathrm{\small AND}\left[\boldsymbol{\boldsymbol{c'_{i}}} , \boldsymbol{\overline{\ell_i^3}}\right]\right)\), we have that \(\mathscr{C}_i\subseteq I(S)\). This completes the proof. ◻

Proof. Let \(U\) consists of all intervals contained in some track. In other words, \(U=\displaystyle\bigcup\limits_{T\in \mathcal{T}} T\). Let \(S_p\) denote the set of point intervals in \(D\). Observe that \(S_p \subseteq S\). Let \(\boldsymbol{u} \in S \cap U\) be the interval with \(min(S\cap U)=min(\boldsymbol{u})\) such that \(\boldsymbol{u}\) belongs to a track with a root \(\boldsymbol{y}\). Let \(A_1\) and \(A_2\) be the sets of all \(\boldsymbol{\gamma\left(p,q\right)}\) intervals and \(\boldsymbol{r}_q\) intervals in \(D\), respectively. Let \(A_3 = \left\{\boldsymbol{z}\in D \colon \boldsymbol{z}\in \left\{\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}\right\}, 1\leq i\leq m\right\}\) and \(A = A_1 \cup A_2 \cup A_3\) and \(\overline{A}=D \setminus (A \cup U \cup S_p)\). Due to Lemma 13, 14, 15, and 16, observe that, \(A\cup U \subseteq I(S_p)\). Therefore, we will be done by proving the following claim.

To prove the claim, define \(S_1=\left\{ \boldsymbol{w}\in S \colon min(\boldsymbol{w}) < min(\boldsymbol{u}) \right\}\) and \(S_2=\left\{\boldsymbol{w}\in S \colon min(\boldsymbol{u}) < min(\boldsymbol{w})\right\}\). First, assume that \(\boldsymbol{v} \in S_1\) and \(\boldsymbol{z}\) be an interval in \(I(\boldsymbol{u},\boldsymbol{v})\cap \overline{A}\). In this case, \(\boldsymbol{v}\) must be a root of some track \(T\) (by definition of \(\boldsymbol{u}\)). Now, we have the following cases.

1. Assume \(\boldsymbol{z}=\boldsymbol{q}\) for some implication gadget \(IMP\left[\neg \boldsymbol{\boldsymbol{p}} \rightarrow \boldsymbol{\boldsymbol{q}}\right]\). Then by Lemma 12, there exists a semi-good shortest path \(Q\) between \(\boldsymbol{v}\) and \(\boldsymbol{u}\) containing \(\boldsymbol{q}\). From the construction of \(IMP\left[\neg \boldsymbol{p} \rightarrow \boldsymbol{q}\right]\), this is only possible if \(\boldsymbol{v} = \boldsymbol{p}\). By Lemma 14, \(\boldsymbol{q}\in I(\boldsymbol{p},\boldsymbol{s_q})\).

2. Assume \(\boldsymbol{z} = \boldsymbol{cov_{i}}\) for some \(1\leq i \leq m\). Using similar arguments as above and Lemma 15, we can show that \(\boldsymbol{v} \in \left\{\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}\right\}\) and therefore \(\boldsymbol{z}\in I(\boldsymbol{v}, \boldsymbol{f_{i}})\).

3. Assume \(\boldsymbol{z} \in \left\{\boldsymbol{\alpha\left(p,q\right)} ,\boldsymbol{\delta\left(p,q\right)}\right\}\) for some AND gadget \(\mathrm{\small AND}\left[\boldsymbol{p} , \boldsymbol{q}\right]\). Using arguments as in Case \(1\) and Lemma 16, we can show that \(\boldsymbol{v} \in \left\{\boldsymbol{p},\boldsymbol{q}\right\}\) and therefore \(\boldsymbol{z}\in I(\boldsymbol{v} \cup S_p)\).

The above cases imply that when \(\boldsymbol{v} < \boldsymbol{u}\), then \(I(\boldsymbol{v},\boldsymbol{u}) \subset I(\boldsymbol{v},\boldsymbol{u'})\), where \(\boldsymbol{u'}\in S \setminus \left\{\boldsymbol{u}\right\}\). Now assume that \(\boldsymbol{v} \in S_2\) and \(\boldsymbol{z} \in I(\boldsymbol{u},\boldsymbol{v})\cap \overline{A}\). Observe that there exists a shortest path from \(\boldsymbol{u}\) to \(\boldsymbol{v}\) that contains \(\boldsymbol{z}\). Consider now the good shortest path between \(\boldsymbol{y}\) and \(\boldsymbol{u}\) concatenated with the shortest path between \(\boldsymbol{u}\) and \(\boldsymbol{v}\) covering \(\boldsymbol{z}\). This is a shortest path between \(\boldsymbol{y}\) and \(\boldsymbol{w}\) covering \(\boldsymbol{z}\). This completes the proof of the claim.

The above arguments imply that \(S^*=(S\setminus \left\{\boldsymbol{u}\right\})\cup \left\{\boldsymbol{y}\right\}\) is also a geodetic set of \(D\). Arguing similarly for all intervals in \(S\cap U\), we have the lemma. ◻

Proof. Suppose \(\boldsymbol{q}\notin S^*\). Then, Lemma 12 implies that there exists a semi-good shortest path \(P\) containing \(\boldsymbol{q}\) whose end-vertices lie in \(S^*\). Then, there must exist two intervals \(\boldsymbol{u_1},\boldsymbol{v_1}\) in \(P\) such that both \(\boldsymbol{u_1},\boldsymbol{v_1}\) intersect \(\boldsymbol{q}\) and \(\max{(\boldsymbol{u_1})}<\min{(\boldsymbol{v_1})}\). From the construction of \(IMP\left[\neg \boldsymbol{p} \rightarrow \boldsymbol{q}\right]\), it follows that \(\boldsymbol{u_1}\in T(\boldsymbol{p})\). Since \(S^*\) is a good geodetic set, our construction implies that \(\boldsymbol{p}\in S^*\). ◻

Proof. Suppose that \(S^*\cap \left\{\boldsymbol{\alpha\left(p,q\right)},\boldsymbol{\gamma\left(p,q\right)},\boldsymbol{\delta\left(p,q\right)}\right\}=\emptyset\). Then, Lemma 12 implies that there exists a shortest path \(P\) containing \(\boldsymbol{\alpha\left(p,q\right)}\) whose end-vertices lie in \(S^*\). Then, there must exist two intervals \(\boldsymbol{u_1},\boldsymbol{v_1}\) in \(P\) such that both \(\boldsymbol{u_1},\boldsymbol{v_1}\) intersect \(\boldsymbol{\alpha\left(p,q\right)}\) and \(\max{(\boldsymbol{u_1})}<\min{(\boldsymbol{v_1})}\). From the construction of \(\mathrm{\small AND}\left[\boldsymbol{p} , \boldsymbol{q}\right]\) it follows that \(\boldsymbol{u_1}\in T(\boldsymbol{p})\). Since \(S^*\) is a good geodetic set, our construction implies that \(\boldsymbol{p}\in S^*\).

Now, Lemma 12 implies that there exists a semi-good shortest path \(Q\) containing \(\boldsymbol{\delta\left(p,q\right)}\), whose end-vertices lies in \(S^*\). Then, there must exist two intervals \(\boldsymbol{u_2},\boldsymbol{v_2}\) in \(Q\) such that both \(\boldsymbol{u_2},\boldsymbol{v_2}\) intersect \(\boldsymbol{\delta\left(p,q\right)}\) and \(\max{\boldsymbol{u_2}}<\min{\boldsymbol{v_2}}\). From the construction of \(\mathrm{\small AND}\left[\boldsymbol{p} , \boldsymbol{q}\right]\), it follows that either \(\boldsymbol{u_2}\in T(\boldsymbol{q})\) or \(\boldsymbol{u_1}=\boldsymbol{\gamma\left(p,q\right)}\).

Consider the case when \(\boldsymbol{u_1}=\boldsymbol{\gamma\left(p,q\right)}\). Since \(\boldsymbol{\gamma\left(p,q\right)} \notin S^*\), there must exist an interval \(\boldsymbol{w_2}\) in \(Q\) such that \(\boldsymbol{\gamma\left(p,q\right)}\) intersects \(\boldsymbol{w_2}\) and the distance between \(\boldsymbol{w_2}\) and \(\boldsymbol{v_2}\) is exactly three. But again from the construction of \(\mathrm{\small AND}\left[\boldsymbol{p} , \boldsymbol{q}\right]\), it follow that no such \(\boldsymbol{w_2}\) exists, leading to a contradiction. Hence, \(\boldsymbol{u_2}\in T(\boldsymbol{q})\). Since \(S^*\) is a good geodetic set, our construction implies that \(\boldsymbol{q}\in S^*\). ◻

Proof. Recall that \(\mathscr{C}{i}\) contains the gadgets \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\ell_i^1}\right]\) and \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a'_{i}}} , \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mu\ell_i^1\mkern-1.5mu}\mkern 1.5mu}\right]\) (along with some other gadegets). By Lemma 20, if \(\boldsymbol{a_{i}} \notin S^*\) then we need at least one vertex among \(\boldsymbol{\alpha\left(\boldsymbol{a_{i}},\ell^1_i\right)},\boldsymbol{\gamma\left(\boldsymbol{a_{i}},\ell^1_i\right)},\boldsymbol{\delta\left(\boldsymbol{a_{i}},\ell^1_i\right)}\). The same holds when \(\boldsymbol{a_{i}} \notin S^*\), we need at least one among \(\boldsymbol{\alpha\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\delta\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)}\). This implies that (a) holds. Using analogous arguments we can show that \((b)\) and \((c)\) holds. ◻

Proof. Assume none of \(\boldsymbol{\ell^i_1},\boldsymbol{\ell^i_2},\boldsymbol{\ell^i_3}\) is in \(S^*\). Since \(\boldsymbol{\ell^1_i}\notin S^*\), due to Lemma 20, we have that at least one among \(\boldsymbol{\alpha\left(\boldsymbol{a_{i}},\ell^1_i\right)}, \boldsymbol{\gamma\left(\boldsymbol{a_{i}},\ell^1_i\right)}, \boldsymbol{\delta\left(\boldsymbol{a_{i}},\ell^1_i\right)}\) lies in \(S^*\). If \(\boldsymbol{a'_{i}}\notin S^*\), then \(\boldsymbol{a_{i}}\in S^*\) and one more interval from \(\boldsymbol{\alpha\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)}, \boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)}, \boldsymbol{\delta\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)}\) lies in \(S^*\) (Lemma 19 and 20). Therefore, \[\left| S^* \cap \left\{\boldsymbol{a_{i}},\boldsymbol{a'_{i}}, \boldsymbol{\alpha\left(\boldsymbol{a_{i}},\ell^1_i\right)},\boldsymbol{\gamma\left(\boldsymbol{a_{i}},\ell^1_i\right)},\boldsymbol{\delta\left(\boldsymbol{a_{i}},\ell^1_i\right)}, \boldsymbol{\alpha\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\gamma\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\delta\left(\boldsymbol{a'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^1_i\mkern-1.5mu}\mkern 1.5mu\right)}\right\}\right| \geq 3\]

Now, using Lemma 21, we also have \[\left| S^* \cap \left\{\boldsymbol{b_{i}},\boldsymbol{b'_{i}}, \boldsymbol{\alpha\left(\boldsymbol{b_{i}},\ell^2_i\right)},\boldsymbol{\gamma\left(\boldsymbol{b_{i}},\ell^2_i\right)},\boldsymbol{\delta\left(\boldsymbol{b_{i}},\ell^2_i\right)}, \boldsymbol{\alpha\left(\boldsymbol{b'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^2_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\gamma\left(\boldsymbol{b'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^2_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\delta\left(\boldsymbol{b'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^2_i\mkern-1.5mu}\mkern 1.5mu\right)}\right\}\right| \geq 2\] and \[\left| S^* \cap \left\{\boldsymbol{c_{i}},\boldsymbol{c'_{i}}, \boldsymbol{\alpha\left(\boldsymbol{c_{i}},\ell^3_i\right)},\boldsymbol{\gamma\left(\boldsymbol{c_{i}},\ell^3_i\right)},\boldsymbol{\delta\left(\boldsymbol{c_{i}},\ell^3_i\right)}, \boldsymbol{\alpha\left(\boldsymbol{c'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^3_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\gamma\left(\boldsymbol{c'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^3_i\mkern-1.5mu}\mkern 1.5mu\right)},\boldsymbol{\delta\left(\boldsymbol{c'_{i}},\mkern 1.5mu\overline{\mkern-1.5mu\ell^3_i\mkern-1.5mu}\mkern 1.5mu\right)}\right\}\right| \geq 2\]

The above arguments imply that when \(\boldsymbol{a'_{i}}\notin S^*\), \(|S^* \cap \mathscr{C}_i|\geq 7\). Arguing similarly as above, we can show that if at least one of \(\boldsymbol{b'_{i}},\boldsymbol{c'_{i}}\) does not belong to \(S^*\), then also \(|S^* \cap \mathscr{C}_i|\geq 7\). Now consider the case, when \(\left\{\boldsymbol{a'_{i}},\boldsymbol{b'_{i}},\boldsymbol{c'_{i}}\right\}\subset S^*\). Moreover, \(S^*\) contains one interval from each of \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{a_{i}}} , \boldsymbol{\ell^1_i}\right]\), \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{b_{i}}} , \boldsymbol{\ell^2_i}\right]\) and \(\mathrm{\small AND}\left[\boldsymbol{\boldsymbol{c_{i}}} , \boldsymbol{\ell^3_i}\right]\). Now, we will be done by showing that at least one of \(\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}, \boldsymbol{cov_{i}}\) must be in \(S^*\).

Suppose that \(\boldsymbol{cov_{i}}\notin S^*\) and let \(\boldsymbol{cov_{i}} \in I(\boldsymbol{u},\boldsymbol{v})\), where \(\boldsymbol{u},\boldsymbol{v}\in S^*\) and \(min(\boldsymbol{u}) < min(\boldsymbol{v})\). Let \(P\) be a shortest path between \(\boldsymbol{u}\) and \(\boldsymbol{v}\) such that \(P\) contains \(\boldsymbol{cov_{i}}\). Then, \(P\) must contain two distinct intervals \(\boldsymbol{w_1}\) and \(\boldsymbol{w_2}\) such that both \(\boldsymbol{w_1},\boldsymbol{w_2}\) intersects \(\boldsymbol{cov_{i}}\) and \(\max(\boldsymbol{w_1}) < \min(\boldsymbol{w_2})\). From construction of \(\mathrm{\small COV}[i]\), it follows that \(\boldsymbol{w_1}\) lies in \(T(\boldsymbol{z})\), where \(\boldsymbol{z}\in \left\{\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}\right\}\). Now, since \(S^*\) is a good geodetic set, we infer that \(S^*\) contains at least one of \(\boldsymbol{a_{i}},\boldsymbol{b_{i}},\boldsymbol{c_{i}}\). Hence \(S^*\) contains at least seven intervals from \(\mathscr{C}_i\). ◻

Proof. Let \(S\) be a geodetic set of \(D\) with cardinality \(4 + 7n + 58m\). Due to Lemma 18, there exists a good geodetic set \(S^*\) of \(D\) with \(|S^*|\leq |S| \leq 4 + 7n + 58m\). Recall that a variable gadget \(\mathscr{X}_i = IMP\left[\neg \boldsymbol{\top} \rightarrow \boldsymbol{x_i}\right] \cup IMP\left[\neg \boldsymbol{x_i} \rightarrow \boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\right]\). Due to Lemma 19, we know that at least one among \(\left\{\boldsymbol{x_i},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\right\}\) lies in \(S^*\). Let \(S_1 = S^* \cap \left(\bigcup\limits_{1\leq i\leq n} \mathscr{X}_i\right)\), and \(S_2 = S^* \cap \left(\bigcup\limits_{1\leq i\leq m} \mathscr{C}_i\right)\). Let \(S_p\) denote the set of point intervals in \(D\). Note that \(S_p \subseteq S^*\). We have \(|S_1|\geq n\), \(|S_2|\geq 6m\) by Lemma 21, and \(|S_p|=4+ 6n + 52m\). Therefore, \(|S_1|=n\) as \(\left|S^*\right| \leq 4 + 7n + 58m\). This means that for each \(1\leq i\leq n\), exactly one of \(\boldsymbol{x_i},\boldsymbol{\mkern 1.5mu\overline{\mkern-1.5mux_i\mkern-1.5mu}\mkern 1.5mu}\) lies in \(S^*\). Based on these, we define the following truth assignment \(\phi\colon \left\{x_1,\ldots,x_n\right\}\rightarrow \left\{1,0\right\}\) of \(F\). Define \(\phi(x_i)=1\) if \(\boldsymbol{x_i}\in S^*\) and \(\phi(x_i)=0\), otherwise. Using Lemma 21 we can infer that for each \(1\leq i\leq m\), we have that \(|S^*\cap \mathscr{C}_i| = 6\). Due to Lemma 22, at least one of the intervals \(\boldsymbol{\ell^i_1},\boldsymbol{\ell^i_2},\boldsymbol{\ell^i_3}\) lies in \(S^*\). Thus, for at least one literal \(\ell_i^j\), we have that \(\phi(\ell_i^j)=1\), as needed. ◻