Given an undirected connected graph ๐บ = (๐ (๐บ), ๐ธ(๐บ)) on ๐ vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset ๐ โ ๐ (๐บ) of minimum cardinality such that, for every edge ๐ โ ๐ธ(๐บ), there exist ๐ฅ, ๐ฆ โ ๐ for which all shortest paths between ๐ฅ and ๐ฆ in ๐บ traverse ๐. We show that, for any constant ๐ < 1/2, no polynomial-time (๐ log ๐)-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.
On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets (short paper)
Bilo' D.;Colli G.;Forlizzi L.;Leucci S.
2024-01-01
Abstract
Given an undirected connected graph ๐บ = (๐ (๐บ), ๐ธ(๐บ)) on ๐ vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset ๐ โ ๐ (๐บ) of minimum cardinality such that, for every edge ๐ โ ๐ธ(๐บ), there exist ๐ฅ, ๐ฆ โ ๐ for which all shortest paths between ๐ฅ and ๐ฆ in ๐บ traverse ๐. We show that, for any constant ๐ < 1/2, no polynomial-time (๐ log ๐)-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
