More results on the complexity of identifying problems in graphs

We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r≥1r≥1 and a graph G=(V,E)G=(V,E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G   containing a subset of vertices X⊂VX⊂V. We locate these problems in the complexity classes of the polynomial hierarchy.