Connected Identifying Codes
Niloofar Fazlollahi, David Starobinski, Ari Trachtenberg · IEEE Transactions on Information Theory · 2012
We consider the problem of generating a connected identifying code for an arbitrary graph. After a brief motivation, we show that the decision problem regarding the existence of such a code is NP-complete, and we propose a novel polynomial-time approximation ConnectID that transforms any identifying code into a connected version of at most twice the size, thus leading to an asymptotically optimal approximation bound. When the input identifying code to is robust to graph distortions, we show that the size of the resulting connected code is related to the best error-correcting code of a given minimum distance, permitting the use of known coding bounds. In addition, we show that the size of the input and output codes converge for increasing robustness, meaning that highly robust identifying codes are almost connected. Finally, we evaluate the performance ConnectID of on various random graphs. Simulations for Erdos-Rényi random graphs show that the connected codes generated are actually at most 25% larger than their unconnected counterparts, while simulations with robust input identifying codes confirm that robustness often provides connectivity for free.