Complexity Results for Identifying Codes in Planar Graphs
International Transactions in Operational Research, Vol. 17, pp. 691-710, 2010.
David AUGER, 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
{auger, charon, hudry, lobstein}@enst.fr
Abstract. Let G be a simple, undirected, connected graph with vertex set V(G) and C be a subset of vertices whose elements are called codewords. For v in V(G) and r a positive integer, let us denote by IrC(v) the set of codewords c in C such that d(v,c) is at most r, where the distance d(v,c) is defined as the length of a shortest path between v and c. More generally, for A a subset of V(G), we define IrC(A) as the union of the sets IrC(v), v in A, 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, C is said to be an (r,$\leq$l)-identifying code if one has IrC(A) $\neq$ IrC(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,$\leq$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 r>0. 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 r>0 and l in {1,2}.