Computing the geodesic number of a graph

Let $G = (V, E)$ be a simple, undirected graph. $S \subseteq V(G)$ is an \emph{interval set} in geodesic convexity if, for every $w \in V \setminus S$, there exist $u, v \in S$ such that $w$ is an internal vertex of some $u,v$-shortest path ($u,v$-geodesic). The \emph{interval number} of $G$ in geodesic convexity, denoted by $\ing(G)$, is the smallest cardinality of an interval set of $G$. This parameter is also known in the literature as the \emph{geodesic number}. Determining the geodesic number of a graph is an $\NP$-Hard problem, even when the input graph is bipartite~\citep{Dourado2010}. In this work, two mathematical formulations are proposed to determine this parameter, one exponential and the other compact. We conduct computational experiments, using CPLEX, to evaluate and compare their performances on randomly generated instances.