Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G = (V, A) be a directed, asymmetric graph and C a subset of vertices, and let B_r^- (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 B_r^- ∩ C, v ∈ V (respectively, v ∈ 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 ∈ V only by knowing which codewords belong to B_r^- (v), and if C is r-locating-dominating, the same is true for the vertices v 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 ≥ 1 and remains so even when restricted to strongly connected, directed, asymmetric, bi-partite graphs or to directed, asymmetric, bipartite graphs without directed cycles.