Minimizing the Size of an Identifying or Locating-Dominating Code in a Graph is NP-Hard
Theoretical Computer Science, Vol. 290/3, pp. 2109-2120, 2003.
Irène CHARON, Olivier HUDRY, Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, hudry, lobstein}@infres.enst.fr
Abstract. Let G=(V,E) be an undirected graph and C a subset of vertices. If for all vertices v in V (respectively, in V \ C), the sets Br (v) $\cap$ C are all nonempty and different, where Br (v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.