Linear formulation of identifying codes in graphs

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 and can be applied to locate fire in a building using sensors. Buildings are modelled by graphs with rooms as vertices. The placement of sensors in the rooms corresponds to choosing a subset of vertices. Finding a sensor-placement such that the location of a fire in one room can be precisely determined is equivalent to constructing an identifying code in the graph. These are dominating sets of vertices for which the closed neighbourhood of each vertex (i.e., the vertex and its neighbours) has a unique intersection with the set.

The problem of finding an identifying code has been widely studied. Yet its formulation as an integer linear problem hasn't been much considered.
Let G be a graph with vertex set V, to an identifying code $C\subseteq V$ of $G$ correspond weights x_u (x_u is 1 if u belongs to C, otherwise x_u is 0) satisfying the following : for all vertices u,v
* the sum of the x_w for w in the closed neighbourhood of u is at least 1
* the sum of the x_w for w in the symmetric difference of the closed neighbourhoods of u and v is at least 1.

Of course, it is interesting to find an identifying code with the smallest possible cardinality. But in general this is a NP-hard problem. A way to obtain bounds on the minimal cardinality is to consider the associated linear problem where the weights x_u are fractional.

In the case of vertex-transitive graphs, the minimal cardinality for the fractional case can only take two values which depend on the number of vertices, the degree of the graph and the smallest symmetric difference between any two closed neighbourhoods. We show that for an infinite family of graphs the bound is tight and for another another the bound is far too be reached.