On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909209159794688 |
|---|---|
| author | Bilò, Davide Colli, Giordano Forlizzi, Luca Leucci, Stefano |
| author_facet | Bilò, Davide Colli, Giordano Forlizzi, Luca Leucci, Stefano |
| contents | 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 \subseteq 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 < \frac{1}{2}$, no polynomial-time $(c \log n)$-approximation algorithm for the minimum MEG-set problem exists, unless $\mathsf{P} = \mathsf{NP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13875 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets Bilò, Davide Colli, Giordano Forlizzi, Luca Leucci, Stefano Computational Complexity Data Structures and Algorithms 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 \subseteq 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 < \frac{1}{2}$, no polynomial-time $(c \log n)$-approximation algorithm for the minimum MEG-set problem exists, unless $\mathsf{P} = \mathsf{NP}$. |
| title | On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.13875 |