Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs

Authors

  • Sylvain Gravier CNRS - Institut Fourier, ERT Maths à Modeler
  • Ralf Klasing LaBRI - Université Bordeaux 1 - CNRS
  • Julien Moncel INPG-ENSGI, Laboratoire G-SCOP

Keywords:

approximation algorithms, approximation hardness, identifying codes, locating-dominating codes, fault tolerance, domination problems, combinatorial optimization, graph algorithms.

Abstract

In a graph G = (V, E), an identifying code of G (resp. a locating-dominating code of G) is a subset of vertices C ⊆ V such that N[v] ∩ C ≠ ∅ for all v ∈ V , and N[u] ∩ C ≠ N[v] ∩ C for all u ≠ v, u, v ∈ V (resp. u, v ∈ V [integerdivide] C), where N[u] denotes the closed neighbourhood of v, that is N[u] = N(u) ∪ {u}. These codes model fault-detection problems in multiprocessor systems and are also used for designing location-detection schemes in wireless sensor networks. We give here simple reductions which improve results of the paper [I. Charon, O. Hudry, A. Lobstein, Minimizing the Size of an Identifying or Locating-Dominating Code in a Graph is NP-hard, Theoretical Computer Science 290(3) (2003), 2109-2120], and we show that minimizing the size of an identifying code or a locating-dominating code in a graph is APX-hard, even when restricted to graphs of bounded degree. Additionally, we give approximation algorithms for both problems with approximation ratio O(ln |V |) for general graphs and O(1) in the case where the degree of the graph is bounded by a constant.

Author Biographies

Sylvain Gravier, CNRS - Institut Fourier, ERT Maths à Modeler

Chargé de recherche CNRS

Ralf Klasing, LaBRI - Université Bordeaux 1 - CNRS

Chargé de recherche CNRS

Julien Moncel, INPG-ENSGI, Laboratoire G-SCOP

Maître de conférences

Downloads

Published

2008-03-25

How to Cite

Gravier, S., Klasing, R., & Moncel, J. (2008). Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs. Algorithmic Operations Research, 3(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2808

Issue

Vol. 3 No. 1 (2008)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.