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 subset of 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 < 1/2, no polynomial-time (c log n)-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 G = (V(G), E(G)) on n vertices, the minimum Monitoring Edge-Geodetic Set (MEG-set) problem asks to find a subset M subset of 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 < 1/2, no polynomial-time (c log n)-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
paper110.pdf
accesso aperto
Tipologia:
Documento in Versione Editoriale
Licenza:
Creative commons
Dimensione
1.29 MB
Formato
Adobe PDF
|
1.29 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
