Hardness and approximation for the geodetic set problem in some graph classes

In this paper, we study the computational complexity of finding the \emph{geodetic number} of graphs. A set of vertices $S$ of a graph $G$ is a \emph{geodetic set} if any vertex of $G$ lies in some shortest path between some pair of vertices from $S$. The $\text{textsc}MinimumGeodeticSet(MGS)$ problem is to find a geodetic set with minimum cardinality. In this paper, we prove that solving the $\text{textsc}MGS$ problem is NP-hard on planar graphs with a maximum degree six and line graphs. We also show that unless $P=NP$, there is no polynomial time algorithm to solve the $\text{textsc}MGS$ problem with sublogarithmic approximation factor (in terms of the number of vertices) even on graphs with diameter $2$. On the positive side, we give an $O(\sqrt[3]{n}\log n)$-approximation algorithm for the $\text{textsc}MGS$ problem on general graphs of order $n$. We also give a $3$-approximation algorithm for the $\text{textsc}MGS$ problem on the family of solid grid graphs which is a subclass of planar graphs.