Identifying Codes and the Set Cover Problem

Abstract

We consider the problem of finding a minimum identifying code in a graph, i.e., a designated set of vertices whose neighborhoods uniquely overlap at any 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 a Θ(log n)-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. Finally, we show that a generalization of the identifying codes problem, for which no complexity results were known thusfar, is NP-hard. 1