On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets

Davide Bilò, Giordano Colli, Luca Forlizzi +1

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 minim…