Complexity results for identifying codes in planar graphs
David Auger, Irène Charon, Olivier Hudry, Antoine C. Lobstein · International Transactions in Operational Research · 2010
Abstract 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 r 1, 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 r 1. 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 1 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.