2026-07-20T10:41:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24922 2026-02-09T08:02:06Z ddc:004 open_access

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem Bilò, Davide Colli, Giordano Forlizzi, Luca Leucci, Stefano Monitoring Edge Geodetic Set Inapproximability Approximation Algorithms We study the minimum Monitoring Edge Geodetic Set (MEG-Set) problem introduced in [Foucaud et al., CALDAM'23]: given a graph G, we say that an edge is monitored by a pair u,v of vertices if all shortest paths between u and v traverse e; the goal is to find a subset M of vertices of G such that each edge of G is monitored by at least one pair of vertices in M, and |M| is minimized. In this paper, we prove that all polynomial-time approximation algorithms for the minimum MEG-Set problem must have an approximation ratio of Ω(log n), unless 𝖯 = NP. To the best of our knowledge, this is the first non-constant inapproximability result known for this problem. We also strengthen the known NP-hardness of the problem on 2-apex graphs by showing that the same result holds for 1-apex graphs. This leaves open the question of determining whether the problem remains NP-hard on planar (i.e., 0-apex) graphs. On the positive side, we design an algorithm that computes good approximate solutions for hereditary graph classes that admit efficiently computable balanced separators of truly sublinear size. This immediately yields polynomial-time approximation algorithms achieving an approximation ratio of O(n^{1/4} √{log n}) on planar graphs, graphs with bounded genus, and k-apex graphs with k = O(n^{1/4}). On graphs with bounded treewidth, we obtain an approximation ratio of O(log^{3/2} n). This compares favorably with the best-known approximation algorithm for general graphs, which achieves an approximation ratio of O(√{n log n}) via a simple reduction to the Set Cover problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Giordano Colli and Luca Forlizzi and Stefano Leucci 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.14 urn:nbn:de:0030-drops-249226 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.14 eng https://creativecommons.org/licenses/by/4.0/legalcode