Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs

In a graph G = (V, E), an identifying code of G (resp. a locating-dominating code of G) is a subset of vertices C ⊆ V such that N[v] ∩ C ≠ ∅ for all v ∈ V, and N[u] ∩ C ≠ N[v] ∩ C for all u ≠ v, u, v ∈ V (resp. u, v ∈ V [integerdivide] C), where N[u] denotes the closed neighbourhood of v, that is N[u] = N(u) ∪ {u}. These codes model fault-detection problems in multiprocessor systems and are also used for designing location-detection schemes in wireless sensor networks. We give here simple reductions which improve results of the paper by Charon, Hudry, and Lobstein, and we show that minimizing the size of an identifying code or a locating-dominating code in a graph is APX-hard, even when restricted to graphs of bounded degree. Additionally, we give approximation algorithms for both problems with approximation ratio O(ln |V|) for general graphs and O(1) in the case where the degree of the graph is bounded by a constant.