# Algorithms and complexity for geodetic sets on interval and chordal graphs

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Galhawat, Dimitri Lajou

<figure><img src="image_1.png" /></figure>

## To cite this version:

Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Galhawat, Dimitri Lajou. Algorithms and complexity for geodetic sets on interval and chordal graphs. 2022. hal-04230514

HAL Id: hal-04230514

https://hal.science/hal-04230514v1

Preprint submitted on 6 Oct 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Algorithms and complexity for geodetic sets on interval and
chordal graphs

Dibyayan Chakraborty*

Sandip Das†

Florent Foucaud ‡§

Harmender Gahlawat ¶

Dimitri Lajou ||

October 6, 2023

Abstract

We study the computational complexity of finding the *geodetic number* of a graph on chordal graphs and interval graphs. A set *S* of vertices of a graph *G* is a *geodetic set* if every vertex of *G* lies in a shortest path between some pair of vertices of *S*. The *MINIMUM GEODETIC SET* (MGS) problem is to find a geodetic set with minimum cardinality of a given graph. We show that *MINIMUM GEODETIC SET* is fixed parameter tractable for chordal graphs when parameterized by its *tree-width* (which equals its clique number). This implies a polynomial-time algorithm for *k*-trees, for fixed *k*. Then, we show that *MINIMUM GEODETIC SET* is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that *MINIMUM GEODETIC SET* is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

# 1 Introduction

A simple undirected graph $G$ has vertex set $V(G)$ and edge set $E(G)$. For two vertices $u, v \in V(G)$, let $I(u, v)$ denote the set of all vertices in $G$ that lie in some shortest path between $u$ and $v$. For a subset $S$ of vertices of a graph $G$, let $I(S) = \bigcup_{u,v \in S} I(u, v)$. We say that $T \subseteq V(G)$ is *covered* by $S$ if $T \subseteq I(S)$. A set of vertices $S$ is a *geodetic set* if $V(G)$ is covered by $S$. The *geodetic number* is the minimum integer $k$ such that $G$ has a geodetic set of cardinality $k$. Given a graph $G$, the *MINIMUM GEODETIC SET* (MGS) problem, introduced in [16], is to compute a geodetic set of $G$ with minimum cardinality. In this paper, we study the computational complexity of *MINIMUM GEODETIC SET* on interval and chordal graphs. *MINIMUM GEODETIC SET* is a natural graph covering problem that falls in the class of problems dealing with the

<footnote>*Corresponding author. Email: d.chakraborty@leeds.ac.uk. School of Computing, University of Leeds, United Kingdom. This research was supported by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39), by the ANR project HOSIGRA (ANR-17-CE40-0022), the ANR project GRALMECO (ANR-21-CE48-0004), the IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001). This paper contains the full versions of parts of an extended abstract from the proceedings of ISAAC 2020 [6].</footnote>

<footnote>†Indian Statistical Institute, Kolkata, India.</footnote>

<footnote>‡Université Clermont Auvergne, CNRS, Clermont Auvergne INP, Mines Saint-Etienne, LIMOS, 63000 Clermont-Ferrand, France.</footnote>

<footnote>§Univ. Orléans, INSA Centre Val de Loire, LIFO EA 4022, F-45067 Orléans Cedex 2, France.</footnote>

<footnote>¶Ben-Gurion University of the Negev, Beersheba, Israel</footnote>

<footnote>||Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France</footnote>
important geometric notion of *convexity*: see [13, 24] for some general discussion on graph convexities. The setting of MINIMUM GEODETIC SET is quite natural, and it can be applied to facility location problems such as the optimal determination of bus routes in a public transport network [7, 25]. See also [12] for further applications. The aim of this paper is to study MINIMUM GEODETIC SET on chordal graphs. Chordal graphs are the graphs with no induced cycle of order greater than 3; equivalently, they are the intersection graphs of subtrees of trees. Their structural properties imply an interesting behaviour of their geodesics for various types of convexity, as pointed out in [11, 13].

The algorithmic complexity of MINIMUM GEODETIC SET has been studied actively. MINIMUM GEODETIC SET is known to be NP-hard on chordal graphs [11], and chordal bipartite graphs [9, 10], subcubic graphs [5], planar graphs [7], co-bipartite graphs [12]. On the positive side, polynomial-time algorithms to solve MINIMUM GEODETIC SET are known for cographs [9], split graphs [9, 11] and more generally well-partitioned chordal graphs [1], ptolemaic graphs [13] and more generally distance-hereditary graphs [19], block-cactus graphs [12], outerplanar graphs [23] and proper interval graphs [12]. From the perspective of parameterized complexity, MINIMUM GEODETIC SET is unlikely to be FPT for the parameters solution size, feedback vertex set number, and pathwidth, combined [20]. The problem is FPT for parameters tree-depth, modular-width and feedback edge set number [20].

To complement the hardness of MINIMUM GEODETIC SET on chordal graphs, in this paper, we design an FPT algorithm for MINIMUM GEODETIC SET on chordal graphs when parameterized by its *treewidth*, which equals its *clique number* $\omega$ minus one. We use dynamic programming on tree-decompositions to prove the following.

**Theorem 1.** MINIMUM GEODETIC SET can be solved in time $2^{2^{O(w)}}$ $n$ for chordal graphs and in time $2^{O(w)}$ $n$ for interval graphs, where $n$ is the order and $w$ the treewidth of the input graph.

This result applies to the following setting. A *k-tree* is a graph formed by starting with a complete graph on ($k+1$) vertices and then repeatedly adding vertices by making each added vertex adjacent to exactly $k$ neighbours forming a ($k+1$)-clique. Allgeier [2] gave a polynomial-time algorithm to solve MINIMUM GEODETIC SET on maximal outerplanar graphs, which is a subclass of 2-trees, and thus our algorithm generalizes this result (note that 2-trees are both chordal and planar), as it shows that MINIMUM GEODETIC SET can be solved in time $2^{2^{O(k)}}$ $n$ for $k$-trees of order $n$. Recall that this is unlikely to hold for partial $k$-trees (which are exactly the graphs of treewidth at most $k$) since MINIMUM GEODETIC SET is W[1]-hard for parameter treewidth [20].

In this paper, we further strengthen the existing NP-hardness result of MINIMUM GEODETIC SET on chordal graphs by proving it to be NP-hard on interval graphs. An interval representation of a graph $G$ is a collection of intervals on the real line such that two intervals intersect if and only if the corresponding vertices are adjacent in $G$. A graph is an interval graph if it has an interval representation. Ekim et al. [12] asked if there is a polynomial-time algorithm for MINIMUM GEODETIC SET on interval graphs. We give a negative answer to their question (note that proper interval graphs are the interval graphs with no induced $K_{1,3}$).

**Theorem 2.** MINIMUM GEODETIC SET is NP-hard for interval graphs (even with no induced $K_{1,5}$).

This result is somewhat surprising, as most covering problems can be solved in polynomial time on interval graphs (but other distance-based problems, like METRIC DIMENSION, are NP-complete for interval graphs [14]). Our reduction (from 3-SAT) uses a quite involved novel technique, that we hope can be used
<figure><img src="image_3.png" /><figcaption>Figure 1: Inclusion diagram for subclasses of chordal graphs. If a class A has an upward path to class B, then A is included in B. For graphs in the green classes, MINIMUM GEODETIC SET is polynomial-time solvable; for graphs in the red classes, it is NP-complete. The results from the two bold boxes are proved in this paper.</figcaption></figure>

to prove similar results for other distance-related problems on interval graphs. The main challenge here is
to overcome the linear structure of the graph to transmit information across the graph. To this end, we use
a sophisticated construction of many parallel tracks, i.e., shortest paths with intervals of (mostly) the same
length spanning roughly the whole graph, and such that each track is shifted with respect to the previous
one. Each track represents shortest paths that will be used by solution vertices from our variable and clause
gadgets. In between the tracks, we are able to build our gadgets.

We remark that MINIMUM GEODETIC SET admits a polynomial-time algorithm on proper interval graphs by a nontrivial dynamic programming scheme [12]. Problems known to be NP-complete on interval graphs but polynomial-time solvable on proper interval graphs are quite rare; two examples known to us are EQUITABLE COLORING [15] and INDUCED SUBGRAPH ISOMORPHISM [17]. Theorem 2 together with the algorithm from [12] adds MINIMUM GEODETIC SET to this list. The state-of-the-art complexity status of MINIMUM GEODETIC SET for various subclasses of chordal graphs is depicted in Figure 1.

**Structure of the paper.** In Section 2, we describe the fixed parameter tractable algorithm for chordal graphs. In Section 3, we prove hardness for interval graphs. We conclude in Section 4.

2 Algorithm for chordal graphs

We give an FPT algorithm for chordal graphs parameterized by the clique number (which is also the tree-
width plus 1). We explain how to improve the complexity in the case of interval graphs after the proof of
the chordal case. Our algorithm performs dynamic programming on a *nice tree decomposition* of the input
chordal graph, as defined in [3] based on the notion of *nice tree-decompositions* for general graphs [21].

**Definition 1.** A *nice tree decomposition* of a chordal graph *G* is a rooted tree *T* where each node *v* is associated to a subset *X*<sub>v</sub> of V(G) called *bag*, and each internal node has one or two children, with the following properties.

1. The set of nodes of T containing a given vertex of G forms a nonempty connected subtree of T.

2. Any two adjacent vertices of G appear in a common node of T.
3. For each node v of the tree, $G[X_v]$ is a clique.

4. Each node of T belongs to one of the following types: introduce, forget, join or leaf.

5. A join node v has two children v_1 and v_2 such that $X_v = X_{v_1} = X_{v_2}$.

6. An introduce node v has one child v_1 such that $X_v \setminus \{x\} = X_{v_1}$, where $x \in X_v$.

7. A forget node v has one son v_1 such that $X_v = X_{v_1} \setminus \{x\}$, where $x \in X_{v_1}$.

8. A leaf node v is a leaf of T with $X_v = \emptyset$.

9. The tree T is rooted at a leaf node r with $X_r = \emptyset$.

In our algorithm, we traverse the nice tree decomposition bottom-up. At each node v of the tree we shall construct a table of size $O(2^{2^{\omega(G)}})$ containing “partial solutions” for the graph induced by the vertices in the bags of the subtree rooted at v (let this graph be denoted as $G_{\le v}$). We associate a “type” to each of these partial solutions which encodes, among other information, the effect of this partial solution to the rest of the graph and vice versa (Definition 2).

a To ensure that at least one of these partial solutions can be “extended” and will be part of a geodetic set with minimum cardinality of $G$, we characterize the shortest path structure between a pair of vertices $u, w$ where $u \in V(G_{\le v})$ and $w \in V(G) \setminus V(G_{\le v})$ (Lemma 3). We observe that the vertices in the bag $X_v$ induce a *clique cutset* (clique whose removal disconnects the graph) and all shortest paths between $u, w$ contain vertices from $X_v$. Let $X' \subseteq X_v$ be the vertices lying in some shortest path between $u, w$ and that have smaller distance to $w$ than $u$. Observe that “pre-selecting” the vertices of $X'$ captures the effect of $w$ on $G_{\le v}$, if $w$ is selected in the solution set. For a given solution set, doing this for all vertices of the set, we obtain a collection of subsets of $X_v$. Hence, by considering all $2^{2^{|X_v|}}$ different collections of subsets of $X_v$, we can capture the possible effects of all the solution vertices in $G - G_{\le v}$ i.e. “*exterior vertices*” on $G_{\le v}$. For different collections of subsets of $X_v$, we have different “types” of partial solutions.

Once we have all the partial solutions for the children of a node v, we show how to extend these to get the partial solutions of v. It is possible that a partial solution of a node of some “type” is extended to a partial solution of its parent of a different “type”. Depending on the node under consideration, we define an exhaustive set of rules to ensure that the extended partial solutions are valid (Definitions 3, 4, 5, 6). We prove the exhaustiveness of these rules in Lemmas 7, 8, 9, 10 and we prove the correctness of our algorithm in Lemma 11.

## 2.1 The algorithm

We shall introduce a few definitions and notations first. Let $G$ be a graph containing a clique $X$ and a vertex $y$. We say that $y$ is *close* to a nonempty set $A \subseteq X$ with respect to $X$, if $d(y, x) = d_y$ when $x \in A$ and $d(y, x) = d_y + 1$ when $x \in X \setminus A$, for some integer $d_y$. The set $X$ is a *clique cutset* of $G$ if $G - S$ is disconnected.

From now on, $T$ shall denote a nice tree decomposition of $G$. For a node $v \in T$, let $G_{\le v}$ be the subgraph of $G$ induced by the vertices present in the nodes of the subtree of $T$ rooted at $v$. We can define similarly $G_{< v}$, $G_{\ge v}$ and $G_{> v}$. For a node $v$ let $\mathcal{T}_v$ be the set of all 4-tuples $\tau = (\tau^{int}, \tau^{ext}, \tau^{cov}, \tau^{bag})$ where $\tau^{int}, \tau^{ext}$ are Boolean vectors of size $2^{|X_v|}$ indexed by subsets of $X_v$ and $\tau^{cov}, \tau^{bag}$ are subsets of $X_v$. Since $|X_v| \le \omega(G)$, the cardinality of $\mathcal{T}_v$ is $2^{2^{O(\omega(G))}}$.
For a node $v$ and a 4-tuple $\tau = (\tau^{\text{int}}, \tau^{\text{ext}}, \tau^{\text{cov}}, \tau^{\text{bag}})$ let $H_v^\tau$ denote the graph obtained by adding a vertex $S$ to $G_{\le v}$ whenever there is a set $S \subseteq X_v$ with $\tau^{\text{ext}}[S] = 1$, and making $S$ adjacent to each $x \in S$. Let $S_v^\tau = \{S: S \subseteq X_v, \tau^{\text{ext}}[S] = 1\}$ denote the newly added vertices. Observe that $G_{\le v}$ is an induced subgraph of $H_v^\tau$ for any 4-tuple $\tau \in \mathcal{T}_v$.

**Definition 2.** Let $v$ be a node of $T$. A 4-tuple $\tau = (\tau^{\text{int}}, \tau^{\text{ext}}, \tau^{\text{cov}}, \tau^{\text{bag}})$ of $\mathcal{T}_v$ is a "type associated with $v$" if there exists a set $D \subseteq V(H_v^\tau)$ such that the following hold.

(i) $S_v^\tau \subseteq D$ and $\tau^{\text{bag}} = D \cap X_v$.

(ii) For a vertex $w \in (V(G_{\le v}) \setminus X_v) \cup \tau^{\text{cov}}$ there exists a pair $w_1, w_2 \in D$ such that $w \in I(w_1, w_2)$ and $w_1 \in D \setminus S_v^\tau$.

(iii) For a subset $A \subseteq X_v$, we have $\tau^{\text{int}}[A] = 1$ if and only if $D \cap V(G_{\le v})$ contains a vertex which is closer to $A$ with respect to $X_v$.

Moreover, we shall say that the set $D \setminus S_v^\tau$ is a "certificate" for $(v, \tau)$.

Intuitively, for a type $\tau$ associated with a node $v$ and for a set $A \subseteq X_v$ of vertices, the Boolean $\tau^{\text{int}}[A]$ represents whether there is some vertex $y$ in the partial solution for $G_{\le v}$ such that $y$ is close to $A$ with respect to $X_v$ ("int" stands for "interior"). The Boolean $\tau^{\text{ext}}[A]$ represents whether we need to add, at a later step of our algorithm, some vertex $y$ which is close to $A$ with respect to $X_v$. Here, $y$ is a vertex of $G_{>v}$ that needs to be added later to the solution, in the upper part of the tree ("ext" stands for "exterior").

Observe that the only type associated with the root node of $T$ is $\tau_0 = (0, 0, \emptyset, \emptyset)$ where $0$ denotes the vector all whose elements are $0$. Now we shall characterize the types associated with different sorts of nodes of the tree decomposition $T$. First, we prove the following lemma which deals with how shortest paths interact with clique cutsets.

**Lemma 3.** Let $X$ be a clique cutset of a graph $G$ and $u, v$ be vertices lying in two different connected components of $G - X$. Let $A$ and $B$ be two subsets of $X$ such that $u$ (resp. $v$) is close to $A$ (resp. $B$) with respect to $X$. Then, a vertex $x \in I(u, v) \cap X$ if and only if $x \in A \cap B$ or, $A \cap B = \emptyset$ and $x \in A \cup B$.

*Proof.* Suppose 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$. Now we consider the following two cases.

1. $A \cap B \neq \emptyset$. If $x \in A \cap B$, then $d(u, v) = d_u + d_v$ as any shorter path would imply the existence of a vertex $y \in X$ such that $d(u, y) + d(y, v) < d_u + d_v$ which would contradict the definition of $A$ and $B$. As $d(u, x) + d(x, v) = d_u + d_v$, $x \in I(u, v)$. Conversely, if $x \notin A \cap B$, let $y \in A \cap B$. Then, $d(u, v) \le d_u + d_v$ as $d(u, y) + d(y, v) = d_u + d_v$. As $d(u, x) + d(x, v) = d_u + d_v + 1$, $x \notin I(u, v)$.

2. $A \cap B = \emptyset$. If $x \in A \cup B$, then $d(u, v) = 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) \le d_u + d_v$ which would contradict $A \cap B = \emptyset$. As $d(u, x) + d(x, v) = d_u + d_v + 1$, $x \in I(u, v)$. Conversely, if $x \notin A \cup B$, let $y \in A$, then $d(u, v) \le d_u + d_v + 1$ as $d(u, y) + d(y, v) = d_u + d_v + 1$. As $d(u, x) + d(x, v) = d_u + d_v + 2$, $x \notin I(u, v)$.

This completes the proof. $\square$
Lemma 3 implies that to compute an optimal partial solution for a given bag $X_v$, it is sufficient to "guess" for which subsets $A$ of $X_v$, there will exist (in the future solution that will be computed for ancestors of $v$) a vertex $y$ which is close to $A$ with respect to $X_v$.

Suppose we have a fixed geodetic set $D$ of $G$. In the following lemma, we show that when $D$ is restricted to a particular subgraph $G_{\le v}$, the set $D \cap G_{\le v}$ acts as a certificate for some $(v, \tau)$. This proves the exhaustiveness of our definition of type.

**Lemma 4.** Let $D$ be a geodetic set of $G$, then for each node $v \in T$, there is a type $\tau$ associated with $v$ such that $D \cap V(G_{\le v})$ is a certificate of $(v, \tau)$.

*Proof.* We construct $\tau$ from $D$ as follows. Define $\tau^{bag} = D \cap X_v$. For each vertex $u \in D \cap V(G_{\le v})$ we find the set $Z_u \subseteq X_v$ such that $u$ is close to $Z_u$ with respect to $X_v$ and put $\tau^{int}[Z_u] = 1$. For each $u \in D \cap V(G_{>v})$ we find the set $Z_u \subseteq X_v$ such that $u$ is close to $Z_u$ with respect to $X_v$ and put $\tau^{ext}[Z_u] = 1$. We put $\tau^{cov} = X_v \setminus D$. Observe that $D \cap V(G_{\le v})$ is a certificate of $(v, \tau)$. $\square$

For a node $v$, there might be some 4-tuples in $\mathcal{T}$ which are not associated with $v$. In the following lemma, we establish certain restrictions that any type associated with $v$ must follow.

**Lemma 5.** Let $v$ be a node of $T$ and $\tau = (\tau^{int}, \tau^{ext}, \tau^{cov}, \tau^{bag})$ be a type associated with $v$. Then $\tau$ must satisfy all of the following conditions.

(a) Whenever we have a vertex $u \in \tau^{bag}$ we have $\tau^{int}[\{u\}] = 1$.

(b) $\tau^{int}[\emptyset] = \tau^{ext}[\emptyset] = 0$.

(c) For all $x \in X_v$, $\tau^{int}[A] = 1$ and $\tau^{ext}[B] = 1$, if $x \in A \cap B$ or if $A \cap B = \emptyset$ and $x \in A \cup B$ then $\tau^{cov}[x] = 1$.

From now on for a node $v$, we will only consider the 4-tuples which satisfy the conditions of Lemma 5. We have the following observation about the leaf nodes of the nice tree decomposition.

**Observation 6.** Let $v$ denote a leaf node. Then $\tau_0 = (0, 0, \emptyset, \emptyset)$ is the only type associated with $v$. Moreover, $\tau_0$ is the only type associated with the root node of $T$.

Let $v$ be an introduce node and $u$ be its child. Let $\tau, \tau_1$ be types associated with $v, u$ respectively. Below we state some rules that $\tau$ and $\tau_1$ must follow so that the certificate for $(u, \tau_1)$ can be extended to a certificate for $(v, \tau)$.

**Definition 3.** Let $v$ be an introduce node and $\tau$ be a type associated with $v$. Let $u$ be the child of $v$ and $\tau_1$ be a type associated with $u$. The pair $(\tau, \tau_1)$ is compatible if the following holds.

(a) $\tau_1^{bag} = \tau^{bag} \setminus \{x\}$.

(b) $\tau_1^{cov} = \tau^{cov} \cap X_u$.

(c) For $A \subsetneq X_u$, $\tau_1^{ext}[A] = 1$ if and only if $\tau^{ext}[A] = 1$ or $\tau^{ext}[A \cup \{x\}] = 1$.

(d) $\tau_1^{ext}[X_u] = 1$ if and only if $\tau^{ext}[X_v] = 1$, $\tau^{ext}[X_u] = 1$, $x \in \tau^{bag}$ or $\tau^{ext}[\{x\}] = 1$.

(e) If $x \notin \tau^{bag}$ then there exist non-empty sets $A \subseteq X_u, B \subseteq X_v \setminus A$ such that $\tau_1^{int}[A] = 1$ and $\tau^{ext}[B \cup \{x\}] = 1$.
(f) $\tau^{\text{int}}[\{x\}] = 1$ if and only if $x \in \tau^{\text{bag}}$.

(g) For all non empty $A \subseteq X_u$, $\tau^{\text{int}}[A \cup \{x\}] = 0$,

(h) For all $A \subseteq X_u$, $\tau^{\text{int}}[A] = 1$ if and only if $\tau_1^{\text{int}}[A] = 1$,

**Lemma 7.** Let $v$ be an introduce node, $\tau$ be a type associated with $v$, $u$ be the child of $v$ and $D$ be a minimal certificate of $(v, \tau)$. Then there exists a type $\tau_1$ associated with $u$ such that $(\tau, \tau_1)$ is a compatible pair.

*Proof.* Let $X_v = X_u \cup \{x\}$. Define $\tau_1^{\text{bag}} = D \cap X_u$, $\tau_1^{\text{cov}} = \tau^{\text{cov}} \cap X_u$ and $\tau_1^{\text{int}}[A] = 1$ if and only if there exists $y \in D \setminus \{x\}$ such that $y$ is close to $A$ with respect to $X_u$. Finally, define $\tau_1^{\text{ext}}$ according to Conditions 3(c) and 3(d). Observe that the set $D' = D \setminus \{x\}$ satisfies all the conditions in Definition 2 for $(u, \tau_1)$ and the pair $(\tau, \tau_1)$ satisfies all conditions in Definition 3. $\square$

Let $C_v$ denote the set of compatible pairs $(\tau, \tau_1)$ where $\tau, \tau_1$ are types associated with $v$ and $u$, respectively.

Let $v$ be a forget node and $u$ be its child. Let $\tau, \tau_1$ be types associated with $v, u$ respectively. Below we state some rules that $\tau$ and $\tau_1$ must follow so that the certificate for $(u, \tau_1)$ can be extended to a certificate for $(v, \tau)$.

**Definition 4.** Let $v$ be a forget node and $\tau$ be a type associated with $v$. Let $u$ be the child of $v$ and $\tau_1$ be a type associated with $u$. The pair $(\tau, \tau_1)$ are compatible if the following holds.

(a) $\tau^{\text{bag}} = \tau_1^{\text{int}} \setminus \{x\}$,

(b) For all $A \subseteq X_v$, $\tau_1^{\text{ext}}[A] = 1$ if and only if $\tau^{\text{ext}}[A] = 1$,

(c) For all $A \subseteq X_v$, $\tau_1^{\text{ext}}[A \cup \{x\}] = 0$.

(d) For $A \subseteq X_v$, $\tau^{\text{int}}[A] = 1$ if and only if $\tau_1^{\text{int}}[A] = 1$ or $\tau_1^{\text{int}}[A \cup \{x\}] = 1$.

(e) $\tau^{\text{int}}[X_v] = 1$ if and only if $\tau_1^{\text{int}}[X_u] = 1$, $\tau_1^{\text{int}}[X_v] = 1$ or $\tau_1^{\text{int}}[\{x\}] = 1$,

(f) $\tau_1^{\text{cov}} = \tau^{\text{cov}} \cup \{x\}$.

**Lemma 8.** Let $v$ be a forget node, $\tau$ be a type associated with $v$, $u$ be the child of $v$, and $D$ be a minimal certificate of $(v, \tau)$. Then there exists a type $\tau_1$ associated with $u$ such that $(\tau, \tau_1)$ is a compatible pair.

*Proof.* Let $X_v = X_u \setminus \{x\}$. Define $\tau_1^{\text{bag}} = D \cap X_u$, $\tau_1^{\text{cov}} = \tau^{\text{cov}} \cup \{x\}$ and $\tau_1^{\text{int}}[A] = 1$ if and only if there exists $y \in D$ such that $y$ is close to $A$ with respect to $X_u$. Finally, define $\tau_1^{\text{ext}}$ according to Definition 4(b) and 4(c). Observe that the set $D$ satisfies all the conditions in Definition 2 for $(u, \tau_1)$ and the pair $(\tau, \tau_1)$ satisfies all conditions in Definition 4. $\square$

Let $C_v$ denote the set of compatible pairs $(\tau, \tau_1)$ where $\tau, \tau_1$ are types associated with $v$ and $u$, respectively.

Let $v$ be a join node, and let $u_1, u_2$ be its children. Let $\tau, \tau_1, \tau_2$ be types associated with $v, u_1, u_2$ respectively. Below we state some rules that $\tau, \tau_1, \tau_2$ must follow so that the certificates for $(u_1, \tau_1)$ and $(u_2, \tau_2)$ can be combined and extended to a certificate for $(v, \tau)$.

**Definition 5.** Let $v$ be a join node and $\tau$ be a type associated with $v$. Let $u_1, u_2$ be the children of $v$ and $\tau_1, \tau_2$ be types associated with $u_1, u_2$ respectively. The triplet $(\tau, \tau_1, \tau_2)$ is compatible if all the following holds.
$$ (a) \tau^{bag} = \tau_{1}^{bag} = \tau_{2}^{bag}, $$

$$ (b) \text{ For } i, j \text{ such that } \{i, j\} = \{1, 2\} \text{ and } A \subseteq X_v, \tau_i^{ext}[A] = 1 \text{ if and only if } \tau_j^{int}[A] = 1 \text{ or } \tau^{ext}[A] = 1. $$

$$ (c) \tau^{cov} = \tau_{1}^{cov} \cup \tau_{2}^{cov} \cup \text{Cov}(u_1, u_2) \text{ where } \text{Cov}(u_1, u_2) \text{ is the subset of vertices } x \text{ of } X_v \text{ such that there exists } A, B \subseteq X_v \text{ with } \tau_{1}^{int}[A] = 1 \text{ and } \tau_{2}^{int}[B] = 1 \text{ where } x \in A \cap B \text{ or where } x \in A \cup B \text{ and } A \cap B = \emptyset. $$

$$ (d) \text{ For } i, j \text{ such that } \{i, j\} = \{1, 2\} \text{ and } A \subseteq X_v, \tau_i^{int}[A] = 1 \text{ then } \tau^{int}[A] = 1 \text{ and } \tau_j^{ext}[A] = 1. $$

$$ (e) \text{ For } i, j \text{ such that } \{i, j\} = \{1, 2\} \text{ and } A \subseteq X_v, \tau_i^{int}[A] = 0 \text{ and } \tau_j^{int}[A] = 0 \text{ then } \tau^{int}[A] = 0. $$

**Lemma 9.** Let $v$ be a join node and $\tau$ be a type associated with $v$. Let $u_1, u_2$ be the children of $v$. Then there are types $\tau_1, \tau_2$ associated with $u_1, u_2$ respectively such that $(\tau, \tau_1, \tau_2)$ is a compatible triplet.

*Proof.* For each $i \in \{1, 2\}$ define $\tau_i^{bag} = \tau^{bag}$ and $\tau_i^{int}[A] = 1$ if and only if there exists $y \in D \cap G_{\le u_i}$ such that $y$ is close to $A$ with respect to $X_{u_i}$. Define $\tau_i^{ext}$ according to Conditions 5(b) and 5(b). Define $\tau_i^{cov}$ according to Definition 5(c). Observe that for each $i \in \{1, 2\}$ the sets $D \cap V(G_{\le u_i})$ satisfies all the conditions in Definition 2 for $(\tau, \tau_i)$ and the triplet $(\tau, \tau_1, \tau_2)$ is compatible. $\square$

For a join node $v$ with children $u_1, u_2$, let $C_v$ denote the set of compatible triplets $(\tau, \tau_1, \tau_2)$ where $\tau, \tau_1, \tau_2$ are types associated with $v, u_1, u_2$, respectively. Finally we consider the root $r$. Recall that the only type associated with $r$ is $\tau_0 = (0, 0, \emptyset, \emptyset)$.

**Definition 6.** Consider the root $r$, its child $u$ with $X_u = \{x\}$ and a type $\tau$ associated with $u$. Then $(\tau_0, \tau)$ is a compatible pair if $x \in \tau_1^{bag}$ and $\tau^{ext}[A] = 0$ for all $A \subseteq X_u$.

The proof for the following lemma is analogous to that of Lemmas 7–9.

**Lemma 10.** For any minimal geodetic set of $G$, there is a compatible pair $(\tau_0, \tau_1)$ where $\tau_1$ is a type associated with $u$.

Let $C_r$ denote the set of compatible pairs $(\tau_0, \tau)$ where $\tau$ is a type associated with the child of $r$.

Now we are ready to describe our algorithm. We process the nodes of $T$ bottom-up. Let $v$ be the current node under consideration. If $v$ is a leaf node, then define

$$ \mathrm{sol}[v, (0, 0, \emptyset, \emptyset)] = \emptyset $$

Let $v$ be an introduce node having $u$ as child. Then for each type $\tau \in \mathcal{T}_v$ define

$$ \mathrm{sol}[v, \tau] = \min_{(\tau, \tau_1) \in C_v} \mathrm{sol}[u, \tau_1] \cup \tau^{bag} $$

Let $v$ be a forget node having $u$ as child. Then for each type $\tau \in \mathcal{T}_v$ define

$$ \mathrm{sol}[v, \tau] = \min_{(\tau, \tau_1) \in C_v} \mathrm{sol}[u, \tau_1] $$

Let $v$ be a join node having $u_1, u_2$ as children. Then for each type $\tau \in \mathcal{T}_v$ define

$$ \mathrm{sol}[v, \tau] = \min_{(\tau, \tau_1, \tau_2) \in C_v} \mathrm{sol}[u_1, \tau_1] \cup \mathrm{sol}[u_2, \tau_2] $$
Finally for the root $r$ let $u$ be its child and $\tau_0 = (0, 0, \emptyset, \emptyset)$. Define

$$ \mathrm{sol}[r, \tau_0] = \min_{(\tau_0, \tau_1) \in C_r} \mathrm{sol}[u, \tau_1] $$

We shall show in the following lemma that $\mathrm{sol}[r, (0, 0, \emptyset, \emptyset)]$ corresponds to a geodetic set of $G$ with minimum cardinality. Recall the definitions of $H_v^\tau$ and $S_v^\tau$.

**Lemma 11.** For each node $v$ and type $\tau$ associated with $v$, $\mathrm{sol}[v, \tau]$ is a certificate of $(v, \tau)$ with minimum cardinality.

*Proof.* The statement of the lemma is trivially true when $v$ is a leaf node. By induction we shall 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$, $X_v = X_u \cup \{x\}$. First we show that $\mathrm{sol}[v, \tau]$ is a certificate of $(v, \tau)$. Let $\tau_1$ be a type associated with $u$ such that $\mathrm{sol}[v, \tau] = \mathrm{sol}[u, \tau_1] \cup \tau^{bag}$ and consider the set $D = \mathrm{sol}[u, \tau_1] \cup \tau^{bag} \cup S_v^\tau$. By Definition 3(a) we have that $\tau_1^{bag} = \tau^{bag} \setminus \{x\}$. Hence $D \cap X_v = \mathrm{sol}[v, \tau] \cap X_v = (\mathrm{sol}[u, \tau_1] \cup \tau^{bag}) \cap X_v = (\mathrm{sol}[u, \tau_1] \cap X_v) \cup (\tau^{bag} \cap X_v) = (\mathrm{sol}[u, \tau_1] \cap (X_u \cup \{x\})) \cup \tau^{bag} = (\mathrm{sol}[u, \tau_1] \cap X_u) \cup \tau^{bag} = \tau_1^{bag} \cup \tau^{bag} = \tau^{bag}$. Hence $D$ satisfies Definition 2(i).

Now, consider any vertex $w \in (V(G_{\le u}) \setminus X_v) \cup \tau^{cov}$ which is distinct from $x$. Then $w \in (V(G_{\le u}) \setminus X_u) \cup (\tau^{cov} \cap X_u)$. Definition 3(b) ensures that $\tau_1^{cov} = \tau^{cov} \cap X_u$ and hence $w \in (V(G_{\le u}) \setminus X_u) \cup \tau_1^{cov}$. Now, due to our induction hypothesis, we have that there exists $w_1, w_2 \in \mathrm{sol}[u, \tau_1] \cup S_u^{\tau_1}$ such that $w \in I(w_1, w_2)$ and $w_1 \in \mathrm{sol}[u, \tau_1]$. If $w_2 \in \mathrm{sol}[u, \tau_1]$ then $w_1, w_2 \in \mathrm{sol}[v, \tau]$ and therefore $w_1, w_2 \in D$. Hence, Definition 2(ii) is satisfied in this case. Assume $w_2 \in S_u^{\tau_1}$; then, there is a set $A \subseteq X_u$ such that $w_2 = A$ and $\tau_1^{ext}[A] = 1$. If $A \neq X_u$, then, due to Definition 3(c), we know that there is a set $B \supseteq A$ such that $\tau_1^{ext}[B] = 1$. Hence, there is a vertex $b \in S_v^\tau$ such that $b = B$ and is adjacent to all vertices of $A$. Observe that $w \in I(w_1, b)$. If $A = X_u$, then again, due to Definition 3(d) and similar arguments as above, we have a vertex $b' \in S_v^\tau$ such that $w \in I(w_1, b')$. Hence, Definition 2(ii) is satisfied. Now, consider the vertex $x$. If $x \in \tau^{bag}$, then $x \in D$. Now, assume that $x \notin \tau^{bag}$. Then, due to Definition 3(e), we have sets $A \subseteq X_u$, $B \subseteq X_v \setminus A$ such that $\tau_1^{int}[A] = 1$ and $\tau^{ext}[B \cup \{x\}] = 1$. Hence, $\mathrm{sol}[u, \tau_1]$ contains a vertex, say $a$, which is close to $A$ with respect to $X_u$. There also exists a vertex, say $b \in S_v^\tau$, such that $b = B$. By Lemma 3, $x \in I(a, b)$. Therefore, Definition 2(ii) is satisfied.

Consider $A \subseteq X_v$ such that $\tau_1^{int}[A] = 1$. If $A = \{x\}$, then, due to Definition 3(f), we have $x \in \tau^{bag}$ and therefore $x \in D$. Due to Definition 3(g), we have $A \subseteq X_u$. By Definition 3(h), $\tau_1^{int}[A] = 1$ and therefore $\mathrm{sol}[u, \tau_1]$ contains a vertex $w$ such that $w \in V(G_{\le u})$ and $w$ is closer to $A$ with respect to $X_u$. Since $v$ is an introduce node with $X_v = X_u \cup \{x\}$, $w$ must be closer to $A$ with respect to $X_v$. Hence, Definition 2(iii) is satisfied. Hence, $\mathrm{sol}[v, \tau]$ is a certificate of $(v, \tau)$. Now, Lemma 7 implies that $\mathrm{sol}[v, \tau]$ is minimum.

2. Now, assume that $v$ is a forget node. Let $u$ be the child of $v$, $X_v = X_u \setminus \{x\}$. First, we show that $\mathrm{sol}[v, \tau]$ is a certificate of $(v, \tau)$. Let $\tau_1$ be a type associated with $u$ such that $\mathrm{sol}[v, \tau] = \mathrm{sol}[u, \tau_1]$ and consider the set $D = \mathrm{sol}[u, \tau_1] \cup S_v^\tau$. By Definition 4(a) we have that $\tau^{bag} = \tau_1^{bag} \setminus \{x\}$. Hence, $D \cap X_v = \mathrm{sol}[v, \tau] \cap X_v = \mathrm{sol}[u, \tau_1] \cap (X_u \setminus \{x\}) = (\mathrm{sol}[u, \tau_1] \cap X_u) \setminus \{x\} = \tau_1^{bag} \setminus \{x\} = \tau^{bag}$. Hence $D$ satisfies Definition 2(i).
Now, consider any vertex $w \in (V(G_{\le v}) \setminus X_v) \cup \tau^{cov}$. Observe that $V(G_{\le v}) = V(G_{\le u})$, $X_v \subset X_u$. Moreover, due to Conditions 4(b) and 4(c), we have that $\tau^{ext} = \tau_1^{ext}$. Therefore, $w \in (V(G_{\le u}) \setminus X_u) \cup \tau_1^{cov}$, there exist $w_1, w_2 \in \text{sol}[u, \tau_1] = \text{sol}[v, \tau]$ such that $w$ is covered by $w_1, w_2$ in $H_v^\tau$. Hence, Definition 2(ii) is satisfied.

By Definition 4(d), for $A \subsetneq X_v$, $\tau^{int}[A] = 1$ if and only if $\tau_1^{int}[A] = 1$ or $\tau_1^{int}[A \cup \{x\}] = 1$. Indeed, if some $y \in G_{\le v}$ is close to $A$ or $A \cup \{x\}$ with respect to $X_u$, then it is close to $A$ with respect to $X_v$. Conversely, if there exists some $y \in G_{\le v}$ close to $A$ with respect to $X_v$, then $A$ is $B \cap X_v$ where $B$ is the set to which $y$ is close to with respect to $X_u$. The only possibilities for $B$ are $A$ and $A \cup \{x\}$. By Definition 4(e), $\tau^{int}[X_v] = 1$ if and only if $\tau_1^{int}[X_u] = 1$, $\tau_1^{int}[X_v] = 1$ or $\tau_1^{int}[\{x\}] = 1$. Indeed, if some $y \in G_{\le v}$ is close to $X_u$, $X_v$ or $\{x\}$ with respect to $X_u$, then it is close to $X_v$ with respect to $X_v$. Conversely, if there exists some $y \in G_{\le v}$ close to $X_v$ with respect to $X_v$, then $X_v$ is included in $A$ or $X_u \setminus A$, where $A$ is the set to which $y$ is close to with respect to $X_u$. The only possibilities for $A$ are $X_u$, $X_v$ or $\{x\}$. Hence Definition 2(iii) is satisfied. Hence, $\text{sol}[v, \tau]$ is a certificate of $(v, \tau)$. Now Lemma 8 implies that $\text{sol}[v, \tau]$ 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 $\text{sol}[v, \tau] = \text{sol}[u_1, \tau_1] \cup \text{sol}[u_2, \tau_2]$. Consider the set $D = \text{sol}[v, \tau] \cup S_v^\tau$. Due to Definition 5(a) we have $\tau^{bag} = \tau_1^{bag} = \tau_2^{bag}$. This implies $\text{sol}[v, \tau^{bag}] \cap X_v = (\text{sol}[u, \tau_1] \cap \tau_1^{bag}) \cup (\text{sol}[u_2, \tau_2] \cap \tau_2^{bag}) = \tau^{bag}$.

Consider $y \in (V(G_{\le v}) \setminus X_v) \cup \tau^{cov}$. If $y \in (V(G_{\le u_1}) \setminus X_{u_1}) \cup \tau_1^{cov})$, then $y$ is covered by a pair of vertices $y_1$ and $y_2$ in $\text{sol}[u, \tau_1] \cup S_{u_1}^{\tau_1}$. If $y_1, y_2 \in \text{sol}[u_1, \tau_1]$ then $y_1, y_2 \in D$ and we are done. Otherwise, assume without loss of generality that $y_2 \in S_{u_1}^{\tau_1} \setminus S_u^\tau$. There must be a set $A \subseteq X_{u_1}$ such that $\tau_1^{ext}[A] = 1$ and $y_2 = A$. By Definition 5(b), either $\tau^{ext}[A] = 1$ or $\tau_2^{int}[A] = 1$. If the first case is true, then there exists a $y'_2 \in S_v^\tau$ such that $y$ is covered by $y_1$ and $y'_2$ in $G_{\le v}$. If the second case is true, then there is a vertex $y'_2 \in \text{sol}[u_2, \tau_2]$ such that $y'_2$ is close to $A$ with respect to $X_{u_2}$. Due to Lemma 3, we have that $y$ is covered by $y_1$ and $y'_2$. The case where $y \in (V(G_{\le u_2}) \setminus X_{u_2}) \cup \tau_2^{cov})$ is symmetrical. If $y \in \text{Cov}(u_1, u_2)$, by its definition in Definition 5(c) and Lemma 3, $y$ is covered by vertices in $\text{sol}[v, \tau]$. Hence, Definition 2(ii) is satisfied.

By Conditions 5(d) and 5(e) we have that for any $A \subseteq X_v$, $\tau^{int}[A] = 1$ if and only if $\tau_1^{int}[A] = 1$ or $\tau_2^{int}[A] = 1$. Therefore by induction Definition 2(iii) is satisfied. The minimality follows from Lemma 9.

4. When $v$ is the root node, the statement follows easily from Definition 6 and Lemma 10.

This completes the proof. $\square$

## 2.2 The case of interval graphs

When the input graph $G$ is an interval graph, the nice tree decomposition of $G$ does not contain any join nodes. Moreover, the linear structure of interval graphs helps us to reduce the time complexity of the dynamic programming algorithm proposed in the previous section. Essentially, we shall show that the number of different types associated with a node $v$ is at most $O(2^{\omega(G)})$. We shall use the following lemma.

**Lemma 12.** Let $X$ be a clique cutset of an interval graph $G$. There exists a collection $\mathcal{A}$ of subsets of $X$ of size $O(|X|)$ such that for each vertex $v \in V(G)$, if $v$ is close to $A$ with respect to $X$, then $A \in \mathcal{A}$.
Proof. If $v \in X$, then $A = \{v\}$. 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) \le \min(u)$, $d(v, w) \le 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_{u \in X} \{\{w \in X | \min(w) \le \min(u)\}\}$. Hence,

$$A = \bigcup_{u \in X} \{\{w \in X | \min(w) \le \min(u)\}, \{w \in X | \max(w) \ge \max(u)\}, \{u\}\}$$

Observe that $|A|$ is $O(|X|)$. $\square$

<figure><img src="image_4.png" /></figure>

The above lemma implies that for an interval graph, the set of 4-tuples for a node $v$ can be chosen as a subset of $\{0, 1\}^A \times \{0, 1\}^A \times 2^{X_v} \times 2^{X_v}$. Hence, there are $2^{O(\omega)}$ types for an interval graph. This proves the statement of Theorem 1 regarding interval graphs.

# 3 Hardness for interval graphs

We now prove Theorem 2. Let $F$ be an instance of 3-SAT with variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$. We construct a set $D$ of intervals in polynomial time such that the geodetic number of the intersection graph of $D$ (denoted as $\mathcal{I}(D)$) is at most $4 + 7n + 58m$ if and only if $F$ is a positive instance of 3-SAT.

The key intuition that explains why the problem is hard on interval graphs is that considering two solution vertices $x$ and $y$, the structure of the covered set $I(x, y)$ can be very complicated. Indeed, it can be that many vertices lying “in between” $x$ and $y$ in the interval representation, are not covered. This allows us to construct gadgets, by controlling which of these vertices get covered, and which do not. Moreover, we can easily force some vertices to be part of the solution by representing them by an interval of length 0 (then, they are simplicial vertices), which is very useful to design our reduction. Nevertheless, implementing this idea turns out to be far from trivial, and to this end we need the crucial idea of tracks, which are shortest paths spanning a large part of the construction. Each track starts at a key interval called its root (representing a literal, for example) and serves as a shortest path from the root to the rightmost end of the construction. In a way, each track “carries the effect of the root” being chosen in a solution to the rest of the graph. The tracks are shifted in a way that no shortcut can be used going from one track to another. We are then able to locally modify the tracks and place our gadgets so that the track of, say, a literal, enables the interval of that literal to cover an interval of a specific clause gadget (while the other tracks are of no use for this purpose).

## 3.1 Overview of the reduction

There are four main stages of our reduction. Figure 2(a) shows a roadmap of the reduction. We initialise it by constructing a set of intervals which we call the start gadget (denoted as $\mathcal{S}$).

After creating the start gadget, we create the variable gadgets, which are placed consecutively, after the start gadget. For each variable $x_i$, with $1 \le i \le n$, we create the variable gadget $\mathcal{X}_i$. Each variable gadget is composed of several implication gadgets. An implication gadget $IMP[\neg p \to q]$ ensures that if $p$ is not
<figure><img src="image_5.png" /><figcaption>Figure 2: Overview of the reduction. (a) Roadmap of the reduction procedure for proving Theorem 2. (b) An illustration of the arrangements of the gadgets are shown. The box with label $\mathcal{S}$ represents the start gadget, the box labelled $\mathcal{E}$ represents the end gadget. A box labelled $\mathcal{C}_i$ represents the gadget for clause $C_i$ and a box labelled $\mathcal{X}_j$, the gadget for variable $x_j$. Lines between such gadgets represent the tracks.</figcaption></figure>

chosen in a geodetic set of our constructed intervals, then **q** must be chosen. These are used to encode the behaviour of the variables of the 3-SAT instance: there will be two possible solutions, corresponding to both truth values of $x_i$.

After creating all the variable gadgets, we create the clause gadgets, also placed consecutively, after the variable gadgets. For each clause $C_j$ with $1 \le j \le m$, we construct the clause gadget $\mathcal{C}_j$. Each clause gadget is composed of a *covering gadget*, several implication gadgets, and several *AND gadgets*. The covering gadget of a clause $C_i$ is denoted by $\text{COV}[i]$. For two intervals **p** and **q**, the corresponding AND gadget is denoted by $\text{AND}[\mathbf{p}, \mathbf{q}]$. Together, these gadgets will ensure that all intervals of the clause gadget corresponding to the clause $C_i$ are covered by six intervals if and only if one of the intervals corresponding to the literals of $C_i$ is chosen in a geodetic set. This encodes the behaviour of the clauses of the 3-SAT instance.

After creating all the clause gadgets, we conclude our construction by creating the *end gadget* $\mathcal{E}$, placed after all clause gadgets. Figure 2(b) shows the arrangement of the gadgets in the reduction.

**Organisation of this section:** In Subsection 3.2, we introduce some notations to use them in the description of the reduction. In Subsection 3.3, we describe the construction of the start gadget. In Subsection 3.4, we describe a generic construction of the implication gadget $IMP[\neg \mathbf{p} \to \mathbf{q}]$. In Subsection 3.5, we describe a generic construction of the cover gadget $\text{COV}[i]$. In Subsection 3.6, we describe a generic construction of the insert gadget $\text{INS}[\mathbf{p}, \mathbf{q}]$. In Subsection 3.7, we describe a generic construction of the AND-gadget AND $[\mathbf{p}, \mathbf{q}]$. Then, in Subsection 3.8, we describe the construction of the variable gadget. In Subsection 3.9,
<figure><img src="image_6.png" /><figcaption>Figure 3: The start gadget $\mathcal{S}$. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.</figcaption></figure>

we describe the construction of the clause gadget. In Subsection 3.10, we describe the construction of the end gadget.

## 3.2 Notations

We shall use the following notations. Let $S$ be a set of intervals. For a vertex $v \in V(\mathcal{I}(S))$, the corresponding interval will be denoted by $v$. The notations $min(v)$, $max(v)$ shall denote the left boundary and right boundary of $v$, respectively. The rightmost neighbour of an interval $v$ is the interval intersecting $v$ that has the maximum right boundary. For a set $S$ of intervals, let $min(S) = min\{min(v): v \in S\}$, $max(S) = max\{max(v): v \in S\}$. For two intervals $u, v$ we have $u < v$ if $max(u) < min(v)$.

Let $S$ be a set of intervals and $u, v \in S$. A shortest path between $u, v$ is a shortest path between $u, v$ in $\mathcal{I}(S)$. The set $\mathcal{I}(u, v)$ is the set of intervals that belongs to some shortest path between $u, v$. The geodetic set of $S$ is analogously defined. For a set of intervals $S$, the phrase “$S$ is covered by $S'$” means that $S'$ is a geodetic set of $S$.

A point interval is an interval of the form $[a, a]$. A unit interval is an interval of the form $[a, a + 1]$. A set of intervals is proper if no two intervals contain each other. A set $T = \{u_1, u_2, \dots, u_t\}$ of intervals is a track if $max(u_i) = \min(u_{i+1})$ for all $1 \le i < t$. Observe that if $T$ is a track, then $\mathcal{I}(T)$ is a path. In our construction, each track $T$ will be associated with a set of intervals called its *roots*, denoted by $R(T)$. Sometimes we shall use the sentence “root $v$ of a track $T$” to say $v \in R(T)$.

**Definition 7.** Let $T$ and $T'$ be two tracks such that $T \cup T'$ is a proper set of intervals. Then, $T < T'$ if $max(T) < max(T')$.

Let $\mathcal{T}$ be a set of tracks and $T \in \mathcal{T}$. The phrase “the track just preceding $T$” shall refer to the track $T'$ such that $T' < T$ and there is no $T''$ such that $T' < T'' < T$. The phrases “the track just following $T$”, “maximal track of $\mathcal{T}$” and “minimal track of $\mathcal{T}$” are analogously defined.

## 3.3 Initiation and construction of start gadget $\mathcal{S}$

Let $F$ be an instance of 3-SAT with variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$. Let $\epsilon = \frac{1}{(n+m)^4}$. The start gadget $\mathcal{S}$ consists of four intervals which are defined as follows: the start interval $o = [1, 1]$, $u_o = [1, 2]$, the true interval $\top = [1 + \epsilon, 1 + \epsilon]$ and $u_\top = [1 + \epsilon, 2 + \epsilon]$. Let $T_1 = \{u_o\}$ and $T_2 = \{u_\top\}$. Observe that $T_1, T_2$ are tracks and $T_1 < T_2$.

We initialize two more sets, the set $\mathcal{T} = \{T_1, T_2\}$, and the set $D = \mathcal{S}$. In what follows, $\mathcal{T}$ will contain all constructed tracks and $D$ will contain all constructed intervals. As we proceed with the construction, we shall insert more intervals in $T_1, T_2$ while maintaining that both of them are tracks. We shall also add more tracks in $\mathcal{T}$. Let $R(T_1) = \{o\}$ and $R(T_2) = \{\top\}$. Recall that for a track $T$, $R(T)$ denotes the set of root intervals of $T$.
<figure><img src="image_7.png" /><figcaption>Figure 4: The implication gadget IMP [¬**p** → **q**]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.</figcaption></figure>

## 3.4 Implication gadget of a root p

In order to construct the variable gadgets and the clause gadgets, we need to define the implication gadget. Below we describe a generic procedure to construct implication gadgets of a root **p** which is different from **o** of *S*. Let $T_p \in \mathcal{T}$ be the track such that **p** $\in R(T_p)$. Since $**p** \neq **o**$, $T_p$ is not the minimal element in $\mathcal{T}$. Below we describe the three steps for constructing IMP [¬**p** → **q**]. See Figure 4 for a graphical representation of the intervals.

1. **Extension of existing tracks:** For each track $T \in \mathcal{T}$, introduce three new intervals $u_T = [max(T), max(T) + 1]$, $v_T = [max(T) + 1, max(T) + 2]$ and $w_T = [max(T) + 2, max(T) + 3]$. Let $T_{new} = \{u_T, v_T, w_T\}$. Observe that, for two tracks $T, T' \in \mathcal{T}$ with $T < T'$, we have $(T \cup T_{new}) < (T' \cup T'_{new})$.

2. **Creation of new intervals:** Let $X$ and $X'$ be the tracks that precede and follow $T_p$ in $\mathcal{T}$, respectively. Note that $X$ always exists since $p \neq o$. When $X'$ exists, let $\theta = max(u_{X'})$ and $\theta' = max(v_{X'})$. Otherwise, $\theta = max(u_{T_p}) + \epsilon$ and $\theta' = max(v_{T_p}) + \epsilon$.

$$ \text{Define } \mathbf{q} = \left[ \frac{\max(u_{\mathbf{x}})+\max(u_{T_p})}{2}, \frac{\max(u_{T_p})+\theta}{2} \right], \quad \mathbf{r}_q = \left[ \max(\mathbf{q}), \frac{\max(v_{T_p})+\theta'}{2} \right] \text{ and } \mathbf{s}_q = [\max(\mathbf{r}_q), \max(\mathbf{r}_q)]. $$

3. **Creation of new tracks:** In this step, we shall create two new tracks. We define three more intervals as follows: $t = [max(s_q), max(s_q) + 1]$, $t_1 = [max(q), \frac{max(v_{T_p}) + min(s_q)}{2}]$ and $t_2 = [max(t_1), max(t_1) + 1]$. Now, let $T_1 = \{t_1, t_2\}$, $R(T_1) = \{q\}$, $T_2 = \{t\}$ and $R(T_2) = \{r_q, s_q\}$.

To complete the construction of the implication gadget, we define IMP [¬**p** → **q**] = {**q**, $r_q$, $s_q$} $\cup$ $T_1 \cup T_2 \cup \bigcup_{T \in \mathcal{T}} \{u_T, v_T, w_T\}$. Let $D = D \cup IMP [\neg p \rightarrow q]$. For each $T \in \mathcal{T}$, let $T = T \cup T_{new}$ and $\mathcal{T} = \mathcal{T} \cup \{T_1, T_2\}$. Observe that the intersection graph of $D$ does not contain $K_{1,5}$ as induced subgraph.

## 3.5 Construction of covering gadgets

Below we describe the three steps for constructing the covering gadget of the clause $C_i$. See Figure 5.
<figure><img src="image_8.png" /><figcaption>Figure 5: The covering gadget COV[i]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.</figcaption></figure>

1. **Extension of existing tracks:** For each track $T \in \mathcal{T}$, introduce three new intervals $\mathbf{u}_T^i = [\max(T), \max(T) + 1]$, $\mathbf{v}_T^i = [\max(T) + 1, \max(T) + 2]$ and $\mathbf{w}_T^i = [\max(T) + 2, \max(T) + 3]$. Let $T_{new} = \{\mathbf{u}_T^i, \mathbf{v}_T^i, \mathbf{w}_T^i\}$. Observe that, for two tracks $T, T' \in \mathcal{T}$ with $T < T'$, we have $(T \cup T_{new}) < (T' \cup T'_{new})$.

2. **Creation of new intervals:** Let $T$ be the maximal track in $\mathcal{T}$. Let $\theta = \min(\mathbf{u}_T^i) + \epsilon$. We define $\mathbf{a}_i = [\theta, \theta + \epsilon]$, $\mathbf{b}_i = [\theta, \theta + 2\epsilon]$, $\mathbf{c}_i = [\theta, \theta + 3\epsilon]$ and $\mathbf{d}_i = [\theta, \theta]$. Also define $\mathbf{cov}_i = [\max(\mathbf{v}_T^i) + 4\epsilon, \max(\mathbf{v}_T^i) + 7\epsilon]$, and $\mathbf{f}_i = [\max(\mathbf{cov}_i), \max(\mathbf{cov}_i)]$.

3. **Creation of new tracks:** Now we create five more tracks as follows. Let $T_{a_i} = \{[\max(\mathbf{a}_i) + k, \max(\mathbf{a}_i) + k + 1] \mid k \in \{0, 1, 2\}\}$, $T_{b_i} = \{[\max(\mathbf{b}_i) + k, \max(\mathbf{b}_i) + k + 1] \mid k \in \{0, 1, 2\}\}$ and $T_{c_i} = \{[\max(\mathbf{c}_i) + k, \max(\mathbf{c}_i) + k + 1] \mid k \in \{0, 1, 2\}\}$. Observe that $T_{a_i}, T_{b_i}, T_{c_i}$ are tracks and define $R(T_{a_i}) = \{\mathbf{a}_i\}, R(T_{b_i}) = \{\mathbf{b}_i\}$ and $R(T_{c_i}) = \{\mathbf{c}_i\}$.

Also, define $T_{d_i} = \{[\max(\mathbf{d}_i) + k, \max(\mathbf{d}_i) + k + 1] \mid k \in \{0, 1, 2\}\}$ where $R(T_{d_i}) = \{\mathbf{d}_i\}$ and $T_{f_i} = \{[\max(\mathbf{f}_i), \max(\mathbf{f}_i) + 1]\}$ where $R(T_{f_i}) = \{\mathbf{cov}_i, \mathbf{f}_i\}$.

To complete the construction of the covering gadget of $C_i$, we define $\text{COV}[i] = \{\mathbf{a}_i, \mathbf{b}_i, \mathbf{c}_i, \mathbf{cov}_i, \mathbf{d}_i, \mathbf{f}_i\} \cup \{\mathbf{u}_T^i, \mathbf{v}_T^i, \mathbf{w}_T^i\}_{T \in \mathcal{T}} \cup \left( \bigcup_{y \in \{a,b,c,d,f\}} T_{y_i} \right)$. For each $T \in \mathcal{T}$, let $T = T \cup T_{new}$ and $\mathcal{T} = \mathcal{T} \cup \{T_{a_i}, T_{b_i}, T_{c_i}, T_{d_i}, T_{f_i}\}$. We set $D = D \cup \text{COV}[i]$. Observe that the intersection graph of $D$ does not contain $K_{1,5}$ as induced subgraph.

## 3.6 Construction of the insert gadget

Let $T_p$ and $T_q$ be two tracks of $\mathcal{T}$ with roots $p$ and $q$, respectively. Without loss of generality, assume that $T_p < T_q$. Below we describe the three steps for constructing the insert gadget INS[$p, q$]. See Figure 6.

1. **Extension of existing tracks:** For each track $T \in \mathcal{T}$, we introduce one new interval $\mathbf{u}_T = [\max(T), \max(T) + 1]$. Let $T_{new} = \{\mathbf{u}_T\}$. Observe that, for two tracks $T, T' \in \mathcal{T}$ with $T < T'$, we have $(T \cup T_{new}) < (T' \cup T'_{new})$.
<figure><img src="image_9.png" /><figcaption>Figure 6: The insert gadget INS $[\mathbf{p}, \mathbf{q}]$. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.</figcaption></figure>

2. **Creation of a new interval:** Let $X$ be the track that just follows $T_p$ in $\mathcal{T}$. Observe that $X$ always exists. Let $\sigma(\mathbf{p}, \mathbf{q}) = \left[ \frac{\max(\mathbf{u}_{T_p})+\max(\mathbf{u}_X)}{2}, \frac{\max(\mathbf{u}_{T_p})+\max(\mathbf{u}_X)}{2} \right]$.

3. **Creation of a new track:** Let $T_m = \{[\max(\sigma(\mathbf{p}, \mathbf{q})), \max(\sigma(\mathbf{p}, \mathbf{q})) + 1]\}$ and $R(T_m) = \{\sigma(\mathbf{p}, \mathbf{q})\}$.

To complete the construction, we define INS $[\mathbf{p}, \mathbf{q}] = \{\sigma(\mathbf{p}, \mathbf{q})\} \cup \{\mathbf{u}_T, v_T\}_{T \in \mathcal{T}} \cup T_m$. We set $D = T_m \cup \text{INS}[\mathbf{p}, \mathbf{q}]$. For each $T \in \mathcal{T}$, let $T = T \cup T_{\text{new}}$ and $\mathcal{T} = \mathcal{T} \cup \{T_m\}$. Observe that $T_p < T_m < T_q$ in $\mathcal{T}$. Moreover, observe that the intersection graph of $D$ does not contain $K_{1,5}$ as induced subgraph.

## 3.7 Construction of AND gadgets

Let $T_p$ and $T_q$ be two tracks of $\mathcal{T}$ with roots $\mathbf{p}$ and $\mathbf{q}$, respectively. Without loss of generality, assume that $T_p < T_q$. Below we describe the four steps of constructing AND $[\mathbf{p}, \mathbf{q}]$. See Figure 7.

1. **Creation of insert gadget:** Create an insert gadget INS $[\mathbf{p}, \mathbf{q}]$. Recall that the interval named $\sigma(\mathbf{p}, \mathbf{q})$ exists and it is the root of track, say, $T_m$.

2. **Extension of existing tracks:** For each track $T \in \mathcal{T}$, introduce two new intervals $\mathbf{u}_T = [\max(T), \max(T) + 1]$ and $v_T = [\max(T) + 1, \max(T) + 2]$. Let $T_{\text{new}} = \{\mathbf{u}_T, v_T\}$. Observe that, for two tracks $T, T' \in \mathcal{T}$ with $T < T'$, we have $(T \cup T_{\text{new}}) < (T' \cup T'_{\text{new}})$.

3. **Creation of new intervals:** Let $Y_1$ be the track just preceding $T_p$. Recall that $T_m$ is the track just following $T_p$. Define $\alpha(\mathbf{p}, \mathbf{q}) = \left[ \frac{\max(\mathbf{u}_{Y_1})+\max(\mathbf{u}_{T_p})}{2}, \frac{\max(\mathbf{u}_{T_p})+\max(\mathbf{u}_{T_m})}{2} \right]$ and $\beta(\mathbf{p}, \mathbf{q}) = \left[ \frac{\max(\mathbf{u}_{T_p})+\max(\alpha(\mathbf{p}, \mathbf{q}))}{2}, \frac{\max(\mathbf{u}_{T_p})+\max(\alpha(\mathbf{p}, \mathbf{q}))}{2} \right]$.

Let $Y_2$ be the track just preceding $T_q$ in $\mathcal{T}$. Observe that either $Y_2 = T_m$ or $T_m < Y_2 < T_q$. Now define $\gamma(\mathbf{p}, \mathbf{q}) = [\max(\alpha(\mathbf{p}, \mathbf{q})), \frac{\max(\mathbf{u}_{Y_2})+\max(\mathbf{u}_{T_q})}{2}]$. Let $Y'_2$ be the track just following $T_q$ in $\mathcal{T}$. We define $h = \max(\mathbf{u}_{Y'_2})$ if $Y'_2$ exists and $h = \max(\mathbf{u}_{T_q}) + \epsilon$ otherwise. Now we define $\delta(\mathbf{p}, \mathbf{q}) = [\max(\gamma(\mathbf{p}, \mathbf{q})), \frac{\max(\mathbf{u}_{T_q})+h}{2}]$.

4. **Creation of new tracks:** We create $T_1 = \{[\max(\beta(\mathbf{p}, \mathbf{q})), \max(\beta(\mathbf{p}, \mathbf{q}) + 1]\}$ where $R(T_1) = \{\alpha(\mathbf{p}, \mathbf{q}), \beta(\mathbf{p}, \mathbf{q})\}$, $T_2 = \{[\max(\gamma(\mathbf{p}, \mathbf{q})), \max(\gamma(\mathbf{p}, \mathbf{q}) + 1]\}$ where $R(T_2) = \{\gamma(\mathbf{p}, \mathbf{q})\}$ and $T_3 = \{[\delta(\mathbf{p}, \mathbf{q}), \delta(\mathbf{p}, \mathbf{q}) + 1]\}$ where $R(T_3) = \{\delta(\mathbf{p}, \mathbf{q})\}$.
<figure><img src="image_10.png" /><figcaption>Figure 7: The AND gadget AND $[p, q]$. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.</figcaption></figure>

To complete the construction, define AND $[p, q] = \{\alpha(p, q), \beta(p, q), \gamma(p, q), \delta(p, q)\} \cup \{u_T, v_T\}_{T \in \mathcal{T}} \cup \{T_j\}_{1 \le j \le 3}$. For each $T \in \mathcal{T}$, let $T = T \cup T_{new}$. Let $D = D \cup$ AND $[p, q]$ and $\mathcal{T} = \mathcal{T} \cup \{T_1, T_2, T_3\}$. Observe that the intersection graph of $D$ does not contain $K_{1,5}$ as induced subgraph.

## 3.8 Construction of variable gadgets

We construct the variable gadgets sequentially and connect each of them to the previous one ($\mathcal{X}_1$ is connected to the start gadget $\mathcal{S}$). Assuming that we have placed $\mathcal{S}$, $\mathcal{X}_1, \dots, \mathcal{X}_{i-1}$, we construct $\mathcal{X}_i$ as follows. For variable $x_i$, the gadget $\mathcal{X}_i$ consists of two implication gadgets. Let $D$ and $\mathcal{T}$ be the set of intervals and tracks created so far. First, we construct $IMP[\neg T \rightarrow x_i]$. Observe that the sets $D$ and $\mathcal{T}$ have been updated after the last operation. There is an interval $x_i$ in $D$ and there is a track $T \in \mathcal{T}$ whose root is $x_i$. Now we construct $IMP[\neg x_i \rightarrow \bar{x}_i]$. Observe that after constructing all the variable gadgets, for each literal $\ell$, there is an interval named $\ell$ in $D$. See Figure 8 for an illustration of $\mathcal{X}_i$ created corresponding to the variable $x_i$.

## 3.9 Construction of clause gadgets

We shall complete our construction of clause gadget $\mathcal{C}_i$ corresponding to the clause $C_i = (\ell_i^1, \ell_i^2, \ell_i^3)$. First, we create the covering gadget COV[$i$] and update $D, \mathcal{T}$ as described in Section 3.5. Recall from the construction of COV[$i$] that the intervals named $a_i, b_i, c_i$ exist. Also recall from the construction of variable gadgets (described in Section 3.8) that the intervals $\ell_i^1, \ell_i^2, \ell_i^3$ and $\bar{\ell}_i^1, \bar{\ell}_i^2, \bar{\ell}_i^3$ exist. Now we create, in this order, $IMP[\neg a_i \rightarrow a'_i]$, AND $[a_i, \ell_i^1]$, AND $[a'_i, \bar{\ell}_i^1]$, $IMP[\neg b_i \rightarrow b'_i]$, AND $[b_i, \ell_i^2]$, AND $[b'_i, \bar{\ell}_i^2]$, $IMP[\neg c_i \rightarrow c'_i]$, AND $[c_i, \ell_i^3]$, AND $[c'_i, \bar{\ell}_i^3]$ where $a'_i, b'_i$ and $c'_i$ are three new intervals constructed in the
<figure><img src="image_11.png" /><figcaption>Figure 8: The variable gadget $\mathcal{X}_i$ created corresponding to the variable $x_i$. The first implication gadget contains three special intervals named $x_i$, $r_{x_i}$, $s_{x_i}$. The second implication gadget contains three special intervals named $\bar{x}_i$, $r_{\bar{x}_i}$, $s_{\bar{x}_i}$.</figcaption></figure>

corresponding implication gadgets. This completes the construction of $\mathcal{C}_i$. See Figure 9 for an illustration of the clause gadget $\mathcal{C}_i$.

## 3.10 Construction of end gadget

For each $T \in \mathcal{T}$, we introduce two new intervals $u_T = [max(T), max(T) + 1]$, $e_T = [max(u_T), max(u_T)]$ and define $T = T \cup \{u_T\}$, $D = D \cup \{u_T, e_T\}_{T \in \mathcal{T}}$. For each $T \in \mathcal{T}$, let $e_T$ be the tail of $T$. The end gadget $\mathcal{E}$ consists of all the new intervals created above. See Figure 10 for an illustration of all the gadgets created corresponding to the 3-SAT instance $F = (x_1 \lor \bar{x}_2 \lor x_3)$. Observe that the intersection graph of $D$ does not contain $K_{1,5}$ as induced subgraph.

## 3.11 Proofs

In this section, we shall show that the 3-SAT instance is satisfiable if and only if the constructed graph has a geodetic set with a certain cardinality. For the entirety of this section, $F$ shall denote a 3-SAT instance with variables $x_1, x_2, \dots, x_n$ and clauses $C_1, C_2, \dots, C_m$. The set $D$ will denote the set of constructed intervals, $T$ will denote the tracks. For each $i \in [n]$, $\mathcal{X}_i$ shall denote the constructed variable gadget and for each $j \in [m]$, $\mathcal{C}_j$ shall denote the set of constructed gadget. The reader may use Figure 11 to navigate the proof of Theorem 2.

We begin by showing that the number of vertices in the constructed graph is polynomial in the number of variables and clauses, which implies that the construction procedure takes polynomial time.

**Lemma 13.** There are $2 + 4n + 35m$ tracks in $\mathcal{T}$ and $4 + 6n + 52m$ point intervals in $D$. The total number of intervals in $D$ is $O((n+m)^2)$.

*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
<figure><img src="image_12.png" /><figcaption>Figure 9: Illustration of the clause gadget $\mathscr{C}_i$ with literals $\ell_i^1$, $\ell_i^2$, $\ell_i^3$. The names of the special intervals created at each gadget are highlighted above or below the box illustrating the respective gadgets.</figcaption></figure>

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)$. $\square$

In the next few lemmas, we prove that if an induced path of an interval graph has a certain structure, then it is also a shortest path between its end-vertices.

**Lemma 14.** Let $\mathbf{u}$ and $\mathbf{v}$ be two intervals of $D$ such that $\min(\mathbf{u}) < \min(\mathbf{v})$. Let $P = \mathbf{u}_0\mathbf{u}_1\dots\mathbf{u}_k\mathbf{v}$ be an induced path such that $\mathbf{u}_0 = \mathbf{u}$ and $\mathbf{u}_{i+1}$ is the rightmost neighbour of $\mathbf{u}_i$ for $0 \le i \le k-1$, and $\mathbf{u}_{k-1} \notin N(\mathbf{v})$, while $\mathbf{u}_k \in N(\mathbf{v})$. Then, $P$ is a shortest path.

*Proof.* Let $P = \mathbf{u}_0\mathbf{u}_1\dots\mathbf{u}_k\mathbf{v}$ and $P'$ be a shortest path from $\mathbf{u}$ to $\mathbf{v}$ which starts by the longest common subpath with $P$. Hence $P' = \mathbf{u}_0\mathbf{u}_1\dots\mathbf{u}_i\mathbf{z}\dots\mathbf{v}$ with $\mathbf{z} \notin P$. If $i = k$ then $P$ and $P'$ have the same length. Otherwise, replace $\mathbf{z}$ in $P'$ by $\mathbf{u}_{i+1}$ to obtain a path $P''$. It is indeed a path as $\max(\mathbf{z}) < \max(\mathbf{u}_{i+1})$. Moreover $P'$ and $P''$ have the same length, a contradiction with the definition of $P'$. $\square$

**Definition 8.** Let $P = \mathbf{u}_1\dots\mathbf{u}_k$ be a path such that $\mathbf{u}_{i+1}$ is the rightmost neighbour of $\mathbf{u}_i$ for all $i \in 1 \le i \le k-2$ and $\mathbf{u}_{k-2}$ is not adjacent to $\mathbf{u}_k$. The path $P$ is a shortest path between $\mathbf{u}_1$ and $\mathbf{u}_k$ by Lemma 14. We say that such a path is a "good shortest path".

**Definition 9.** Let $\mathbf{u}, \mathbf{v}, \mathbf{w}$ be three intervals of $D$ such that $\max(\mathbf{u}) < \min(\mathbf{w})$ and $\mathbf{v} \in I(\mathbf{u}, \mathbf{w})$. A shortest path $P = \mathbf{u}_0\mathbf{u}_1\dots\mathbf{u}_k\mathbf{v}\mathbf{u}_{k+1}\dots\mathbf{w}$ between $\mathbf{u}_0 = \mathbf{u}$ and $\mathbf{w}$ is "semi-good" if for each $0 \le i \le k-1$, $\mathbf{u}_{i+1}$ is the rightmost interval of $\mathbf{u}_i$.
**Lemma 15.** Let $\mathbf{u}, \mathbf{v}, \mathbf{w}$ be two intervals of $D$ such that $\max(\mathbf{u}) < \min(\mathbf{w})$ and $\mathbf{v} \in I(\mathbf{u}, \mathbf{w})$. Then, there exists a semi-good shortest path between $\mathbf{u}$ and $\mathbf{w}$ containing $\mathbf{v}$.

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

In Subsection 3.11.1, we shall show that if the 3-SAT instance is satisfiable, then the constructed interval graph has a geodetic set of certain cardinality. In Section 3.11.2, we shall show that if the constructed interval graph has a geodetic set of certain cardinality, then the 3-SAT instance is satisfiable.

**3.11.1 Satisfiability implies optimality**

Recall that each track $T$ is associated with a set of intervals called its roots, denoted by $R(T)$. Also from our construction, it is clear that an interval is the root of at most one track. Hence we define the following notation: for an interval $z$, let $T(z)$ denote the track $T$ such that $z \in R(T(z))$.

**Lemma 16.** If $T$ is a track in $T$, then $T \subseteq I(o, e_T)$.

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

Observe that both $b_k$ and $a_j$ belong to the end gadget and therefore they are adjacent with $\max(b_k) < \max(a_j)$. From the construction it implies that $\min(b_k) < \min(a_j)$. Since $\max(b_{k-1}) = \min(b_k)$, it follows that $b_{k-1}$ is not adjacent with $a_j$. Hence the path induced by the set $\{o, b_1, \dots, b_k, a_j, 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 $a_i$ and $b_{k-j+i}$ are neighbours. Hence, the path induced by the set $\{o, b_1, \dots, b_{k-j+1}, a_1, \dots, a_j, e_T\}$ induces a shortest path $P'$ from $o$ to $e_T$ such that $V(T) \subseteq V(P')$. Hence, $T \subseteq I(o, e_T)$. $\square$

**Lemma 17.** Consider an implication gadget IMP $[\neg p \to q]$. We have that $q \in I(p, s_q)$ and $r_q \in I(o, s_q)$.

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

Now consider the track $T(o)$. Observe from the construction of IMP $[\neg p \to q]$ that there exists a subset $\{w_1, w_2, \dots, w_t\} \subseteq T(o)$ such that $w_1$ is the rightmost neighbour of $o$, $w_{i+1}$ is the leftmost neighbour of $v_i$ for $1 \le i \le t-1$, $s_q \cap w_{t-1} = \emptyset$, and $s_q \subseteq w_t$. By Lemma 14, the set $\{o, w_1, w_2, \dots, w_{t-1}, w_t, s_q\}$ is a shortest path between $o$ and $s_q$ of length $t+1$. Also observe from the construction that $w_{t-1}$ is adjacent to $r_q$. Hence, the path induced by the set $\{o, w_1, w_2, \dots, w_{t-1}, r_q, s_q\}$ is a shortest path between $o$ and $s_q$. $\square$
**Lemma 18.** Consider the cover gadget COV[i] and let $z \in \{a_i, b_i, c_i\}$. Then, $z \in I(d_i, e_{T(z)})$ and $cov_i \in I(z, f_i)$.

*Proof.* Let $T$ denote the track $T(z)$ and let $T = \{u_1, u_2, \dots, u_k\}$ such that $u_{i+1}$ is the rightmost neighbour of $u_i$ for all $1 \le j \le k-1$. Observe from the construction that the path induced by the set $\{d_i, z, u_1, u_2, \dots, u_k, e_T\}$ is a shortest path between $d_i$ and $e_T$. This proves the first part of the proposition. For the second part, consider the path $P$ induced by the set $\{z, u_1, u_2, cov_i, f_i\}$. Clearly, $P$ is a shortest path between $z$ and $f_i$. □

**Lemma 19.** Consider an AND gadget AND $[p, q]$ and the insert gadget INS $[p, q]$. Let $T_1 = T(\alpha(p, q))$, $T_2 = T(\gamma(p, q))$ and $T_3 = T(\delta(p, q))$. Then

$$ (a) \gamma(p, q) \in I(\sigma(p, q), e_{T_2}), $$

$$ (b) \alpha(p, q) \in I(p, e_{T_1}), \delta(p, q) \in I(q, e_{T_3}), \text{ and} $$

$$ (c) \alpha(p, q) \in I(\beta(p, q), \gamma(p, q)) \text{ and } \delta(p, q) \in I(\gamma(p, q), e_{T_3}). $$

*Proof.* First, we prove (a). Consider the track $T(\sigma(p, q))$. Observe from the construction that $T(\sigma(p, q))$ can be partitioned into two sets $P_a = \{u_1, u_2, \dots, u_j\}$ and $P'_a = \{u_{j+1}, u_{j+2}, \dots, u_k\}$ where $u_1$ is the rightmost neighbour of $\sigma(p, q)$, $u_{i+1}$ is the rightmost neighbour of $u_i$ for all $1 \le i \le k-1$, and $u_j$ is the interval of $T(\sigma(p, q))$ with minimal index which intersects $\gamma(p, q)$. Let $z_a$ be the rightmost neighbour of $u_k$. Observe from the construction $z_a \in \mathcal{E}$ and therefore $e_{T_2}$ is adjacent to $z_a$. Hence, by Lemma 14, the path induced by $Q_a = \{\sigma(p, q)\} \cup P_a \cup P'_a \cup \{z_a, e_{T_2}\}$ is a good shortest path between $\sigma(p, q)$ and $e_{T_2}$. Observe from the construction that $|T_2| = |P'|$. Therefore, the set $Q'_a = \{\sigma(p, q)\} \cup P_a \cup \{\gamma(p, q)\} \cup T_2 \cup \{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 $\sigma(p, q)$ and $e_{T_2}$.

Second, we prove (b). Consider the track $T(p)$. Observe from the construction that $T(p)$ can be partitioned into two sets $P_b = \{v_1, v_2, \dots, v_{j'}\}$ and $P'_b = \{v_{j'+1}, v_{j'+2}, \dots, v_{k'}\}$ where $v_1$ is the rightmost neighbour of $p$, $v_{i+1}$ is the rightmost neighbour of $v_i$ for all $1 \le i \le k' - 1$, and $v_{j'}$ is the interval of $T(p)$ with minimal index which intersects $\alpha(p, q)$. Let $z_b$ be the rightmost neighbour of $v_{k'}$. Observe from the construction $z_b \in \mathcal{E}$ and therefore $e_{T_1}$ is adjacent to $z_b$. Hence, by Lemma 14, the path induced by $Q_b = \{p\} \cup P_b \cup P'_b \cup \{z_b, e_{T_1}\}$ is a good shortest path between $p$ and $e_{T_1}$. Observe from the construction that $|T_1| = |P'_b|$. Therefore, the set $Q'_b = \{p\} \cup P_b \cup \{\alpha(p, q)\} \cup T_1 \cup \{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 $pq$ and $e_{T_1}$. Using similar arguments, we can show that $\delta(p, q) \in I(q, e_{T_3})$.

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

**Lemma 20.** If the 3-SAT instance $F$ is satisfiable then $\mathcal{I}(D)$ has a geodetic set of cardinality $4+7n+58m$.
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: \{x_1, x_2, \dots, x_n\} \to \{1, 0\}$ be a satisfying assignment of $F$. Now, define the following sets. Let $S_1 = \{x_i: \phi(x_i) = 1\} \cup \{\bar{x}_i: \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 \{a_i, \gamma (a'_i, \bar{\ell}_i^1)\}$ and if $\phi(\ell_i^1) = 0$ then put $S_2 = S_2 \cup \{a'_i, \gamma (a_i, \ell_i^1)\}$.

2. If $\phi(\ell_i^2) = 1$, then put $S_2 = S_2 \cup \{b_i, \gamma (b'_i, \bar{\ell}_i^2)\}$ and if $\phi(\ell_i^2) = 0$ then put $S_2 = S_2 \cup \{b'_i, \gamma (b_i, \ell_i^2)\}$.

3. If $\phi(\ell_i^3) = 1$, then put $S_2 = S_2 \cup \{c_i, \gamma (c'_i, \bar{\ell}_i^3)\}$ and if $\phi(\ell_i^3) = 0$ then put $S_2 = S_2 \cup \{c'_i, \gamma (c_i, \ell_i^3)\}$.

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

As $S_p \subseteq S$, observe that $o \in S$ and for each track $T \in \mathcal{T}$, the point interval $e_T \in S$. Hence, due to Lemma 16, we have that each track $T \in \mathcal{T}$ is covered by $S$.

Consider any variable gadget $\mathcal{X}_i$ corresponding to the variable $x_i$. Recall that from the construction, $\mathcal{X}_i = \text{IMP}[\neg T \to x_i] \cup \text{IMP}[\neg x_i \to \bar{x}_i]$. Due to Lemma 17, we have that $x_i \in I(T, s_{x_i})$ and $r_{x_i} \in I(o, s_{x_i})$. Hence, $\text{IMP}[\neg T \to x_i] \subseteq I(S)$. Now, consider the implication gadget $\text{IMP}[\neg x_i \to \bar{x}_i]$. Due to Lemma 17, we have that $r_{\bar{x}_i} \in I(o, s_{\bar{x}_i})$. Since $\phi$ is a satisfying assignment, then either $\bar{x}_i \in S$ or $x_i \in S$. In the latter case, due to Lemma 17, $r_{\bar{x}_i} \in I(x_i, s_{\bar{x}_i})$. Hence, $\text{IMP}[\neg x_i \to \bar{x}_i] \subseteq S$, and therefore $\mathcal{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 $\mathcal{C}_i$. Since $\phi$ is a satisfying assignment, observe that, there exists at least one interval $z \in \{a_i, b_i, c_i\} \cap S$. Now due to Lemma 18, $z \in I(d_i, e_T(z))$ and $\text{cov}_i \in I(z, f_i)$. Hence $\text{COV}[i] \subseteq I(S)$. Now, consider the implication gadget $\text{IMP}[\neg a_i \to a'_i]$. From our definition of $S_2$, it follows that $\{a_i, a'_i\} \cap S \neq \emptyset$. Now due to Lemma 17, $a'_i \in I(S)$ and $r_{a'_i} \in I(S)$. Hence, $\text{IMP}[\neg a_i \to a'_i] \subseteq I(S)$. Repeating the above arguments for $\text{IMP}[\neg b_i \to b'_i]$ and $\text{IMP}[\neg c_i \to c'_i]$, we infer that

$$ \text{IMP}[\neg a_i \to a'_i] \cup \text{IMP}[\neg b_i \to b'_i] \cup \text{IMP}[\neg c_i \to c'_i] \subseteq I(S) $$

Now, consider the AND gadgets AND $[a_i, \ell_i^1]$ and AND $[a'_i, \bar{\ell}_i^1]$. From our definition of $S_2$, it follows that either $\{a_i, \gamma (a'_i, \bar{\ell}_i^1)\} \subseteq S$ or $\{a'_i, \gamma (a_i, \ell_i^1)\} \subseteq S$. First consider the case when $\{a_i, \gamma (a'_i, \bar{\ell}_i^1)\} \subseteq S$. This means $\phi(\ell_i^1) = 1$ and therefore $\ell_i^1 \in S$. Now invoking Lemma 19(a) and (b) (with $p = a_i$ and $q = \ell_i^1$), we have that AND $[a_i, \ell_i^1] \subseteq I(S)$. Also, invoking Lemma 19(a) and (c) ($p = a'_i$ and $q = \bar{\ell}_i^1$) we have that AND $[a'_i, \bar{\ell}_i^1] \subseteq I(S)$. The above arguments imply that when $\{a_i, \gamma (a'_i, \bar{\ell}_i^1)\} \subseteq S$, we have

$$ \text{AND } [a_i, \ell_i^1] \cup \text{AND } [a'_i, \bar{\ell}_i^1] \subseteq I(S) $$

Similarly when $\{a'_i, \gamma (a_i, \ell_i^1)\} \subseteq S$ using similar arguments we have $(\text{AND } [a_i, \ell_i^1] \cup \text{AND } [a'_i, \bar{\ell}_i^1]) \subseteq I(S)$. Now arguing similarly for $(\text{AND } [b_i, \ell_i^2] \cup \text{AND } [b'_i, \bar{\ell}_i^2])$ and $(\text{AND } [c_i, \ell_i^3] \cup \text{AND } [c'_i, \bar{\ell}_i^3])$, we have that $\mathcal{C}_i \subseteq I(S)$. This completes the proof. $\square$
### 3.11.2 Optimality implies satisfiability

Now, we shall show that if the geodetic number of $D$ is at most $4 + 7n + 58m$, then $F$ is satisfiable.

**Lemma 21.** Let $S$ be a geodetic set of $D$. There exists a geodetic set $S^*$ of $D$ with $|S^*| \le |S|$ such that for any track $T \in \mathcal{T}$ we have $S \cap T = \emptyset$.

*Proof.* Let $U$ consists of all intervals contained in some track. In other words, $U = \bigcup_{T \in \mathcal{T}} T$. Let $S_p$ denote the set of point intervals in $D$. Observe that $S_p \subseteq S$. Let $u \in S \cap U$ be the interval with $\min(S \cap U) = \min(u)$ such that $u$ belongs to a track with a root $y$. Let $A_1$ and $A_2$ be the sets of all $\gamma(p, q)$ intervals and $r_q$ intervals in $D$, respectively. Let $A_3 = \{z \in D: z \in \{a_i, b_i, c_i\}, 1 \le i \le m\}$ and $A = A_1 \cup A_2 \cup A_3$ and $\bar{A} = D \setminus (A \cup U \cup S_p)$. Due to Lemma 16, 17, 18, and 19, observe that, $A \cup U \subseteq I(S_p)$. Therefore, we will be done by proving the following claim.

**Claim 22.** Let $v$ be any interval in $S$. We have $I(u, v) \cap \bar{A} \subseteq I(y, v) \cap \bar{A}$.

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

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

2. Assume $z = cov_i$ for some $1 \le i \le m$. Using similar arguments as above and Lemma 18, we can show that $v \in \{a_i, b_i, c_i\}$ and therefore $z \in I(v, f_i)$.

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

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

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

A good geodetic set of $D$ is a geodetic set of minimum cardinality which does not contain any interval belonging to a track. By Lemma 21, a good geodetic set of $D$ always exists. Now we shall prove some further properties of good geodetic sets of $D$.

**Lemma 23.** Let $S^*$ be a good geodetic set of $D$ and $IMP[\neg p \to q]$ be an implication gadget where $p$ is the only root of $T(p)$. Then, either $p \in S^*$ or $q \in S^*$.

*Proof.* Suppose $q \notin S^*$. Then, Lemma 15 implies that there exists a semi-good shortest path $P$ containing $q$ whose end-vertices lie in $S^*$. Then, there must exist two intervals $u_1, v_1$ in $P$ such that both $u_1, v_1$ intersect $q$ and $\max(u_1) < \min(v_1)$. From the construction of $IMP[\neg p \to q]$, it follows that $u_1 \in T(p)$. Since $S^*$ is a good geodetic set, our construction implies that $p \in S^*$. $\square$
**Lemma 24.** Let $S^*$ be a good geodetic set of D and AND $[\mathbf{p}, \mathbf{q}]$ be an AND gadget where $\mathbf{p}$ is the only root of $T(\mathbf{p})$ and $\mathbf{q}$ is the only root of $T(\mathbf{q})$. Then, either $\{\mathbf{p}, \mathbf{q}\} \subseteq S^*$, or $S^*$ contains at least one interval among $\{\alpha(\mathbf{p}, \mathbf{q}), \gamma(\mathbf{p}, \mathbf{q}), \delta(\mathbf{p}, \mathbf{q})\}$.

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

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

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

**Lemma 25.** Let $S^*$ be a good geodetic set of D and let $C_i = (\ell_i^1, \ell_i^2, \ell_i^3)$ be a clause. Then we have

$$ (a) \left| S^* \cap \left\{ a_i, a_i', \alpha(a_i, \ell_i^1), \gamma(a_i, \ell_i^1), \delta(a_i, \ell_i^1), \alpha(a_i', \bar{\ell}_i^1), \gamma(a_i', \bar{\ell}_i^1), \delta(a_i', \bar{\ell}_i^1) \right\} \right| \ge 2, $$

$$ (b) \left| S^* \cap \left\{ b_i, b_i', \alpha(b_i, \ell_i^2), \gamma(b_i, \ell_i^2), \delta(b_i, \ell_i^2), \alpha(b_i', \bar{\ell}_i^2), \gamma(b_i', \bar{\ell}_i^2), \delta(b_i', \bar{\ell}_i^2) \right\} \right| \ge 2, \text{ and} $$

$$ (c) \left| S^* \cap \left\{ c_i, c_i', \alpha(c_i, \ell_i^3), \gamma(c_i, \ell_i^3), \delta(c_i, \ell_i^3), \alpha(c_i', \bar{\ell}_i^3), \gamma(c_i', \bar{\ell}_i^3), \delta(c_i', \bar{\ell}_i^3) \right\} \right| \ge 2. $$

*Proof.* Recall that $C_i$ contains the gadgets AND $[a_i, \ell_i^1]$ and AND $[a_i', \bar{\ell}_i^1]$ (along with some other gadgets). By Lemma 24, if $a_i \notin S^*$ then we need at least one vertex among $\alpha(a_i, \ell_i^1), \gamma(a_i, \ell_i^1), \delta(a_i, \ell_i^1)$. The same holds when $a_i \notin S^*$, we need at least one among $\alpha(a_i', \bar{\ell}_i^1), \gamma(a_i', \bar{\ell}_i^1), \delta(a_i', \bar{\ell}_i^1)$. This implies that (a) holds. Using analogous arguments we can show that (b) and (c) holds. $\square$

**Lemma 26.** Let $S^*$ be a good geodetic set of D and $C_i = (\ell_i^1, \ell_i^2, \ell_i^3)$ be a clause. If none of $\ell_1^i, \ell_2^i, \ell_3^i$ is in $S^*$ then $|S^* \cap C_i| \ge 7$.

*Proof.* Assume none of $\ell_1^i, \ell_2^i, \ell_3^i$ is in $S^*$. Since $\ell_i^1 \notin S^*$, due to Lemma 24, we have that at least one among $\alpha(a_i, \ell_i^1), \gamma(a_i, \ell_i^1), \delta(a_i, \ell_i^1)$ lies in $S^*$. If $a_i' \notin S^*$, then $a_i \in S^*$ and one more interval from $\alpha(a_i', \bar{\ell}_i^1), \gamma(a_i', \bar{\ell}_i^1), \delta(a_i', \bar{\ell}_i^1)$ lies in $S^*$ (Lemma 23 and 24). Therefore,

$$ \left| S^* \cap \left\{ a_i, a_i', \alpha(a_i, \ell_i^1), \gamma(a_i, \ell_i^1), \delta(a_i, \ell_i^1), \alpha(a_i', \bar{\ell}_i^1), \gamma(a_i', \bar{\ell}_i^1), \delta(a_i', \bar{\ell}_i^1) \right\} \right| \ge 3 $$

Now, using Lemma 25, we also have

$$ \left| S^* \cap \left\{ b_i, b_i', \alpha(b_i, \ell_i^2), \gamma(b_i, \ell_i^2), \delta(b_i, \ell_i^2), \alpha(b_i', \bar{\ell}_i^2), \gamma(b_i', \bar{\ell}_i^2), \delta(b_i', \bar{\ell}_i^2) \right\} \right| \ge 2 $$

and

$$ \left| S^* \cap \left\{ c_i, c_i', \alpha(c_i, \ell_i^3), \gamma(c_i, \ell_i^3), \delta(c_i, \ell_i^3), \alpha(c_i', \bar{\ell}_i^3), \gamma(c_i', \bar{\ell}_i^3), \delta(c_i', \bar{\ell}_i^3) \right\} \right| \ge 2 $$
The above arguments imply that when $a'_i \notin S^*$, $|S^* \cap \mathscr{C}_i| \ge 7$. Arguing similarly as above, we can show that if at least one of $b'_i, c'_i$ does not belong to $S^*$, then also $|S^* \cap \mathscr{C}_i| \ge 7$. Now consider the case, when $\{a'_i, b'_i, c'_i\} \subset S^*$. Moreover, $S^*$ contains one interval from each of AND $[a_i, \ell_i^1]$, AND $[b_i, \ell_i^2]$ and AND $[c_i, \ell_i^3]$. Now, we will be done by showing that at least one of $a_i, b_i, c_i, \text{cov}_i$ must be in $S^*$.

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

**Lemma 27.** If there is a geodetic set of $D$ with cardinality $4 + 7n + 58m$, then $F$ is satisfiable.

*Proof.* Let $S$ be a geodetic set of $D$ with cardinality $4 + 7n + 58m$. Due to Lemma 21, there exists a good geodetic set $S^*$ of $D$ with $|S^*| \le |S| \le 4 + 7n + 58m$. Recall that a variable gadget $\mathscr{X}_i = \text{IMP} [\neg \top \to x_i] \cup \text{IMP} [\neg x_i \to \bar{x}_i]$. Due to Lemma 23, we know that at least one among $\{x_i, \bar{x}_i\}$ lies in $S^*$. Let $S_1 = S^* \cap \left( \bigcup_{1 \le i \le n} \mathscr{X}_i \right)$, and $S_2 = S^* \cap \left( \bigcup_{1 \le i \le 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| \ge n$, $|S_2| \ge 6m$ by Lemma 25, and $|S_p| = 4 + 6n + 52m$. Therefore, $|S_1| = n$ as $|S^*| \le 4 + 7n + 58m$. This means that for each $1 \le i \le n$, exactly one of $x_i, \bar{x}_i$ lies in $S^*$. Based on these, we define the following truth assignment $\phi$: $\{x_1, \dots, x_n\} \to \{1, 0\}$ of $F$. Define $\phi(x_i) = 1$ if $x_i \in S^*$ and $\phi(x_i) = 0$, otherwise. Using Lemma 25 we can infer that for each $1 \le i \le m$, we have that $|S^* \cap \mathscr{C}_i| = 6$. Due to Lemma 26, at least one of the intervals $\ell_1^i, \ell_2^i, \ell_3^i$ lies in $S^*$. Thus, for at least one literal $\ell_i^j$, we have that $\phi(\ell_i^j) = 1$, as needed. $\square$

### 3.11.3 Completion of Proof of Theorem 2

Lemma 13, 20, and 27 completes the proof of Theorem 2.

## 4 Conclusion

We proved that MINIMUM GEODETIC SET is FPT on chordal graphs when parameterized by the clique number/treewidth, and that MINIMUM GEODETIC SET is NP-hard on interval graphs.

An interesting question is whether there are FPT algorithms for MINIMUM GEODETIC SET on interval or chordal graphs, when parameterized by the geodetic number? Are there constant-factor approximation algorithms for these classes? (These are not true for general graphs, see [20] and [7].)

Assuming the *Exponential Time Hypothesis*, our reduction implies that there cannot be a $2^{o(\sqrt{n})}$ time algorithm for MINIMUM GEODETIC SET on interval graphs of order $n$. Are there subexponential time algorithms for MINIMUM GEODETIC SET on interval graphs or chordal graphs, matching this lower bound? (This is the case for many graph problems for geometric intersection graphs, see [4].)

We have seen that for every $k$, MINIMUM GEODETIC SET is solvable in time $f(k)n$ for $k$-trees (which are chordal graphs with clique number $k+1$), but such a running time is unlikely to be possible for partial $k$-trees (i.e. graphs of treewidth $k$), since MINIMUM GEODETIC SET is known to be W[1]-hard for parameter treewidth [20]. However, there could still exist an XP-time algorithm for MINIMUM GEODETIC SET, running in time $n^{g(k)}$ on partial $k$-trees. In fact, it is unknown whether MINIMUM GEODETIC SET is solvable in
polynomial time on partial 2-trees (also known as graphs of treewidth at most 2, series-parallel graphs, and $K_4$-minor-free graphs).

Finally, we think that studying the computational complexities of related problems like ISOMETRIC PATH COVER [8], STRONG GEODETIC SET [22], GEODETIC HULL [18] on interval graphs is another interesting direction of research.

**Conflict of Interest:** The authors declare that there is no conflict of interest.

## References

[1] J. Ahn, L. Jaffke, O. Kwon, and P. T. Lima. Well-partitioned chordal graphs. *Discrete Mathematics*, 345(10):112985, 2022.

[2] B. Allgeier. *Structure and properties of maximal outerplanar graphs*. PhD thesis, University of Louisville, 2009.

[3] R. Belmonte, P. A. Golovach, P. Heggernes, P. van't Hof, M. Kamiński, and D. Paulusma. Detecting fixed patterns in chordal graphs in polynomial time. *Algorithmica*, 69:501–521, 2014.

[4] É. Bonnet and P. Rzążewski. Optimality program in segment and string graphs. *Algorithmica*, 81(7):3047–3073, 2019.

[5] L. R. Bueno, L. D. Penso, F. Protti, V. R. Ramos, D. Rautenbach, and U. S. Souza. On the hardness of finding the geodetic number of a subcubic graph. *Information Processing Letters*, 135:22–27, 2018.

[6] D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic Sets on planar and chordal graphs. In *31st International Symposium on Algorithms and Computation (ISAAC 2020)*, volume 181 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 7:1–7:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.

[7] D. Chakraborty, F. Foucaud, H. Gahlawat, S. K. Ghosh, and B. Roy. Hardness and approximation for the geodetic set problem in some graph classes. In *Proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM'20)*, volume 12016 of *Lecture Notes in Computer Science*, pages 102–115, Cham, 2020. Springer International Publishing.

[8] Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. In *33rd International Symposium on Algorithms and Computation (ISAAC 2022)*, volume 248 of *LIPIcs*, pages 12:1–12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.

[9] M. C. Dourado, F. Protti, D. Rautenbach, and J.L. Szwarcfiter. Some remarks on the geodetic number of a graph. *Discrete Mathematics*, 310(4):832–837, 2010.

[10] M. C. Dourado, F. Protti, and J.L. Szwarcfiter. On the complexity of the geodetic and convexity numbers of a graph. In *Proceedings of the International Conference on Discrete Mathematics (ICDM)*, volume 7 of *RMS Lecture Notes Series*, pages 101–108. Ramanujan Mathematical Society, 2008.
[11] A. L. Douthat and Man C. Kong. Computing geodetic bases of chordal and split graph. *Journal of Combinatorial Mathematics and Combinatorial Computing*, pages 67–77, 1996.

[12] T. Ekim, A. Erey, P. Heggernes, P. van't Hof, and D. Meister. Computing minimum geodetic sets of proper interval graphs. In *Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN'12)*, volume 7256 of *Lecture Notes in Computer Science*, pages 279–290. Springer, 2012.

[13] M. Farber and R. E. Jamison. Convexity in graphs and hypergraphs. *SIAM Journal on Algebraic Discrete Methods*, 7(3):433–444, 1986.

[14] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. *Algorithmica*, 78:914–944, 2017.

[15] G. C. M. Gomes, C. V. G. C. Lima, and V. F. dos Santos. Parameterized complexity of Equitable Coloring. *Discrete Mathematics & Theoretical Computer Science*, vol. 21 no. 1, ICGT 2018, May 2019.

[16] F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. *Mathematical and Computer Modelling*, 17(11):89–95, 1993.

[17] P. Heggernes, P. van't Hof, D. Meister, and Y. Villanger. Induced subgraph isomorphism on proper interval and bipartite permutation graphs. *Theoretical Computer Science*, 562:252–269, 2015.

[18] C. Hernando, T. Jiang, M. Mora, I. M. Pelayo, and C. Seara. On the steiner, geodetic and hull numbers of graphs. *Discrete Mathematics*, 293(1-3):139–154, 2005.

[19] M. M. Kanté and L. Nourine. Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. *SIAM Journal on Discrete Mathematics*, 30(1):311–326, 2016.

[20] Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set. *J. Graph Algorithms Appl.*, 26(4):401–419, 2022.

[21] T. Kloks. *Treewidth, Computations and Approximations*. Springer, 1994.

[22] Carlos V.G.C. Lima, Vinicius F. dos Santos, João H.G. Sousa, and Sebastián A. Urrutia. On the computational complexity of the strong geodetic recognition problem. *arXiv preprint arXiv:2208.01796*, 2022.

[23] M. Mezzini. Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. *Theoretical Computer Science*, 745:63–74, 2018.

[24] I. M. Pelayo. *Geodesic Convexity in Graphs*. Springer, 2013.

[25] Chonghuan Wang, Yiwen Song, Guiyun Fan, Haiming Jin, Lu Su, Fan Zhang, and Xinbing Wang. Optimizing cross-line dispatching for minimum electric bus fleet. *IEEE Transactions on Mobile Computing*, 22(4):2307–2322, 2023.
<figure><img src="image_13.png" /><figcaption>Figure 10: Illustration of the gadgets for the 3-SAT instance $(x_1 \lor \overline{x_2} \lor x_3)$. The names of the special intervals created at each gadget are highlighted above or below the box illustrating the respective gadgets.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Figure 11: Roadmap for proof of Theorem 2.</figcaption></figure>