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 < 12 , no polynomial-time ( log )-approximation algorithm for the minimum MEG-set problem exists, unless P = NP.
In this paper, we show that the problem of finding a MEG-set of minimum size is not approximable within a factor of ln , where < 12 is a constant of choice, unless P = NP.
Lemma 1. Let be a vertex of degree 1 in . Vertex belongs to all MEG-sets of . Proof. Assume towards a contradiction that some MEG-set ⊆ () ∖ {} of exists. Let {, } with , ∈ be a pair of vertices that monitors the unique edge incident to . Since {, } ∩ {} = ∅, all shortest path from to in contain as an internal vertex, thus must have at least two incident edges, contradicting the hypothesis of the lemma. Lemma 2. Let be a vertex of degree 1 in and let be its sole neighbor. If | ()| ≥ is a MEG-set of then ∖ {} is a MEG-set of . 3 and Proof. From Lemma 1 we know that ∈ . We start by observing that {, } only monitors edge (, ) and, since |()| ≥ | ()| − 1 ≥ 2, there must exist some vertex ∈ ∖ {, }.
Since (, ) is a bridge of , it is traversed by all paths between and any vertex in ()∖{} and, in particular, it is monitored by {, }.
We now turn our attention to the edges in ∖ {(, )} and show that any such edge that is monitored by {, }, with ∈ , is also monitored by {, }. Notice, since ̸= (, ), we have ̸= . Consider any shortest path from to in and observe that consists of the edge (, ) followed by a path ′ from to . By suboptimality of shortest paths, ′ is a shortest path from to in . Since {, } monitors , ′ contains and so does . Thus, {, } monitors .
We reduce from the Set Cover problem. A Set Cover instance ℐ = ⟨, ⟩ is described as a set of items = {1, . . . , }, and a collection = {1, . . . , ℎ} of ℎ ≥ 2 distinct subsets of , such that each subset contains at least two items and each item appears in at least two subsets.1 The goal is that of computing a collection * ⊆ of minimum size such that ∪∈* = .2
It is known that, unless P = NP, the Set Cover problem is not approximable within a factor of (1 − ) ln |ℐ|, where > 0 is a constant and |ℐ| is the size of the Set Cover instance [7].
Given an instance ℐ = ⟨, ⟩ of Set Cover, we can build an associated bipartite graph whose vertex set ( ) is ∪ and such that contains edge (, ) if and only if ∈ . We define = ℎ + . Observe that |ℐ| ≥ . 1This can be guaranteed w.l.o.g. by repeatedly reducing the instance by applying the first applicable of the following two reduction rules. Rule 1: if there exists an item that is contained by a single subset , then belongs to all feasible solutions, and we reduce to the instance in which both and have been removed. Rule 2: if there exists a subset that contains a single element, then (due to Rule 1) there is an optimal solution that does not contain , and we reduce to the instance in which has been removed. Notice that this process can only decrease the values of and ℎ. 2We assume w.l.o.g. that ∪=1 = , i.e., that a solution exists.
ℎ S1,1
S2,1
S3,1
S4,1
H1
S1,2
S2,2
S3,2
S4,2
H2 x1,1 x2,1 x3,1 x4,1 x5,1 x1,2 x2,2 x3,2 x4,2 x5,2 y1 y2 y3 y4
y5 y1′ y2′ y3′ y4′ y5′ Figure 1: The graph obtained by applying our reduction with = 2 to the Set Cover instance ℐ = ⟨, ⟩ with = 5, ℎ = 4, 1 = {1, 2, 3}, 2 = {2, 3}, 3 = {2, 4, 5}, and 4 = {3, 5}. To reduce clutter, the edges of the clique induced by the vertices (in the gray area) are not shown.
Let be an integer parameter, whose exact value will be chosen later, that satisfies 2 ≤ = (poly( )). We construct a graph that contains copies 1, . . . , of as induced subgraphs. In the following, for any ℓ = 1, . . . , , we denote by ,ℓ and ,ℓ the vertices of ℓ corresponding to the vertices and of , respectively. More precisely, we build by starting with a graph that contains exactly the copies 1, . . . , of and augmenting it as follows (see Figure 1): • For each item ∈ , we add two new vertices , ′ along with the edge (, ′) and all the edges in {(,ℓ, ) | ℓ = 1, . . . , }; • We add all the edges (, ′ ) for all 1 ≤ ≤ ′ ≤ , so that the subgraph induced by 1, . . . , is complete. • For each set ∈ , we add two new vertices , ′ along with the edge ( , ′ ), and all the edges in {(,ℓ, ) | ℓ = 1, . . . , }.
Observe that the number of vertices of satisfies = 2ℎ + 2 + ( + ℎ) = ( + 2)( + ℎ) = ( + 2) .
Let = { | = 1, . . . , }, ′ = {′ | = 1, . . . , }, = { | = 1, . . . , ℎ}, and ′ = { | = 1, . . . , ℎ}. Moreover, define as the set of all vertices of degree 1 in , i.e., = ′ ∪ ′. By Lemma 1, the vertices in belong to all MEG-sets of .
Lemma 3. monitors all edges having both endvertices ∪ ′ ∪ ∪ ′.
Proof. Observe that all shortest paths from ′ ∈ (resp. ′ ∈ ) to any other vertex ∈ ∖{′} (resp. ∈ ∖ {′ }) must traverse the sole edge incident to ′ (resp. ′), namely (′, ) (resp. ′ , ). Since || ≥ 2, such a always exists, and all edges incident to are monitored by .
The only remaining edges are those with both endpoints in . Let (, ′ ) be such an edge. Since the only shortest path between ′ and ′′ in is ⟨′, , ′ , ′′ ⟩, the pair {′, ′′ } monitors (, ′ ).
Lemma 4. Let 1, . . . , be (not necessarily distinct) set covers of ℐ. The set = ∪ {,ℓ | ∈ ℓ, 1 ≤ ℓ ≤ } is a MEG-set of .
Proof. Since ⊆ , by Lemma 3, we only need to argue about edges with at least one endvertex in some ℓ, with 1 ≤ ℓ ≤ . Let ∈ ℓ, and consider any ∈ . Edge (,ℓ, ) is monitored by {′ , ,ℓ}. Edges (,ℓ, ,ℓ) and (,ℓ, ) are monitored by {,ℓ, ′}.
The only remaining edges with at least one endvertex in ℓ are those incident to vertices ,ℓ with ∈ ∖ ℓ. Consider any such , let be an item in , and let ∈ ℓ be any set such that ∈ (notice that both and exist since sets are non-empty and ℓ is a set cover). Edge (,ℓ, ,ℓ) is monitored by {,ℓ, ′ }, which also monitors (,ℓ, ).
We say that a MEG-set is minimal if, for every ∈ , ∖ {} is not a MEG-set. Lemma 2 ensures that any minimal MEG-set does not contain any of the vertices , for = 1, . . . , , or for = 1, . . . , ℎ. Hence, ∖ contains only vertices in ⋃︀ ℓ=1 (ℓ).
Lemma 5. Let be a minimal MEG-set of . For every = 1, . . . , and every ℓ = 1, . . . , , contains at least one among ,ℓ and all ,ℓ such that ∈ .
The proof of Lemma 5 is given in the full version of this work [8].
Lemma 6. Given a MEG-set ′ of , we can compute in polynomial time a MEG-set of such that | | ≤ | ′| and, for every ℓ = 1, . . . , , the set ℓ = { ∈ | ,ℓ ∈ } is a set cover of ℐ.
Proof. Let ′′ be a minimal MEG-set of that is obtained from ′ by possibly discarding some of the vertices. Clearly | ′′| ≤ | ′| and ′′ can be computed in polynomial time. Moreover, by Lemma 5, for every = 1, . . . , and every ℓ = 1, . . . , , ′′ contains ,ℓ or some ,ℓ such that covers . We compute from ′′ by replacing each ,ℓ ∈ ′′ with ,ℓ, where ∈ is any set that covers . As a consequence, for every ℓ = 1, . . . , , the set ℓ = { ∈ | ,ℓ ∈ } is a set cover of ℐ. Moreover, since ′′ contains all vertices in by Lemma 1, so does . Then, Lemma 4 implies that is a MEG-set of .
Lemma 7. Let > 0 be a constant of choice. Any polynomial-time ( ln )-approximation algorithm for the minimum MEG-set problem, where > 0 is a constant, implies the existence of a polynomial-time ((2 + ) ln )-approximation algorithm for Set Cover.
Proof. Given an instance ℐ = ⟨, ⟩ of Set Cover and let ℎ* be the size of an optimal set cover of ℐ. In the rest of the proof we assume w.l.o.g. that ≥ 4 and ℎ* ≥ 4 . Indeed, if any of the above two conditions does not hold, we can solve ℐ in constant time.
We now construct the graph with = ( + 2) ≤ 2 vertices by making = − 2 copies of . Next, we run the ( ln )-approximation algorithm to compute a MEG-set ′ of , and we use Lemma 6 to find a MEG-set with | | ≤ | ′| that contains set covers 1, . . . , in polynomial time. Among these set covers, we output one ′ of minimum size.
To analyze the approximation ratio of the above algorithm, let * be an optimal MEG-set of . Lemma 4 ensures that | * | ≤ | | + ℎ* = + ℎ* , and hence
| | ≤ | ′| ≤ ( + ℎ* ) ln = ( + ℎ* ) ln 2 = 2ℎ * ln + 2 ln . Therefore we have: |′| ≤ | | ≤ 2ℎ * ln + 2 ln ︂( 2 + 4 )︂ ℎ* ≤ 2ℎ * ln + 4 ln = ℎ* ln ≤ (2 + )ℎ* ln .
Let be any positive constant. Since Set Cover cannot be approximated in polynomial time within a factor of (1 − ) ln |ℐ|, unless P = NP [7], and since an invocation of Lemma 7 with = 12 − and = shows that any polynomial-time (( 12 − ) ln )-approximation algorithm for the minimum MEG-set problem can be turned into a polynomial-time approximation algorithm for Set Cover with an approximation ratio of (1 − ) ln ≤ (1 − ) ln |ℐ|, we have: Theorem 1. The minimum MEG-set problem cannot be approximated in polynomial time within a factor of ln , for any constant < 12 , unless P = NP.
In this work we present inapproximability results on the minimum MEG-set problem, proving that the problem is APX-hard and not approximable within a factor of ln , for any constant < 12
. Observe that it is not hard to devise an eficient approximation algorithm for the minimum MEG-set achieving an approximation ratio of (√ · ln ) based on the well-known approximation algorithm for the Set Cover [9]. It is an open problem to narrow the gap between the lower and upper bounds on approximability of minimum MEG-set. Moreover, it could be interesting to study the approximability of the problem on specific classes of graphs. [2] J. Haslegrave, Monitoring edge-geodetic sets: Hardness and graph products, Discret. Appl. [3] F. Foucaud, P. Marcille, Z. M. Myint, R. B. Sandeep, S. Sen, S. Taruni, Monitoring edgegeodetic sets in graphs: Extremal graphs, bounds, complexity, in: S. Kalyanasundaram, A. Maheshwari (Eds.), Algorithms and Discrete Applied Mathematics - 10th International Conference, CALDAM 2024, Bhilai, India, February 15-17, 2024, Proceedings, volume 14508 of Lecture Notes in Computer Science, Springer, 2024, pp. 29–43. URL: https://doi.org/10.1007/ 978-3-031-52213-0_3. doi:10.1007/978-3-031-52213-0\_3. [4] A. Tan, W. Li, X. Wang, X. Li, Monitoring edge-geodetic numbers of convex polytopes and four networks, Int. J. Parallel Emergent Distributed Syst. 38 (2023) 301–312. URL: https://doi.org/10.1080/17445760.2023.2220143. doi:10.1080/17445760.2023.2220143. [5] R. Ma, Z. Ji, Y. Yao, Y. Lei, Monitoring-edge-geodetic numbers of radix triangular mesh and sierpiński graphs, Int. J. Parallel Emergent Distributed Syst. 39 (2024) 353–361. URL: https://doi.org/10.1080/17445760.2023.2294369. doi:10.1080/17445760.2023.2294369. [6] X. Xu, C. Yang, G. Bao, A. Zhang, X. Shao, Monitoring-edge-geodetic sets in product networks, Int. J. Parallel Emergent Distributed Syst. 39 (2024) 264–277. URL: https://doi. org/10.1080/17445760.2024.2301929. doi:10.1080/17445760.2024.2301929. [7] I. Dinur, D. Steurer, Analytical approach to parallel repetition, in: D. B. Shmoys (Ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, ACM, 2014, pp. 624–633. URL: https://doi.org/10.1145/2591796.2591884. doi:10.1145/ 2591796.2591884. [8] D. Bilò, G. Colli, L. Forlizzi, S. Leucci, On the inapproximability of finding minimum monitoring edge-geodetic sets, 2024. arXiv:2405.13875. [9] G. Colli, Monitoring graph edges via shortest paths: computational complexity and approximation algorithms, Tesi di laurea, University of L’Aquila, 2023.