Covering problems in graphs: identifying codes and its fractional relaxation

Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin in 1998 to model fault-diagnosis in multiprocessor systems. An identifying code is a dominating set of vertices for which the closed neighbourhood of each vertex 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 has not been much considered. In this talk, we will compare this problem with its fractional relaxation and we will focus on the particular case of vertex-transitive graphs.