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

Preprint · Davide Bilò, Giordano Colli, Stefano Leucci

- Archive id: arxiv:2610.27935
- Published: 2026-10-20
- arXiv: https://arxiv.org/abs/2610.27935
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.27935
- PDF: https://arxiv.org/pdf/2610.27935
- Provenance: arxiv

## Abstract

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/3}\\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\\sqrt{n\\log n})$ approximation ratio. On the negative side, for every constant $\\varepsilon \\in (0,1)$, we prove that the problem admits no polynomial-time $\\big(2^{\\log^{1-\\varepsilon} n}\\big)$-approximation algorithm, unless $\\mathsf{NP}\\subseteq \\mathsf{DTIME}(n^{\\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \\megset is $\\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\\mathsf{NP}$-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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.