The Complexity of the Identifying Code Problem in Restricted Graph Classes

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its nonempty neighbourhood within the identifying code. We study the associated computational problem

Minimum Identifying Code

, which is known to be

NP

-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Though the problem is approximable within a logarithmic factor, it is known to be 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. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), it is hard to approximate within some constant factor. We summarize known results in the area, and we compare them to the ones for the related problem

Minimum Dominating Set

. In particular, our work exhibits important graph classes for which

Minimum Dominating Set

is efficiently solvable, but

Minimum Identifying Code

is hard (whereas in all previously studied classes, their complexity is the same). We also introduce a graph class for which the converse holds.