Title: More results on the complexity of domination problems in graphs

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.

DOI: 10.1504/IJICOT.2017.083829

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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article