On the (In)Approximability of the Monitoring Edge Geodetic Set Problem

The minimum \emph{Monitoring Edge-Geodetic Set} problem asks for a minimum vertex subset $M$ such that for every edge $e$ of the input graph $G$, there exist a two vertices $u,v \in M$, that monitor $e$, i.e. every shortest path between $u$ and $v$ in $G$ contains $e$. We prove that this problem c