Minimal identifying codes in trees and planar graphs with large girth

Let G be a finite undirected graph with vertex set V ( G ) . If v ∈ V ( G ) , let N [ v ] denote the closed neighbourhood of v , i.e.  v itself and all its adjacent vertices in G . An identifying code in G is a subset C of V ( G ) such that the sets N [ v ] ∩ C are nonempty and pairwise distinct for each vertex v ∈ V ( G ) . We consider the problem of finding the minimum size of an identifying code in a given graph, which is known to be N P -hard. We give a linear algorithm that solves it in the class of trees, but show that the problem remains N P -hard in the class of planar graphs with arbitrarily large girth.