More Results on the Complexity of Identifying Problems in Graphs
Theoretical Computer Science, Vol. 626, pp. 1-12, 2016.
Olivier HUDRY, Antoine LOBSTEIN
Centre National de la Recherche Scientifique / LTCI Laboratoire de Traitement et Communication de l'Information
Institut Télécom - Télécom ParisTech
46 rue Barrault, 75634 Paris cédex 13, France
{hudry, lobstein}@infres.enst.fr
Abstract. We investigate the complexity of several problems linked with identification in graphs; for instance, given an integer r and a graph G=(V,E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a given subset of vertices. We locate these problems in the complexity classes of the polynomial hierarchy.