Vol 3 No 1 (2008)
Articles

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

Sylvain Gravier
CNRS - Institut Fourier, ERT Maths à Modeler
Bio
Ralf Klasing
LaBRI - Université Bordeaux 1 - CNRS
Bio
Julien Moncel
INPG-ENSGI, Laboratoire G-SCOP
Bio
Published March 25, 2008
Keywords
  • approximation algorithms,
  • approximation hardness,
  • identifying codes,
  • locating-dominating codes,
  • fault tolerance,
  • domination problems,
  • combinatorial optimization,
  • graph algorithms.
  • ...More
    Less
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

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.