Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classesReportar como inadecuado

Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined identi ed by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identi ed, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of speci c graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree at least 3, the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard whereas in all previous works, their complexity was the same. We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set diff er.

Keywords : Approximation Test cover Separating system Identifying code Locating-dominating set NP-completeness Approximation.

Autor: Florent Foucaud -



Documentos relacionados