# On the Approximation Hardness of Geodetic Set and its Variants

Jocelyn Thiebaut, 14 Feb 2022

Given a graph \(G\), a geodetic set (resp. edge geodetic set) is a subset \(X\) of its vertices such that every vertex (resp. edge) of \(G\) is on a shortest path between two vertices of \(X\). A strong geodetic set is a subset \(X\) of vertices AND a choice of a shortest path for every pair of vertices of \(X\) such that every vertex is on one of these shortest paths. The geodetic number (resp. edge geodetic number) of a graph is the minimum size of a geodetic set (resp. edge geodetic set) and the strong geodetic number is the minimum size of a strong geodetic set. In this work we prove that geodetic number and edge geodetic number are both \(\mathsf{LOG-APX}\)-hard, even on subcubic bipartite graphs with arbitrarily high girth. Then, we show that there is no \(\frac{781}{780}\) polynomial-time approximation algorithm for strong (edge) geodetic number, even on subcubic bipartite graphs with arbitrarily high girth. We also prove that, given a subset of vertices, it is \(\mathsf{NP}\)-hard to determine whether it is a strong geodesic set. Therefore, it is natural to study the problem of maximizing the number of covered vertices by a choice of a shortest path for every pair of a provided subset of vertices. We provide a tight \(2\)-approximation algorithm to solve this problem. Finally, we disprove a conjecture of Iršič and Konvalinka by proving that the strong geodetic number can be computed in polynomial time in complete multipartite graphs.

Joint work with Tom Davot and Lucas Isenmann