Identifying codes and the set cover problem - 10/06/2006

Moshe Laifenfeld

We consider the problem of finding a minimum identifying code in a graph, i.e., a designated set of vertices whose neighborhoods uniquely overlap atany vertex on the graph. This identifying code problem was initially introduced in 1998 and has been since fundamentally connected to a wide range of applications, including fault diagnosis, location detection, environmental monitoring, and connections to information theory, superimposed codes, and tilings. Though this problem is NP- complete, its known reduction is from 3-SAT and does not readily yield an approximation algorithm. In this paper we show that the identifying code problem is computationally equivalent to the set cover problem and present \Theta(\logn)-approximation algorithm based on the greedy approach for set cover; we further show that, subject to reasonable assumptions, no polynomial-time approximation algorithm can do better.

This is joint work with Ari Trachtenberg and Tanya Berger-Wolf.