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^-(v) ∩ 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, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.