Identifying and Locating-Dominating Codes: NP-Completeness Results for Directed Graphs
IEEE Transactions on Information Theory, Vol. IT-48, pp. 2192-2200, August 2002.
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,A) be a directed, asymmetric graph and C a subset of vertices, and let Br-(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets Br-(v) $\cap$ C, for all vertices v in V (respectively, in V \ C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v in V only by knowing which codewords belong to Br-(v), and if C is r-locating-dominating, the same is true for the vertices in V \ C. We prove that, given a directed, asymmetric 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 greater than or equal to 1, and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.