More Results on the Complexity of Identifying Problems in Graphs

Olivier Hudry (1, 2) , Antoine Lobstein (1, 2)

1 MC2 - Mathématiques discrètes, Codage et Cryptographie
2 INFRES - Département Informatique et Réseaux

We investigate the complexity of several problems linked with identification in graphs, such as, given an integer r >= 1 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.

Mots clés: NP-Completeness; Hardness; Identifying Codes; Twin-Free Graphs.; Graph Theory; Complexity; Complexity Classes; Polyno- mial Hierarchy

Domaines: Complexité [cs.CC]; Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Olivier Hudry, Antoine Lobstein. More Results on the Complexity of Identifying Problems in Graphs. Theoretical Computer Science, 2016, 626, pp.1-12. ⟨hal-02287134⟩