Dibyayan Chakraborty
email: d.chakraborty@leeds.ac.uk.

Sandip Das

Florent Foucaud

Harmender Galhawat

Harmender Gahlawat

Dimitri Lajou

Algorithms and complexity for geodetic sets on interval and chordal graphs

come

Introduction

A simple undirected graph G has vertex set V (G) and edge set E(G). For two vertices u, v ∈ 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) = u,v∈S I(u, v). We say that T ⊆ V (G) is covered by S if T ⊆ 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 [START_REF] Harary | The geodetic number of a graph[END_REF], 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 important geometric notion of convexity: see [START_REF] Farber | Convexity in graphs and hypergraphs[END_REF][START_REF] Pelayo | Geodesic Convexity in Graphs[END_REF] 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 [START_REF] Chakraborty | Hardness and approximation for the geodetic set problem in some graph classes[END_REF][START_REF] Wang | Optimizing cross-line dispatching for minimum electric bus fleet[END_REF]. See also [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF] 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 [START_REF] Douthat | Computing geodetic bases of chordal and split graph[END_REF][START_REF] Farber | Convexity in graphs and hypergraphs[END_REF].

The algorithmic complexity of Minimum Geodetic Set has been studied actively. Minimum Geodetic

Set is known to be NP-hard on chordal graphs [START_REF] Douthat | Computing geodetic bases of chordal and split graph[END_REF], and chordal bipartite graphs [START_REF] Dourado | Some remarks on the geodetic number of a graph[END_REF][START_REF] Dourado | On the complexity of the geodetic and convexity numbers of a graph[END_REF], subcubic graphs [START_REF] Bueno | On the hardness of finding the geodetic number of a subcubic graph[END_REF],

planar graphs [START_REF] Chakraborty | Hardness and approximation for the geodetic set problem in some graph classes[END_REF], co-bipartite graphs [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF]. On the positive side, polynomial-time algorithms to solve Minimum Geodetic Set are known for cographs [START_REF] Dourado | Some remarks on the geodetic number of a graph[END_REF], split graphs [START_REF] Dourado | Some remarks on the geodetic number of a graph[END_REF][START_REF] Douthat | Computing geodetic bases of chordal and split graph[END_REF] and more generally well-partitioned chordal graphs [START_REF] Ahn | Well-partitioned chordal graphs[END_REF], ptolemaic graphs [START_REF] Farber | Convexity in graphs and hypergraphs[END_REF] and more generally distance-hereditary graphs [START_REF] Kanté | Polynomial time algorithms for computing a minimum hull set in distancehereditary and chordal graphs[END_REF], block-cactus graphs [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF], outerplanar graphs [START_REF] Mezzini | Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs[END_REF] and proper interval graphs [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF]. 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 [START_REF] Kellerhals | Parameterized complexity of geodetic set[END_REF]. The problem is FPT for parameters tree-depth, modular-width and feedback edge set number [START_REF] Kellerhals | Parameterized complexity of geodetic set[END_REF].

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 ω 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 [START_REF] Allgeier | Structure and properties of maximal outerplanar graphs[END_REF] 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 [START_REF] Ahn | Well-partitioned chordal graphs[END_REF]-hard for parameter treewidth [START_REF] Kellerhals | Parameterized complexity of geodetic set[END_REF].

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. [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF] 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 [START_REF] Foucaud | Identification, location-domination and metric dimension on interval and permutation graphs[END_REF]). Our reduction (from 3-Sat) uses a quite involved novel technique, that we hope can be used chordal [START_REF] Dourado | Some remarks on the geodetic number of a graph[END_REF][START_REF] Douthat | Computing geodetic bases of chordal and split graph[END_REF] well-partitioned chordal [START_REF] Ahn | Well-partitioned chordal graphs[END_REF] split [START_REF] Dourado | Some remarks on the geodetic number of a graph[END_REF][START_REF] Douthat | Computing geodetic bases of chordal and split graph[END_REF] interval proper interval [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF] ptolemaic [START_REF] Farber | Convexity in graphs and hypergraphs[END_REF] k-trees (fixed k) block [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF] maximal outerplanar [START_REF] Allgeier | Structure and properties of maximal outerplanar graphs[END_REF] trees [START_REF] Harary | The geodetic number of a graph[END_REF] 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.

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 [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF]. 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 [START_REF] Gomes | Parameterized complexity of Equitable Coloring[END_REF] and Induced Subgraph Isomorphism [START_REF] Heggernes | Induced subgraph isomorphism on proper interval and bipartite permutation graphs[END_REF]. Theorem 2 together with the algorithm from [START_REF] Ekim | Computing minimum geodetic sets of proper interval graphs[END_REF] 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.

Algorithm for chordal graphs

We give an FPT algorithm for chordal graphs parameterized by the clique number (which is also the treewidth 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 [START_REF] Belmonte | Detecting fixed patterns in chordal graphs in polynomial time[END_REF] based on the notion of nice tree-decompositions for general graphs [START_REF] Kloks | Computations and Approximations[END_REF]. 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 v 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.

A join node

v has two children v 1 and v 2 such that X v = X v1 = X v2 . 6. An introduce node v has one child v 1 such that X v \ {x} = X v1 , where x ∈ X v . 7. A forget node v has one son v 1 such that X v = X v1 \ {x}, where x ∈ X v1 . 8. A leaf node v is a leaf of T with X v = ∅.
9. The tree T is rooted at a leaf node r with X r = ∅.

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 ω(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 ≤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 ∈ V (G ≤v ) and w ∈ V (G) \ V (G ≤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 ′ ⊆ 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 ≤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 |Xv | different collections of subsets of X v , we can capture the possible effects of all the solution vertices in G -G ≤v i.e. "exterior vertices" on G ≤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,[START_REF] Bonnet | Optimality program in segment and string graphs[END_REF][START_REF] Bueno | On the hardness of finding the geodetic number of a subcubic graph[END_REF][START_REF] Chakraborty | Algorithms and complexity for geodetic Sets on planar and chordal graphs[END_REF]. We prove the exhaustiveness of these rules in Lemmas 7, 8, 9, 10 and we prove the correctness of our algorithm in Lemma 11.

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 ⊆ X with respect to

X, if d(y, x) = d y when x ∈ A and d(y, x) = d y + 1 when x ∈ X \ 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 ∈ T , let G ≤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 ≥v and G >v . For a node v let T v be the set of all 4-tuples τ = (τ int , τ ext , τ cov , τ bag ) where τ int , τ ext are Boolean vectors of size 2 |Xv| indexed by subsets of X v and τ cov , τ bag are subsets of

X v . Since |X v | ≤ ω(G), the cardinality of T v is 2 2 O(ω(G)) .
For a node v and a 4-tuple τ = (τ int , τ ext , τ cov , τ bag ) let H τ v denote the graph obtained by adding a vertex S to G ≤v whenever there is a set S ⊆ X v with τ ext [S] = 1, and making S adjacent to each x ∈ S. Let S τ v = {S : S ⊆ X v , τ ext [S] = 1} denote the newly added vertices. Observe that G ≤v is an induced subgraph of H τ v for any 4-tuple τ ∈ T v .

Definition 2. Let v be a node of T . A 4-tuple τ = (τ int , τ ext , τ cov , τ bag ) of T v is a "type associated with v" if there exists a set D ⊆ V (H τ v ) such that the following hold.

(i) S τ v ⊆ D and τ bag = D ∩ X v .

(ii) For a vertex w ∈ (V (G ≤v ) \ X v ) ∪ τ cov there exists a pair w 1 , w 2 ∈ D such that w ∈ I(w 1 , w 2 ) and

w 1 ∈ D \ S τ v . (iii) For a subset A ⊆ X v , we have τ int [A] = 1 if and only if D ∩ V (G ≤v ) contains a vertex which is closer to A with respect to X v .
Moreover, we shall say that the set D \ S τ v is a "certificate" for (v, τ ).

Intuitively, for a type τ associated with a node v and for a set A ⊆ X v of vertices, the Boolean τ int [A] represents whether there is some vertex y in the partial solution for G ≤v such that y is close to A with respect to X v ("int" stands for "interior"). The Boolean τ 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 τ 0 = (0, 0, ∅, ∅) 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 ∈ I(u, v) ∩ X if and only if x ∈ A ∩ B or, A ∩ B = ∅ and x ∈ A ∪ B.

Proof. Suppose that for all y ∈ A, d(u, y) = d u and for all y ∈ B, d(v, y) = d v for some integers d u , d v and let x ∈ X. Now we consider the following two cases.

1. A ∩ B ̸ = ∅. If x ∈ A ∩ B, then d(u, v) = d u + d v
d(u, x) + d(x, v) = d u + d v , x ∈ I(u, v). Conversely, if x / ∈ A ∩ B, let y ∈ A ∩ B. Then, d(u, v) ≤ 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 / ∈ I(u, v). 2. A ∩ B = ∅. If x ∈ A ∪ B, then d(u, v) = d u + d v + 1
, as any shorter path would imply the existence of a vertex y ∈ X such that d(u, y)

+ d(y, v) ≤ d u + d v which would contradict A ∩ B = ∅. As d(u, x)+d(x, v) = d u +d v +1, x ∈ I(u, v). Conversely, if x / ∈ A∪B, let y ∈ A, then d(u, v) ≤ 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 / ∈ I(u, v).
This completes the proof.

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 ≤v , the set D∩G ≤v acts as a certificate for some (v, τ ). This proves the exhaustiveness of our definition of type. Lemma 4. Let D be a geodetic set of G, then for each node v ∈ T , there is a type τ associated with v such that D ∩ V (G ≤v ) is a certificate of (v, τ ).

Proof. We construct τ from D as follows. Define

τ bag = D ∩X v . For each vertex u ∈ D ∩V (G ≤v ) we find the set Z u ⊆ X v such that u is close to Z u with respect to X v and put τ int [Z u ] = 1. For each u ∈ D ∩ V (G >v ) we find the set Z u ⊆ X v such that u is close to Z u with respect to X v and put τ ext [Z u ] = 1. We put τ cov = X v \ D. Observe that D ∩ V (G ≤v ) is a certificate of (v, τ ).
For a node v, there might be some 4-tuples in 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 τ = (τ int , τ ext , τ cov , τ bag ) be a type associated with v. Then τ must satisfy all of the following conditions.

(a) Whenever we have a vertex u ∈ τ bag we have

τ int [{u}] = 1. (b) τ int [∅] = τ ext [∅] = 0. (c) For all x ∈ X v , τ int [A] = 1 and τ ext [B] = 1, if x ∈ A ∩ B or if A ∩ B = ∅ and x ∈ A ∪ B then τ 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 τ 0 = (0, 0, ∅, ∅) is the only type associated with v. Moreover, τ 0 is the only type associated with the root node of T .

Let v be an introduce node and u be its child. Let τ, τ 1 be types associated with v, u respectively. Below we state some rules that τ and τ 1 must follow so that the certificate for (u, τ 1 ) can be extended to a certificate for (v, τ ). Definition 3. Let v be an introduce node and τ be a type associated with v. Let u be the child of v and τ 1 be a type associated with u. The pair (τ, τ 1 ) is compatible if the following holds.

(a) τ bag 1 = τ bag \ {x}. (b) τ cov 1 = τ cov ∩ X u . (c) For A ⊊ X u , τ ext 1 [A] = 1 if and only if τ ext [A] = 1 or τ ext [A ∪ {x}] = 1. (d) τ ext 1 [X u ] = 1 if and only if τ ext [X v ] = 1, τ ext [X u ] = 1, x ∈ τ bag or τ ext [{x}] = 1. (e) If x / ∈ τ bag then there exist non-empty sets A ⊆ X u , B ⊆ X v \ A such that τ int 1 [A] = 1 and τ ext [B ∪ {x}] = 1. (f ) τ int [{x}] = 1 if and only if x ∈ τ bag . (g) For all non empty A ⊆ X u , τ int [A ∪ {x}] = 0, (h) For all A ⊆ X u , τ int [A] = 1 if and only if τ int 1 [A] = 1, Lemma 7.
Let v be an introduce node, τ be a type associated with v, u be the child of v and D be a minimal certificate of (v, τ ). Then there exists a type τ 1 associated with u such that (τ, τ 1 ) is a compatible pair.

Proof.

Let X v = X u ∪ {x}. Define τ bag 1 = D ∩ X u , τ cov 1 = τ cov ∩ X u and τ int 1 [A] = 1
if and only if there exists y ∈ D \ {x} such that y is close to A with respect to X u . Finally, define τ ext 1 according to Conditions 3(c) and 3(d). Observe that the set D ′ = D \ {x} satisfies all the conditions in Definition 2 for (u, τ 1 ) and the pair (τ, τ 1 ) satisfies all conditions in Definition 3.

Let C v denote the set of compatible pairs (τ, τ 1 ) where τ, τ 1 are types associated with v and u, respectively. Let v be a forget node and u be its child. Let τ, τ 1 be types associated with v, u respectively. Below we state some rules that τ and τ 1 must follow so that the certificate for (u, τ 1 ) can be extended to a certificate for (v, τ ). Definition 4. Let v be a forget node and τ be a type associated with v. Let u be the child of v and τ 1 be a type associated with u. The pair (τ, τ 1 ) are compatible if the following holds.

(a) τ bag = τ int 1 \ {x}, (b) For all A ⊆ X v , τ ext 1 [A] = 1 if and only if τ ext [A] = 1, (c) For all A ⊆ X v , τ ext 1 [A ∪ {x}] = 0. (d) For A ⊊ X v , τ int [A] = 1 if and only if τ int 1 [A] = 1 or τ int 1 [A ∪ {x}] = 1. (e) τ int [X v ] = 1 if and only if τ int 1 [X u ] = 1, τ int 1 [X v ] = 1 or τ int 1 [{x}] = 1, (f ) τ cov 1 = τ cov ∪ {x}.
Lemma 8. Let v be a forget node, τ be a type associated with v, u be the child of v, and D be a minimal certificate of (v, τ ). Then there exists a type τ 1 associated with u such that (τ, τ 1 ) is a compatible pair.

Proof.

Let X v = X u \ {x}. Define τ bag 1 = D ∩ X u , τ cov 1 = τ cov ∪ {x} and τ int 1 [A] = 1
if and only if there exists y ∈ D such that y is close to A with respect to X u . Finally, define τ ext 1 according to Definition 4(b) and 4(c). Observe that the set D satisfies all the conditions in Definition 2 for (u, τ 1 ) and the pair (τ, τ 1 ) satisfies all conditions in Definition 4.

Let C v denote the set of compatible pairs (τ, τ 1 ) where τ, τ 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 τ, τ 1 , τ 2 be types associated with v, u 1 , u 2 respectively. Below we state some rules that τ, τ 1 , τ 2 must follow so that the certificates for (u 1 , τ 1 ) and (u 2 , τ 2 ) can be combined and extended to a certificate for (v, τ ). Definition 5. Let v be a join node and τ be a type associated with v. Let u 1 , u 2 be the children of v and τ 1 , τ 2 be types associated with u 1 , u 2 respectively. The triplet (τ, τ 1 , τ 2 ) is compatible if all the following holds.

(a) τ bag = τ bag 1 = τ bag 2 , (b) For i, j such that {i, j} = {1, 2} and A ⊆ X v , τ ext i [A] = 1 if and only if τ int j [A] = 1 or τ ext [A] = 1. (c) τ cov = τ cov 1 ∪ τ cov 2 ∪ Cov(u 1 , u 2 ) where Cov(u 1 , u 2 ) is the subset of vertices x of X v such that there exists A, B ⊆ X v with τ int 1 [A] = 1 and τ int 2 [B] = 1 where x ∈ A ∩ B or where x ∈ A ∪ B and A ∩ B = ∅. (d) For i, j such that {i, j} = {1, 2} and A ⊆ X v , τ int i [A] = 1 then τ int [A] = 1 and τ ext j [A] = 1.
(e) For i, j such that {i, j} = {1, 2} and

A ⊆ X v , τ int i [A] = 0 and τ int j [A] = 0 then τ int [A] = 0. Lemma 9.
Let v be a join node and τ be a type associated with v. Let u 1 , u 2 be the children of v. Then there are types τ 1 , τ 2 associated with u 1 , u 2 respectively such that (τ, τ 1 , τ 2 ) is a compatible triplet.

Proof. For each i ∈ {1, 2} define τ bag i = τ bag and τ int i [A] = 1 if and only if there exists y ∈ D ∩ G ≤ui such that y is close to A with respect to X ui . Define τ ext i according to Conditions 5(b) and 5(b). Define τ cov i according to Definition 5(c). Observe that for each i ∈ {1, 2} the sets D ∩ V (G ≤ui ) satisfies all the conditions in Definition 2 for (τ, τ i ) and the triplet (τ, τ 1 , τ 2 ) is compatible.

For a join node v with children u 1 , u 2 , let C v denote the set of compatible triplets (τ, τ 1 , τ 2 ) where τ, τ 1 , τ 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 τ 0 = (0, 0, ∅, ∅). Definition 6. Consider the root r, its child u with X u = {x} and a type τ associated with u.

Then (τ 0 , τ ) is a compatible pair if x ∈ τ bag 1 and τ ext [A] = 0 for all A ⊆ 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 (τ 0 , τ 1 ) where τ 1 is a type associated with u.

Let C r denote the set of compatible pairs (τ 0 , τ ) where τ 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 sol [v, (0, 0, ∅, ∅)] = ∅ Let v be an introduce node having u as child. Then for each type

τ ∈ T v define sol [v, τ ] = min (τ,τ1)∈Cv sol [u, τ 1 ] ∪ τ bag
Let v be a forget node having u as child. Then for each type τ ∈ T v define

sol [v, τ ] = min (τ,τ1)∈Cv sol [u, τ 1 ]
Let v be a join node having u 1 , u 2 as children. Then for each type τ ∈ T v define

sol [v, τ ] = min (τ,τ1,τ2)∈Cv sol [u 1 , τ 1 ] ∪ sol [u 2 , τ 2 ]
Finally for the root r let u be its child and τ 0 = (0, 0, ∅, ∅). Define

sol [r, τ 0 ] = min (τ0,τ1)∈Cr sol [u, τ 1 ]
We shall show in the following lemma that sol [r, (0, 0, ∅, ∅)] corresponds to a geodetic set of G with minimum cardinality. Recall the definitions of H τ v and S τ v .

Lemma 11. For each node v and type τ associated with v, sol [v, τ ] is a certificate of (v, τ ) 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 ∪ {x}. First we show that sol [v, τ ] is a certificate of (v, τ ). Let τ 1 be a type associated with u such that sol [v, τ ] = sol [u, τ 1 ]∪τ bag and consider the set D = sol [u, τ 1 ] ∪ τ bag ∪ S τ v . By Definition 3(a) we have that τ bag 1 = τ bag \ {x}. Hence D ∩ X v = sol [v, τ ] ∩ X v = (sol [u, τ 1 ] ∪ τ bag ) ∩ X v = (sol [u, τ 1 ] ∩ X v ) ∪ (τ bag ∩ X v ) = (sol [u, τ 1 ] ∩ (X u ∪ {x})) ∪ τ bag = (sol [u, τ 1 ] ∩ X u ) ∪ τ bag = τ bag 1 ∪ τ bag = τ bag . Hence D satisfies Definition 2(i). Now, consider any vertex w ∈ (V (G ≤v ) \ X v ) ∪ τ cov which is distinct from x. Then w ∈ (V (G ≤u ) \ X u ) ∪ (τ cov ∩ X u ). Definition 3(b) ensures that τ cov 1 = τ cov ∩ X u and hence w ∈ (V (G ≤u ) \ X u ) ∪ τ cov
1 . Now, due to our induction hypothesis, we have that there exists

w 1 , w 2 ∈ sol [u, τ 1 ] ∪ S τ1 u such that w ∈ I(w 1 , w 2 ) and w 1 ∈ sol [u, τ 1 ]. If w 2 ∈ sol [u, τ 1 ] then w 1 , w 2 ∈ sol [v, τ ] and therefore w 1 , w 2 ∈ D. Hence, Definition 2(ii) is satisfied in this case. Assume w 2 ∈ S τ1 u ; then, there is a set A ⊆ X u such that w 2 = A and τ ext 1 [A] = 1. If A ̸ = X u ,
⊆ X u , B ⊆ X v \ A such that τ int 1 [A] = 1 and τ ext [B ∪ {x}] = 1. Hence, sol [u, τ 1 ] contains a vertex, say a, which is close to A with respect to X u . There also exists a vertex, say b ∈ S τ v , such that b = B. By Lemma 3, x ∈ I(a, b). Therefore, Definition 2(ii) is satisfied. Consider A ⊆ X v such that τ int [A] = 1. If A = {x}, then, due to Definition 3(f), we have x ∈ τ bag and therefore x ∈ D. Due to Definition 3(g), we have A ⊆ X u . By Definition 3(h), τ int 1 [A] = 1 and therefore sol [u, τ 1 ] contains a vertex w such that w ∈ V (G ≤u ) and w is closer to A with respect to X u . Since v is an introduce node with X v = X u ∪ {x}, w must be closer to A with respect to X v . Hence, Definition 2(iii) is satisfied. Hence, sol [v, τ ] is a certificate of (v, τ ). Now, Lemma 7 implies that sol [v, τ ] is minimum. 2. Now, assume that v is a forget node. Let u be the child of v, X v = X u \ {x}. First, we show that sol [v, τ ] is a certificate of (v, τ ). Let τ 1 be a type associated with u such that sol [v, τ ] = sol [u, τ 1 ]
and consider the set

D = sol [u, τ 1 ] ∪ S τ v . By Definition 4(a) we have that τ bag = τ bag 1 \ {x}. Hence, D ∩ X v = sol [v, τ ] ∩ X v = sol [u, τ 1 ] ∩ (X u \ {x}) = (sol [u, τ 1 ] ∩ X u ) \ {x} = τ bag 1 \ {x} = τ bag . Hence D satisfies Definition 2(i). Now, consider any vertex w ∈ (V (G ≤v ) \ X v ) ∪ τ cov . Observe that V (G ≤v ) = V (G ≤u ), X v ⊂ X u .
Moreover, due to Conditions 4(b) and 4(c), we have that

τ ext = τ ext 1 . Therefore, w ∈ (V (G ≤u ) \ X u ) ∪ τ cov 1 , there exist w 1 , w 2 ∈ sol [u, τ 1 ] = sol [v, τ ] such that w is covered by w 1 , w 2 in H τ v . Hence, Definition 2(ii) is satisfied. By Definition 4(d), for A ⊊ X v , τ int [A] = 1 if and only if τ int 1 [A] = 1 or τ int 1 [A ∪ {x}] = 1. Indeed, if some y ∈ G ≤v is close to A or A ∪ {x} with respect to X u , then it is close to A with respect to X v .
Conversely, if there exists some y ∈ G ≤v close to A with respect to X v , then A is B ∩ 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 ∪ {x}.

By Definition 4(e), τ int [X v ] = 1 if and only if τ int 1 [X u ] = 1, τ int 1 [X v ] = 1 or τ int 1 [{x}] = 1. Indeed, if some y ∈ G ≤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 ∈ G ≤v close to X v with respect to X v , then X v is included in A or X u \ 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, sol [v, τ ] is a certificate of (v, τ ). Now Lemma 8 implies that sol [v, τ ] is minimum.

3. Assume v to be a join node. Let u 1 , u 2 be the children of v. Let τ 1 , τ 2 be types associated with

u 1 , u 2 such that sol [v, τ ] = sol [u 1 , τ 1 ]∪sol [u 2 , τ 2 ]. Consider the set D = sol [v, τ ]∪S τ v . Due to Definition 5(a) we have τ bag = τ bag 1 = τ bag 2 . This implies sol v, τ bag ∩ X v = (sol [u, τ 1 ] ∩ τ bag 1 ) ∪ (sol [u 2 , τ 2 ] ∩ τ bag 2 ) = τ bag . Consider y ∈ (V (G ≤v )\X v )∪τ cov . If y ∈ (V (G ≤u1 )\X u1 )∪τ cov 1 )
, then y is covered by a pair of vertices This completes the proof.

y 1 and y 2 in sol [u, τ 1 ] ∪ S τ1 u1 . If y 1 , y 2 ∈ sol [u 1 , τ 1 ] then y 1 ,

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 ω(G) ). We shall use the following lemma.

Lemma 12. Let X be a clique cutset of an interval graph G. There exists a collection A of subsets of X of size O(|X|) such that for each vertex v ∈ V (G), if v is close to A with respect to X, then A ∈ A.

Proof. If v ∈ 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 ∈ X such that d(v, u) = d, then for every w ∈ X such that min(w) ≤ min(u), d(v, w) ≤ 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:

u∈X {{w ∈ X| min(w) ≤ min(u)}}. Hence, A = u∈X {{w ∈ X| min(w) ≤ min(u)} , {w ∈ X| max(w) ≥ max(u)} , {u}} Observe that |A| is O(|X|).
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 × {0, 1} A × 2 Xv × 2 Xv . Hence, there are 2 O(ω) types for an interval graph. This proves the statement of Theorem 1 regarding interval graphs.

Hardness for interval graphs

We now prove Theorem 2. Let F be an instance of 3-Sat with variables x 1 , . . . , x n and clauses C 1 , . . . , 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 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).

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 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 ≤ i ≤ n, we create the variable gadget X i . Each variable gadget is composed of several implication gadgets. An implication gadget IM P 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 .

[¬p → q] ensures that if p is not Reduction Variable Gadget (X i ) Clause Gadget (C j ) Implication Gadget Start Gadget Covering Gadget AND Gadget Insert Gadget End Gadget (a) S X 1 X 2 • • • X n C 1 C 2 • • • C m E (b)
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 ≤ j ≤ m, we construct the clause gadget 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 COV[i]. For two intervals p and q, the corresponding AND gadget is denoted by AND [p, 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 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 IM P [¬p → q]. In Subsection 3.5, we describe a generic construction of the cover gadget COV[i]. In Subsection 3.6, we describe a generic construction of the insert gadget INS [p, q]. In Subsection 3.7, we describe a generic construction of the AND-gadget AND [p, q]. Then, in Subsection 3.8, we describe the construction of the variable gadget. In Subsection 3.9,

o ⊤ u o u ⊤ Figure 3:
The start gadget S . For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.

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

Notations

We shall use the following notations. Let S be a set of intervals. For a vertex v ∈ V (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 ∈ S}, max(S) = max{max(v) : v ∈ 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 ∈ S. A shortest path between u, v is a shortest path between u, v in I(S). The set 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 , . . . , u t } of intervals is a track if max(u i ) = min (u i+1 ) for all 1 ≤ i < t. Observe that if T is a track, then 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 ∈ R(T ). Definition 7. Let T and T ′ be two tracks such that T ∪ T ′ is a proper set of intervals. Then, T < T ′ if max(T ) < max(T ′ ).

Let T be a set of tracks and T ∈ 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 T " and "minimal track of T " are analogously defined.

Initiation and construction of start gadget S

Let F be an instance of 3-Sat with variables x 1 , . . . , x n and clauses C 1 , . . . , C m . Let ϵ = 1 (n+m) 4 . The start gadget S consists of four intervals which are defined as follows: the

start interval o = [1, 1], u o = [1, 2], the true interval ⊤ = [1 + ϵ, 1 + ϵ] and u ⊤ = [1 + ϵ, 2 + ϵ]. Let T 1 = {u o } and T 2 = {u ⊤ }. Observe that T 1 , T 2 are tracks and T 1 < T 2 .
We initialize two more sets, the set T = {T 1 , T 2 }, and the set D = S . In what follows, 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 T . Let R(T 1 ) = {o} and R(T 2 ) = {⊤}. Recall that for a track T , R(T ) denotes the set of root intervals of T .

s q q r q • • • X T p u Tp v Tp w Tp T 2 t T 1 t 2 t 1 • • • X ′ Figure 4:
The implication gadget IM P [¬p → q]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.

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 ∈ T be the track such that p ∈ R(T p ). Since p ̸ = o, T p is not the minimal element in T . Below we describe the three steps for constructing IM P [¬p → q]. See Figure 4 for a graphical representation of the intervals. 2. Creation of new intervals: Let X and X ′ be the tracks that precede and follow T p in T , respectively. Note that X always exists since p ̸ = o. When X ′ exists, let θ = max(u X ′ ) and θ ′ = max(v X ′ ).

Otherwise, θ = max(u Tp ) + ϵ and θ ′ = max(v Tp ) + ϵ.

Define q = max(uX )+max(uT p ) 2

, max(uT p )+θ 2

, r q = max(q), max(vT p )+θ ′ 2

and s q = [max(r q ), max(r q )].

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), max(vT p )+min(sq) 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 IM P

[¬p → q] = {q, r q , s q } ∪ T 1 ∪ T 2 ∪ T ∈T {u T , v T , w T }. Let D = D ∪ IM P [¬p → q]. For each T ∈ T , let T = T ∪ T new and T = T ∪ {T 1 , T 2 }.
Observe that the intersection graph of D does not contain K 1,5 as induced subgraph.

Construction of covering gadgets

Below we describe the three steps for constructing the covering gadget of the clause C i . See Figure 5. Nevertheless, the obtained interval graph is unchanged.

c i b i a i d i cov i f i • • • T di T ai T bi T ci T fi
1. Extension of existing tracks: For each track T ∈ T , introduce three new intervals

u i T = [max(T ), max(T ) + 1], v i T = [max(T ) + 1, max(T ) + 2] and w i T = [max(T ) + 2, max(T ) + 3]. Let T new = {u i T , v i T , w i T }.
Observe that, for two tracks T, T ′ ∈ T with T < T ′ , we have

(T ∪ T new ) < (T ′ ∪ T ′ new ).

Creation of new intervals:

Let T be the maximal track in T . Let θ = min(u i T ) + ϵ. We define

a i = [θ, θ + ϵ], b i = [θ, θ + 2ϵ], c i = [θ, θ + 3ϵ] and d i = [θ, θ]. Also define cov i = max(v i T ) + 4ϵ, max(v i T ) + 7ϵ , and f i = [max(cov i ), max(cov i )].

Creation of new tracks:

Now we create five more tracks as follows.

Let

T ai = {[max(a i ) + k, max(a i ) + k + 1] | k ∈ {0, 1, 2}}, T bi = {[max(b i ) + k, max(b i ) + k + 1] | k ∈ {0, 1, 2}} and
T ci = {[max(c i ) + k, max(c i ) + k + 1] | k ∈ {0, 1, 2}}. Observe that T ai , T bi , T ci are tracks and define R(T ai ) = {a i } , R(T bi ) = {b i } and R(T ci ) = {c i }. Also, define T di = {[max(d i ) + k, max(d i ) + k + 1] |k ∈ {0, 1, 2}} where R(T di ) = {d i } and T fi = {[max(f i ), max(f i ) + 1]} where R(T fi ) = {cov i , f i }.
To complete the construction of the covering gadget of C i , we define

COV[i] = {a i , b i , c i , cov i , d i , f i } ∪ {u i T , v i T , w i T } T ∈T ∪   y∈{a,b,c,d,f } T yi   . For each T ∈ T , let T = T ∪ T new and T = T ∪ {T ai , T bi , T ci , T di , T fi }. We set D = D ∪ COV[i].
Observe that the intersection graph of D does not contain K 1,5 as induced subgraph.

Construction of the insert gadget

Let T p and T q be two tracks of 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.

Extension of existing tracks:

For each track T ∈ T , we introduce one new interval u T = [max(T ), max(T ) + 1]. Let T new = {u T }. Observe that, for two tracks T, T ′ ∈ T with T < T ′ , we have

(T ∪ T new ) < (T ′ ∪ T ′ new ). σ(p, q) • • • T p T m T q • • • • • • X Figure 6: The insert gadget INS [p, q].
For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.

2. Creation of a new interval: Let X be the track that just follows T p in T . Observe that X always exists. Let σ(p, q) = max(u Tp )+max(u X ) 2

, max(u Tp )+max(u X ) 2

.

Creation of a new track:

Let T m = {[max(σ(p, q)), max(σ(p, q)) + 1]} and R(T m ) = {σ(p, q)}.
To complete the construction, we define

INS [p, q] = {σ(p, q)} ∪ {u T , v T } T ∈T ∪ T m . We set D = D ∪ INS [p, q]. For each T ∈ T , let T = T ∪ T new and T = T ∪ {T m }. Observe that T p < T m < T q in T .
Moreover, observe that the intersection graph of D does not contain K 1,5 as induced subgraph.

Construction of AND gadgets

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

1. Creation of insert gadget: Create an insert gadget INS [p, q]. Recall that the interval named σ(p, q) exists and it is the root of track, say, T m .

Extension of existing tracks:

For each track T ∈ T , introduce two new intervals u T = [max(T ), max(T ) + 1] and v T = [max(T ) + 1, max(T ) + 2]. Let T new = {u T , v T }. Observe that, for two tracks T, T ′ ∈ T with T < T ′ , we have (T ∪ T new ) < (T ′ ∪ T ′ new ).

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 α (p, q) = max(uY 1 )+max(uT p ) 2 , max(uT p )+max(uT m ) 2 and β (p, q) = max(uT p )+max(α(p,q)) 2 , max(u Tp )+max(α(p,q)) 2
.

Let Y 2 be the track just preceding T q in T . Observe that either

Y 2 = T m or T m < Y 2 < T q . Now define γ (p, q) = max(α (p, q)), max(uY 2 )+max(uT q ) 2
. Let Y ′ 2 be the track just following T q in T . We define h = max(u Y ′

2 ) if Y ′ 2 exists and h = max(u Tq ) + ϵ otherwise. Now we define δ (p, q) = max(γ (p, q)), max(uT q )+h 2 .

Creation of new tracks:

We create T 1 = {[max(β (p, q)), max(β (p, q) + 1]} where R(T 1 ) = {α (p, q), β (p, q)}, T 2 = {[max(γ (p, q)), max(γ (p, q)) + 1]} where R(T 2 ) = {γ (p, q)} and T 3 = {[δ (p, q), δ (p, q) + 1]} where R(T 3 ) = {δ (p, q)}. β (p, q) α (p, q) δ (p, q) γ (p, q) • • • Y 1 T p T 1 T m • • • Y 2 T 2 T q T 3 • • • Y ′ 2 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.

To complete the construction, define AND [p, q] = {α (p, q), β (p, q), γ (p, q), δ (p, q)}∪{u T , v T } T ∈T ∪ {T j } 1≤j≤3 . For each T ∈ T , let T = T ∪ T new . Let D = D ∪ AND [p, q] and T = T ∪ {T 1 , T 2 , T 3 }. Observe that the intersection graph of D does not contain K 1,5 as induced subgraph.

Construction of variable gadgets

We construct the variable gadgets sequentially and connect each of them to the previous one (X 1 is connected to the start gadget S ). Assuming that we have placed S , X 1 , . . . , X i-1 , we construct X i as follows. For variable x i , the gadget X i consists of two implication gadgets. Let D and T be the set of intervals and tracks created so far. First, we construct IM P [¬⊤ → x i ]. Observe that the sets D and T have been updated after the last operation. There is an interval x i in D and there is a track T ∈ T whose root is x i . Now we construct IM P [¬x i → x i ]. Observe that after constructing all the variable gadgets, for each literal ℓ, there is an interval named ℓ in D. See Figure 8 for an illustration of X i created corresponding to the variable x i .

Construction of clause gadgets

We shall complete our construction of clause gadget C i corresponding to the clause

C i = (ℓ 1 i , ℓ 2 i , ℓ 3 i ).
First, we create the covering gadget COV[i] and update D, 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 ℓ 1 i , ℓ 2 i , ℓ 3 i and ℓ 1 i , ℓ 2 i , ℓ 3 i exist. Now we create, in this order, IM P ¬a i → a ′ i , AND a i , corresponding implication gadgets. This completes the construction of C i . See Figure 9 for an illustration of the clause gadget C i .

ℓ 1 i , AND a ′ i , ℓ 1 i , IM P ¬b i → b ′ i , AND b i , ℓ 2 i , AND b ′ i , ℓ 2 i , IM P ¬c i → c ′ i , AND c i , ℓ 3 i , AND c ′ i , ℓ 3 i where a ′ i , b ′ i and c ′ i are three new intervals constructed in the IM P [¬⊤ → x i ] IM P [¬x i → x i ] x i , r xi , s xi x i , r xi , s xi

Construction of end gadget

For each T ∈ 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 ∪ {u T }, D = D ∪ {u T , e T } T ∈T .
For each T ∈ T , let e T be the tail of T . The end gadget 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 ∨ x 2 ∨ x 3 ). Observe that the intersection graph of D does not contain K 1,5 as induced subgraph.

COV[i] IM P ¬ai → a ′ i AND ai, ℓ 1 i AND a ′ i , ℓ 1 i IM P ¬bi → b ′ i AND bi, ℓ 2 i AND b ′ i , ℓ 2 i IM P ¬ci → c ′ i AND ci, ℓ 3 i AND c ′ i , ℓ 3 i d i a i b i c i cov i f i a ′ i r a ′ i s a ′ i σ(a i , ℓ i 1 ) α a i , ℓ i 1 β a i , ℓ i 1 γ a i , ℓ i 1 δ a i , ℓ i 1 σ(a ′ i , ℓ i 1 ) α a ′ i , ℓ i 1 β a ′ i , ℓ i 1 γ a ′ i , ℓ i 1 δ a ′ i , ℓ i 1 b ′ i r b ′ i s b ′ i σ(b i , ℓ i 2 ) α b i , ℓ i 2 β b i , ℓ i 2 γ b i , ℓ i 2 δ b i , ℓ i 2 σ(b ′ i , ℓ i 2 ) α b ′ i , ℓ i 2 β b ′ i , ℓ i 2 γ b ′ i , ℓ i 2 δ b ′ i , ℓ i 2 c ′ i r c ′ i s c ′ i σ(c i , ℓ i 3 ) α c i , ℓ i 3 β c i , ℓ i 3 γ c i , ℓ i 3 δ c i , ℓ i 3 σ(c ′ i , ℓ i 3 ) α c ′ i , ℓ i 3 β c ′ i , ℓ i 3 γ c ′ i , ℓ i 3 δ c ′ i , ℓ i 3 Figure 9: Illustration of the clause gadget C i with literals ℓ 1 i , ℓ 2 i , ℓ 3 i .
The names of the special intervals created at each gadget are highlighted above or below the box illustrating the respective gadgets. created is 2n + 3m. Each clause gadget contains six AND gadgets. Hence, the total number of AND gadgets created is 6m. The total number of covering gadgets created is m. So, the total number of tracks created is 2 + 4n + 35m. The end gadget contains one distinct point interval for each track. Hence, the total number of point intervals is 4 + 6n + 52m. Thus, the total number of intervals in D is O((n + m) 2 ).

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 u and v be two intervals of D such that min(u) < min(v). Let P = u 0 u 1 . . . u k v be an induced path such that u 0 = u and u i+1 is the rightmost neighbour of u i for 0 ≤ i ≤ k-1, and u k-1 / ∈ N (v), while u k ∈ N (v). Then, P is a shortest path.

Proof. Let P = u 0 u 1 . . . u k v and P ′ be a shortest path from u to v which starts by the longest common subpath with P . Hence P ′ = u 0 u 1 . . . u i z . . . v with z / ∈ P . If i = k then P and P ′ have the same length. Otherwise, replace z in P ′ by u i+1 to obtain a path P ′′ . It is indeed a path as max(z) < max(u i+1 ). Moreover P ′ and P ′′ have the same length, a contradiction with the definition of P ′ . Definition 8. Let P = u 1 . . . u k be a path such that u i+1 is the rightmost neighbour of u i for all i ∈ 1 ≤ i ≤ k -2 and u k-2 is not adjacent to u k . The path P is a shortest path between u 1 and u k by Lemma 14. We say that such a path is a "good shortest path". Definition 9. Let u, v, w be three intervals of D such that max(u) < min(w) and v ∈ I(u, w). A shortest path P = u 0 u 1 . . . u k vu k+1 . . . w between u 0 = u and w is "semi-good" if for each 0 ≤ i ≤ k -1, u i+1 is the rightmost interval of u i . Lemma 15. Let u, v, w be two intervals of D such that max(u) < min(w) and v ∈ I(u, w). Then, there exists a semi-good shortest path between u and w containing v.

Proof. Let P = u 0 . . . u k vu k+1 . . . w be a shortest path between u 0 = u and w that contains v. Now consider the path Q = u ′ 0 . . . u ′ k such that u ′ 0 = u and for 0 ≤ i ≤ k -1, u ′ i+1 is the rightmost neighbour of u ′ i . Observe that u ′ k intersects v and u ′ k does not intersect u k+1 (else, it contradicts the fact that P is a shortest path). Therefore, u ′ 0 . . . u ′ k vu k+1 . . . w is a semi-good shortest path containing v.

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.

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 ∈ R(T (z)). Proof. Let T = {a 1 , . . . , a j } be the set of intervals of T such that max(a i ) = min(a i+1 ) for i ∈ 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 , . . . , 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 , . . . , b k-j+1 , a 1 , . . . , a j , e T } induces a shortest path P ′ from o to e T such that V (T ) ⊆ V (P ′ ). Hence, T ⊆ I(o, e T ).

[j -1]. Let T (o) = {b 1 , . . . , b k } such that max(b i ) = min(b i+1 ) for i ∈ [k -1]. By
Lemma 17. Consider an implication gadget IM P [¬p → q]. We have that q ∈ I(p, s q ) and r q ∈ I(o, s q ). Proof. Consider the track T (p). Observe from the construction of IM P [¬p → q] that there exists a subset {v 1 , v 2 , . . . , v k+2 } ⊆ T (p) such that p and v 1 are adjacent, v i+1 is the rightmost neighbour of v i for 1 ≤ i ≤ k + 1 and v k is the leftmost neighbour of q. By Lemma 14, {p, v 1 , v 2 , . . . , 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 , . . . , 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 IM P [¬p → q] that there exists a subset {w 1 , w 2 , . . . , w t } ⊆ T (o) such that w 1 is the rightmost neighbour of o, w i+1 is the leftmost neighbour of v i for 1 ≤ i ≤ t -1, s q ∩ w t-1 = ∅, and s q ⊂ w t . By Lemma 14, the set {o, w 1 , w 2 , . . . , 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 , . . . , w t-1 , r q , s q } is a shortest path between o and s q .

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 ϕ : {x 1 , x 2 , . . . , x n } → {1, 0} be a satisfying assignment of F . Now, define the following sets. Let S 1 = {x i : ϕ(

x i ) = 1} ∪ {x i : ϕ(x i ) = 0}. Let S 2 = ∅. Now, for each clause C i = (ℓ 1 i , ℓ 2 i , ℓ 3 i ), do the following. 1. If ϕ(ℓ 1 i ) = 1, then put S 2 = S 2 ∪ a i , γ a ′ i , ℓ 1 i and if ϕ(ℓ 1 i ) = 0 then put S 2 = S 2 ∪ a ′ i , γ a i , ℓ 1 i . 2. If ϕ(ℓ 2 i ) = 1, then put S 2 = S 2 ∪ b i , γ b ′ i , ℓ 2 i and if ϕ(ℓ 2 i ) = 0 then put S 2 = S 2 ∪ b ′ i , γ b i , ℓ 2 i . 3. If ϕ(ℓ 3 i ) = 1, then put S 2 = S 2 ∪ c i , γ c ′ i , ℓ 3 i and if ϕ(ℓ 3 i ) = 0 then put S 2 = S 2 ∪ c ′ i , γ c i , ℓ 3 i . Let S = S 1 ∪ S 2 ∪ S p .
We shall show that S is a geodetic set of D. Due to Lemma 13, we have that

|S 1 ∪ S 2 ∪ S p | = 4 + 7n + 58m.
As S p ⊆ S, observe that o ∈ S and for each track T ∈ T , the point interval e T ∈ S. Hence, due to Lemma 16, we have that each track T ∈ T is covered by S.

Consider any variable gadget X i corresponding to the variable x i . Recall that from the construction,

X i = IM P [¬⊤ → x i ] ∪ IM P [¬x i → x i ]. Due to Lemma 17, we have that x i ∈ I(⊤, s xi ) and r xi ∈ I(o, s xi ). Hence, IM P [¬⊤ → x i ] ⊆ I(S). Now, consider the implication gadget IM P [¬x i → x i ].
Due to Lemma 17, we have that r xi ∈ I(o, s xi ). Since ϕ is a satisfying assignment, then either x i ∈ S or x i ∈ S. In the latter case, due to Lemma 17, r xi ∈ I(x i , s xi ). Hence, IM P [¬x i → x i ] ⊆ S, and therefore X i ⊆ I(S). Now, consider any clause

C i = (ℓ 1 i , ℓ 2 i , ℓ 3
i ) and recall the construction of C i . Since ϕ is a satisfying assignment, observe that, there exists at least one interval z ∈ {a i , b i , c i } ∩ S. Now due to Lemma 18, z ∈ I(d i , e T (z) ) and cov i ∈ I(z, f i ). Hence COV[i] ⊆ I(S). Now, consider the implication gadget IM P ¬a i → a ′ i . From our definition of S 2 , it follows that a i , a ′ i ∩ S ̸ = ∅. Now due to Lemma 17, a ′ i ∈ I(S) and r a ′ i ∈ I(S). Hence, IM P ¬a i → a ′ i ⊆ I(S). Repeating the above arguments for IM P ¬b i → b ′ i and IM P ¬c i → c ′ i , we infer that

IM P ¬a i → a ′ i ∪ IM P ¬b i → b ′ i ∪ IM P ¬c i → c ′ i ⊆ I(S)
Now, consider the AND gadgets AND a i , ℓ 1 i and AND a ′ i , ℓ 1 i . From our definition of S 2 , it follows that either a i , γ a

′ i , ℓ 1 i ⊆ S or a ′ i , γ a i , ℓ 1 i ⊆ S. First consider the case when a i , γ a ′ i , ℓ 1 i ⊆ S.
This means ϕ(ℓ 1 i ) = 1 and therefore ℓ 1 i ∈ S. Now invoking Lemma 19(a) and (b) (with p = a i and q = ℓ 1 i ), we have that AND a i , ℓ 1 i ⊆ I(S). Also, invoking Lemma 19(a) and (c) (p = a ′ i and q = ℓ 1 i ) we have that AND a ′ i , ℓ 1 i ⊆ I(S). The above arguments imply that when a i , γ a ′ i , ℓ 1 i ⊆ S, we have

AND a i , ℓ 1 i ∪ AND a ′ i , ℓ 1 i ⊆ I(S)
Similarly when a ′ i , γ a i , ℓ , we have that C i ⊆ I(S). This completes the proof.

Lemma 24. Let S * be a good geodetic set of D and AND [p, q] be an AND gadget where p is the only root of T (p) and q is the only root of T (q). Then, either {p, q} ⊆ S * , or S * contains at least one interval among {α (p, q), γ (p, q), δ (p, q)}.

Proof. Suppose that S * ∩ {α (p, q), γ (p, q), δ (p, q)} = ∅. Then, Lemma 15 implies that there exists a shortest path P containing α (p, 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 α (p, q) and max (u 1 ) < min (v 1 ). From the construction of AND [p, q] it follows that u 1 ∈ T (p). Since S * is a good geodetic set, our construction implies that p ∈ S * . Now, Lemma 15 implies that there exists a semi-good shortest path Q containing δ (p, q), whose endvertices lies in S * . Then, there must exist two intervals u 2 , v 2 in Q such that both u 2 , v 2 intersect δ (p, q) and max u 2 < min v 2 . From the construction of AND [p, q], it follows that either u 2 ∈ T (q) or u 1 = γ (p, q).

Consider the case when u 1 = γ (p, q). Since γ (p, q) / ∈ S * , there must exist an interval w 2 in Q such that γ (p, q) intersects w 2 and the distance between w 2 and v 2 is exactly three. But again from the construction of AND [p, q], it follow that no such w 2 exists, leading to a contradiction. Hence, u 2 ∈ T (q). Since S * is a good geodetic set, our construction implies that q ∈ S * . Lemma 25. Let S * be a good geodetic set of D and let

C i = (ℓ 1 i , ℓ 2 i , ℓ 3 i ) be a clause. Then we have (a) S * ∩ a i , a ′ i , α a i , ℓ 1 i , γ a i , ℓ 1 i , δ a i , ℓ 1 i , α a ′ i , ℓ 1 i , γ a ′ i , ℓ 1 i , δ a ′ i , ℓ 1 i ≥ 2, (b) S * ∩ b i , b ′ i , α b i , ℓ 2 i , γ b i , ℓ 2 i , δ b i , ℓ 2 i , α b ′ i , ℓ 2 i , γ b ′ i , ℓ 2 i , δ b ′ i , ℓ 2 i ≥ 2, and (
c) S * ∩ c i , c ′ i , α c i , ℓ 3 i , γ c i , ℓ 3 i , δ c i , ℓ 3 i , α c ′ i , ℓ 3 i , γ c ′ i , ℓ 3 i , δ c ′ i , ℓ 3 i ≥ 2.
Proof. Recall that C i contains the gadgets AND a i , ℓ 1 i and AND a ′ i , ℓ 1 i (along with some other gadegets). By Lemma 24, if a i / ∈ S * then we need at least one vertex among α a i , ℓ 1 i , γ a i , ℓ 1 i , δ a i , ℓ 1 i . The same holds when a i / ∈ S * , we need at least one among α a ′ i , ℓ 1 i , γ a ′ i , ℓ 1 i , δ a ′ i , ℓ 1 i . This implies that (a) holds. Using analogous arguments we can show that (b) and (c) holds.

Lemma 26. Let S * be a good geodetic set of D and C i = (ℓ 1 i , ℓ 2 i , ℓ

S * ∩ a i , a ′ i , α a i , ℓ 1 i , γ a i , ℓ 1 i , δ a i , ℓ 1 i , α a ′ i , ℓ 1 i , γ a ′ i , ℓ 1 i , δ a ′ i , ℓ 1 i ≥ 3
Now, using Lemma 25, we also have

S * ∩ b i , b ′ i , α b i , ℓ 2 i , γ b i , ℓ 2 i , δ b i , ℓ 2 i , α b ′ i , ℓ 2 i , γ b ′ i , ℓ 2 i , δ b ′ i , ℓ 2 i ≥ 2 and S * ∩ c i , c ′ i , α c i , ℓ 3 i , γ c i , ℓ 3 i , δ c i , ℓ 3 i , α c ′ i , ℓ 3 i , γ c ′ i , ℓ 3 i , δ c ′ i , ℓ 3 i ≥ 2
The above arguments imply that when a ′ i / ∈ S * , |S * ∩ C i | ≥ 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 * ∩ C i | ≥ 7. Now consider the case, when a ′ i , b ′ i , c ′ i ⊂ S * . Moreover, S * contains one interval from each of AND a i , ℓ 1 i , AND b i , ℓ 2 i and AND c i , ℓ 3 i . Now, we will be done by showing that at least one of a i , b i , c i , cov i must be in S * . Suppose that cov i / ∈ S * and let cov i ∈ I(u, v), where u, v ∈ S * and min(u) < min(v). Let P be a shortest path between u and v such that P contains cov i . Then, P must contain two distinct intervals w 1 and w 2 such that both w 1 , w 2 intersects 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 ∈ {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 C i . Lemma 27. If there is a geodetic set of D with cardinality 4 + 7n + 58m, then F is satisfiable. . This means that for each 1 ≤ i ≤ n, exactly one of x i , x i lies in S * . Based on these, we define the following truth assignment ϕ : {x 1 , . . . , x n } → {1, 0} of F . Define ϕ(x i ) = 1 if x i ∈ S * and ϕ(x i ) = 0, otherwise. Using Lemma 25 we can infer that for each 1 ≤ i ≤ m, we have that |S * ∩ C i | = 6. Due to Lemma 26, at least one of the intervals ℓ i 1 , ℓ i 2 , ℓ i 3 lies in S * . Thus, for at least one literal ℓ j i , we have that ϕ(ℓ j i ) = 1, as needed.

Completion of Proof of Theorem 2

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

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 [START_REF] Kellerhals | Parameterized complexity of geodetic set[END_REF] and [START_REF] Chakraborty | Hardness and approximation for the geodetic set problem in some graph classes[END_REF].)

Assuming the Exponential Time Hypothesis, our reduction implies that there cannot be a 2 o( √ 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 [START_REF] Bonnet | Optimality program in segment and string graphs[END_REF].)

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 [START_REF] Ahn | Well-partitioned chordal graphs[END_REF]-hard for parameter treewidth [START_REF] Kellerhals | Parameterized complexity of geodetic set[END_REF]. 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

  as any shorter path would imply the existence of a vertex y ∈ X such that d(u, y) + d(y, v) < d u + d v which would contradict the definition of A and B. As

  then, due to Definition 3(c), we know that there is a set B ⊇ A such that τ ext [B] = 1. Hence, there is a vertex b ∈ S τ v such that b = B and is adjacent to all vertices of A. Observe that w ∈ 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 ′ ∈ S τ v such that w ∈ I(w 1 , b ′ ). Hence, Definition 2(ii) is satisfied. Now, consider the vertex x. If x ∈ τ bag , then x ∈ D. Now, assume that x / ∈ τ bag . Then, due to Definition 3(e), we have sets A

y 2 ∈ 4 .

 24 D and we are done. Otherwise, assume without loss of generality that y 2 ∈ S τ1 u1 \ S τ u . There must be a set A ⊆ X u1 such that τ ext 1 [A] = 1 and y 2 = A. By Definition 5(b), either τ ext [A] = 1 or τ int 2 [A] = 1. If the first case is true, then there exists a y ′ 2 ∈ S τ v such that y is covered by y 1 and y ′ 2 in G ≤v . If the second case is true, then there is a vertex y ′ 2 ∈ sol [u 2 , τ 2 ] such that y ′ 2 is close to A with respect to X u2 . Due to Lemma 3, we have that y is covered by y 1 and y ′ 2 . The case where y ∈ (V (G ≤u2 ) \ X u2 ) ∪ τ cov 2 ) is symmetrical. If y ∈ Cov(u 1 , u 2 ), by its definition in Definition 5(c) and Lemma 3, y is covered by vertices in sol [v, τ ]. Hence, Definition 2(ii) is satisfied. By Conditions 5(d) and 5(e) we have that for any A ⊆ X v , τ int [A] = 1 if and only if τ int 1 [A] = 1 or τ int 2 [A] = 1. Therefore by induction Definition 2(iii) is satisfied. The minimality follows from Lemma 9. When v is the root node, the statement follows easily from Definition 6 and Lemma 10.

Figure 2 :

 2 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 S represents the start gadget, the box labelled E represents the end gadget. A box labelled C i represents the gadget for clause C i and a box labelled X j , the gadget for variable x j . Lines between such gadgets represent the tracks.

1 .

 1 Extension of existing tracks: For each track T ∈ 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 ′ ∈ T with T < T ′ , we have (T ∪ T new ) < (T ′ ∪ T ′ new ).

Figure 5 :

 5 Figure 5: The covering gadget COV[i]. For drawing purposes, the proportions of the intervals were changed. Nevertheless, the obtained interval graph is unchanged.

Figure 8 :

 8 Figure 8: The variable gadget X i created corresponding to the variable x i . The first implication gadget contains three special intervals named x i , r xi , s xi . The second implication gadget contains three special intervals named x i , r xi , s xi .

Lemma 16 .

 16 If T is a track in T , then T ⊆ I(o, e T ).

  Lemma 14, the path induced by the set {o, b 1 , . . . , 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.

  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 * | ≤ |S| ≤ 4 + 7n + 58m. Recall that a variable gadgetX i = IM P [¬⊤ → x i ] ∪ IM P [¬x i → x i ].Due to Lemma 23, we know that at least one among {x i , x i } lies in S * . Let S 1 = S * ∩ 1≤i≤n X i , and S 2 = S * ∩ 1≤i≤m C i . Let S p denote the set of point intervals in D. Note that S p ⊆ S * . We have |S 1 | ≥ n, |S 2 | ≥ 6m by Lemma 25, and |S p | = 4 + 6n + 52m. Therefore, |S 1 | = n as |S * | ≤ 4 + 7n + 58m

S 1 ]

 1 o, ⊤ IM P [¬⊤ → x1] IM P [¬x1 → x1] ¬⊤ → x2] IM P [¬x2 → x2] ¬⊤ → x3] IM P [¬x3 → x3] IM P ¬a1 → a ′ 1 AND [a1, x1] AND a ′ 1 , x 1 IM P ¬b1 → b ′ 1 AND [b1, x2] AND b ′ 1 , x2 IM P ¬c1 → c ′

  3 i ) be a clause. If none of ℓ i 1 , ℓ i 2 , ℓ i 3 is in S * then |S * ∩ C i | ≥ 7. Proof. Assume none of ℓ i 1 , ℓ i 2 , ℓ i 3 is in S * . Since ℓ 1 i / ∈ S *, due to Lemma 24, we have that at least one among α a i , ℓ 1 i , γ a i , ℓ 1 i , δ a i , ℓ 1 i lies in S * . If a ′ i / ∈ S * , then a i ∈ S * and one more interval from

	α a ′ i , ℓ 1 i , γ a ′ i , ℓ 1 i , δ a ′ i , ℓ 1

i lies in S * (Lemma 23 and 24). Therefore,

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.

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].

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 , . . . , x n and clauses C 1 , C 2 , . . . , C m . The set D will denote the set of constructed intervals, T will denote the tracks. For each i ∈ [n], X i shall denote the constructed variable gadget and for each j ∈ [m], 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 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 Lemma 18. Consider the cover gadget COV[i] and let z ∈ {a i , b i , c i }. Then, z ∈ I(d i , e T (z) ) and cov i ∈ I(z, f i ).

Proof. Let T denote the track T (z) and let T = {u 1 , u 2 , . . . , u k } such that u i+1 is the rightmost neighbour of u i for all 1 ≤ j ≤ k -1. Observe from the construction that the path induced by the set {d i , z, u 1 , u 2 , . . . , 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

(b) α (p, q) ∈ I(p, e T1 ), δ (p, q) ∈ I(q, e T3 ), and (c) α (p, q) ∈ I(β (p, q), γ (p, q)) and δ (p, q) ∈ I(γ (p, q), e T3 ).

Proof. First, we prove (a). Consider the track T (σ(p, q)). Observe from the construction that T (σ(p, q)) can be partitioned into two sets P a = {u 1 , u 2 , . . . , u j } and P ′ a = {u j+1 , u j+2 , . . . , u k } where u 1 is the rightmost neighbour of σ(p, q), u i+1 is the rightmost neighbour of u i for all 1 ≤ i ≤ k -1, and u j is the interval of T (σ(p, q)) with minimal index which intersects γ (p, q). Let z a be the rightmost neighbour of u k . Observe from the construction z a ∈ E and therefore e T2 is adjacent to z a . Hence, by Lemma 14, the path induced by Q a = {σ(p, q)} ∪ P a ∪ P ′ a ∪ {z a , e T2 } is a good shortest path between σ(p, q) and e T2 . Observe from the construction that |T 2 | = |P ′ |. Therefore, the set Q ′ a = {σ(p, q)} ∪ P a ∪ {γ (p, q)} ∪ T 2 ∪ {e T2 } has the same cardinality as Q a . Moreover, Q ′ a induces a path. This implies Q ′ a induces a shortest path between σ(p, q) and e T2 .

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 , . . . , v j ′ } and P ′ b = {v j ′ +1 , v j ′ +2 , . . . , v k ′ } where v 1 is the rightmost neighbour of p, v i+1 is the rightmost neighbour of v i for all 1 ≤ i ≤ k ′ -1, and v j ′ is the interval of T (p) with minimal index which intersects α (p, q). Let z b be the rightmost neighbour of v k ′ . Observe from the construction z b ∈ E and therefore e T1 is adjacent to z b . Hence, by Lemma 14, the path induced by

} is a good shortest path between p and e T1 . Observe from the construction that

b induces a path. This implies Q ′ b induces a shortest path between pq and e T1 . Using similar arguments, we can show that δ (p, q) ∈ I(q, e T3 ).

Finally, we prove (c). Observe from the construction that the distance between β (p, q) and δ (p, q) is two and therefore α (p, q) ∈ I(β (p, q), γ (p, q)). Let T 3 = {w 1 , w 2 , . . . , w k ′′ } such that w 1 is the rightmost neighbour of δ (p, q), w i+1 is the rightmost neighbour of w i for all 1 ≤ i ≤ k ′′ -1. Hence, by Lemma 14, the path induced by {δ (p, q), w 1 , w 2 , . . . , w k ′′ , e T3 } is a good shortest path. Now observe from the construction that the distance between w 1 is two and no neighbour of γ (p, q) is adjacent to w i for 2 ≤ i ≤ k ′′ . This implies that the path induced by the set {γ (p, q), δ (p, q), w 1 , w 2 , . . . , w k ′′ , e T3 } is a shortest path between γ (p, q) and e T3 . This completes the proof.

Lemma 20. If the 3-SAT instance F is satisfiable then I(D) has a geodetic set of cardinality 4 + 7n + 58m. Now, we shall show that if the geodetic number of D is at most 4 + 7n + 58m, then F is satisfiable. such that u belongs to a track with a root y. Let A 1 and A 2 be the sets of all γ (p, q) intervals and r q intervals in D, respectively. Let Lemma 16,[START_REF] Heggernes | Induced subgraph isomorphism on proper interval and bipartite permutation graphs[END_REF][START_REF] Hernando | On the steiner, geodetic and hull numbers of graphs[END_REF][START_REF] Kanté | Polynomial time algorithms for computing a minimum hull set in distancehereditary and chordal graphs[END_REF], observe that, A ∪ U ⊆ I(S p ). Therefore, we will be done by proving the following claim.

Claim 22. Let v be any interval in S. We have

To prove the claim, define S 1 = {w ∈ S : min(w) < min(u)} and S 2 = {w ∈ S : min(u) < min(w)}. First, assume that v ∈ S 1 and z be an interval in I(u, v) ∩ 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 IM P [¬p → q]. Then by Lemma 15, there exists a semigood shortest path Q between v and u containing q. From the construction of IM P [¬p → q], this is only possible if v = p. By Lemma 17, q ∈ I(p, s q ).

2. Assume z = cov i for some 1 ≤ i ≤ m. Using similar arguments as above and Lemma 18, we can show that v ∈ {a i , b i , c i } and therefore z ∈ I(v, f i ).

3. Assume z ∈ {α (p, q), δ (p, q)} for some AND gadget AND [p, q]. Using arguments as in Case 1 and Lemma 19, we can show that v ∈ {p, q} and therefore z ∈ I(v ∪ S p ).

The above cases imply that when v < u, then I(v, u) ⊂ I(v, u ′ ), where u ′ ∈ S \ {u}. Now assume that v ∈ S 2 and z ∈ I(u, v) ∩ 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 \ {u}) ∪ {y} is also a geodetic set of D. Arguing similarly for all intervals in S ∩ U , we have the lemma.

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 IM P [¬p → q] be an implication gadget where p is the only root of T (p). Then, either p ∈ S * or q ∈ S * .

Proof. Suppose q / ∈ 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 IM P [¬p → q], it follows that u 1 ∈ T (p). Since S * is a good geodetic set, our construction implies that p ∈ S * .

Conflict of Interest:

The authors declare that there is no conflict of interest.