Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem

We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1\mathrm{/}3}{\log }^{2\mathrm{/}3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\epsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\left(2^{{\log }^{1-\epsilon }n}\right)$-approximation algorithm, unless $\mathsf{N}\mathsf{P}\subseteq \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}(n^{\mathrm{polylog}n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{N}\mathsf{P}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{N}\mathsf{P}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.