We investigate the computational complexity of finding the geodetic number of graphs on chordal and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic set} if every vertex of $G$ lies on a shortest path between some pair of vertices in $S$. The \textsc{Minimum Geodetic Set (MGS)} problem aims to find a geodetic set with minimal cardinality for a given graph. We show that \textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. We also demonstrate that \textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thus answering a question posed by Ekim et al. (LATIN, 2012), who showed that \textsc{Minimum Geodetic Set} is solvable in polynomial time on proper interval graphs. Given the constraints of interval graphs, we employ a sophisticated reduction technique to navigate around their inherent linear structure to prove the latter result.
Blogger's Review: This paper reveals the complexity of geodetic sets in specific classes of graphs, particularly contrasting fixed parameter tractability with NP-hardness. Such complexity analysis provides a crucial theoretical foundation for subsequent algorithm designs, warranting further investigation.