More Results on the Complexity of Domination Problems in Graphs
International Journal of Information and Coding Theory, Vol. 4, pp. 129-144, 2017.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
Abstract. Given a graph G=(V,E) and an integer r>0, we call r-dominating code any subset C of V such that every vertex in V is at distance at most r from at least one vertex in C. We investigate, and locate in the complexity classes of the polynomial hierarchy, several problems linked with domination in graphs, such as, given r and G, the existence of, or search for, optimal r-dominating codes in G, or optimal r-dominating codes in G containing a subset of vertices X of V.
