pipette
ENEnglish

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

Davide Bil\`o, Giordano Colli, and Stefano Leucci

Preprint

En palabras de los autores

We study the Monitoring Edge-Geodetic Set problem (MEG-Set), which asks for a minimum-cardinality set of vertices of an undirected graph of vertices such that every edge of belongs to all shortest paths between some pair of vertices in . We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time -approximation algorithm, improving upon the previously best-known approximation ratio. On the negative side, for every constant , we prove that the problem admits no polynomial-time -approximation algorithm, unless . This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is -hard on planar -degenerate graphs, whereas -hardness was previously known for -apex -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 . Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 18 pages, 4 figures