On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets

Abstract

Given an undirected connected graph $G=(V(G),E(G))$ on $n$ vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset $M\subseteq V(G)$ of minimum cardinality such that, for every edge $e\in E(G)$, there exist $x,y\in M$ for which all shortest paths between $x$ and $y$ in $G$ traverse $e$. We show that, for any constant $c<\frac{1}{2}$, no polynomial-time $(c\log n)$-approximation algorithm for the minimum MEG-set problem exists, unless $\mathsf{P}=\mathsf{NP}$.