Authors: Olivier Hudry; Antoine Lobstein
Addresses: Département INFRES Institut Télécom - Télécom ParisTech, 46, rue Barrault, 75634 Paris Cedex 13, France ' Centre National de la Recherche Scientifique, Laboratoire de Recherche en Informatique, UMR 8623, Bâtiment 650, Université Paris-Sud, 91405 Orsay Cedex, France
Abstract: Given a graph G = (V, E) and an integer r ≥ 1, 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 ⊂ V .
Keywords: complexity; complexity classes; covering radius; dominating codes; graph theory; hardness; NP-completeness; polynomial hierarchy.
International Journal of Information and Coding Theory, 2017 Vol.4 No.2/3, pp.129 - 144
Received: 05 Sep 2016
Accepted: 05 Sep 2016
Published online: 24 Apr 2017 *