Bounds on the maximal number of corrupted nodes via Boolean Network Tomography

In this thesis we are concentrating on identifying defective items in larger sets which is a main problem with many applications in real life situations, e.g., fault diagnosis, medical screening and DNA screening. We consider the problem of localizing defective nodes in networks through an approach based on Boolean Network Tomography (BNT), which is grounded on inferring informations from the Boolean outcomes of end-to-end measurement paths. In particular, we focus on the following three: • Studying Maximal Identifiability, which was recently introduced in BNT to measure the maximal number of corrupted nodes which can be uniquely localized in sets of end-to-end measurement paths on networks; • Central role of Vertex-Connectivity in maximal identifiability; • Investigating identifiability conditions on the set of paths which guarantee discovering or counting unambiguously the defective nodes and contributing this problem both from a theoretical and applied perspective. We prove tight upper and lower bounds on the maximal identifiability for sets of end-to-end paths in network topologies obtained from trees and d-(dimensional) grids over n^d nodes. For trees (both directed and undirected) we show that the maximal identifiability is 1. For undirected d-grids we prove that, using only 2d monitors, maximal identifiability is at least d − 1 and at most d. In the directed case proving that the maximal identifiability is d and can be reached at the cost of placing 2d(n − 1) + 2 monitors on the d-grid. This monitor placement is optimal and adding more monitors will not increase the identifiability. We also study maximal identifiability for directed topologies under embeddings establishing new relations with embeddability, graph dimension and proving that under the operation of transitive closure maximal identifiability grows linearly. Our results suggest the design of networks over n nodes reaching maximal identifiability Ω(log n) using O(log n) monitors and an heuristic to boost maximal identifiability increasing the minimal degree of the network which we test experimentally. Moreover we prove tight bounds on the maximal identifiability first in a particular class of graphs, the Line of Sight networks and then slightly weaker bounds for arbitrary networks. Furthermore we initiate the study of maximal identifiability in random networks. We investigate two models: the classical Erdős-Rényi model, and that of Random Regular graphs. The proposed framework allows a probabilistic analysis of the identifiability in random networks giving a tradeoff between the number of monitors to place and the maximal identifiability. Further in this thesis, we work on the precise tradeoff between number of nodes and number of paths such that at most k nodes can be identified unambiguously. The answer to this problem is known only for k = 1 and we answer it for any k, setting a problem implicitly left open in previous works. We focus on upper and lower bounds on the number of unambiguously identifiable nodes, introducing new identifiability measures (Separability and Distinguishability) which strictly imply and are strictly implied by the notion of identifiability introduced in [39]. We utilize these new measures to design algorithmic heuristics to count failure nodes in a fine-grained way and further to prove the first complexity hardness results on the problem of identifying failure nodes in networks via BNT. At last but not least, we introduce a random model so as to achieve lower bounds on the number of unambiguously identifiable defective nodes. We use this model to approximate that number on real networks by a maximum likelihood estimate approach.