Network failure detection and graph connectivity
Jon M. Kleinberg, Mark B. Sandler, Aleksandrs Slivkins · 2004
We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with £¥¤§¦©¨� � detecting-failures: events in which an adversary deletes up ¨ to network elements (nodes or edges), after which there are two sets of � nodes � and, each at least ¤ an fraction of the network, that are disconnected from one another. We say that a � set of nodes is an-detection set if, for any £¥¤§¦©¨� �-failure of the network, some two nodes in � are no longer able to communicate; in this � way, “witnesses ” any such failure. Recent results show that for any � graph, there is £�¤§¦©¨� � an-detection set of size bounded by a polynomial ¨ in ¤ and, independent of the size � of. In this paper, we expose some relationships between bounds on detection sets and the � edge-connectivity and � node-connectivity of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can ¨ delete edges, there is always a detection set of ��£������������� � size which can be found by random sampling. Moreover, £�¤§ ¦ � an-detection set of minimum size (which is at � � most) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of � but also of the value of � Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of �� £ � � ���� � � � � nodes is a detection set for adversaries that can delete a number of nodes up to � , the node-connectivity. For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph. 1