On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
<|reference_start|>On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets: 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}$.<|reference_end|>
@article{bilò2024on,
    title={On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic
  Sets},
    author={Davide Bil`o, Giordano Colli, Luca Forlizzi, Stefano Leucci},
    journal={arXiv preprint arXiv:2405.13875},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13875},
    primaryClass={cs.CC cs.DS}
}