Minimal identifying codes in trees and planar graphs with large girth

Let GG be a finite undirected graph with vertex set V(G)V(G). If v∈V(G)v∈V(G), let N[v]N[v] denote the closed neighbourhood of vv, i.e. vv itself and all its adjacent vertices in GG. An identifying code in GG is a subset CC of V(G)V(G) such that the sets N[v]∩CN[v]∩C are nonempty and pairwise distinct for each vertex v∈V(G)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 NPNP-hard. We give a linear algorithm that solves it in the class of trees, but show that the problem remains NPNP-hard in the class of planar graphs with arbitrarily large girth.