Complexity results for identifying codes in planar graphs

Let G be a simple, undirected, connected graph with vertex set V(G) and ⊆V(G) be a set of vertices whose elements are called codewords. For v∈V(G) and r1, let us denote by I_r (v) the set of codewords c∈ such that d(v, c)r, where the distance d(v, c) is defined as the length of a shortest path between v and c. More generally, for A⊆V(G), we define, which is the set of codewords whose minimum distance to an element of A is at most r. If r and l are positive integers, is said to be an (r, l)-identifying code if one has I_r(A)≠I_r(A′) whenever A and A′ are distinct subsets of V(G) with at most l elements. We consider the problem of finding the minimum size of an (r, l)-identifying code in a given graph. It is already known that this problem is NP-hard in the class of all graphs when l=1 and r1. We show that it is also NP-hard in the class of planar graphs with maximum degree at most three for all (r, l) with r1 and l∈(1, 2). This shows, in particular, that the problem of computing the minimum size of an (r, 2)-identifying code in a given graph is NP-hard.