Polyhedra associated with identifying codes in graphs

Abstract

The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra and present some general results on their combinatorial structure. We demonstrate how the polyhedral approach can be applied to find minimum identifying codes for special graphs, and discuss further lines of research in order to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.