The complexity of boolean failure identification

We consider the problem of identifying failure nodes in networks under the Boolean Network Tomography (BNT) approach, which is based on end-to-end measurements routed in a network along paths and producing a boolean (failure/not-failure) outcome. Such end-to-end measurements paths are usually described by an incidence boolean matrix M with m rows (the measurements paths) and n columns (the nodes of the network). A key notion used in practice in this approach is that of k-identifiability. Loosely speaking, a set of m boolean measurements paths over n nodes is k-identifiable, where k is a non-negative integer, if, whenever there are fewer than k+1 failures, it is always possible to identify unambiguously and uniquely which nodes are failing. Following the focus of some recent results analyzing maximal identifiability from a theoretical point of view, this work establishes the complexity of the optimization problem that determines the maximal k for which a set of measurement paths is k-identifiable (MID). We prove that such problem is NP-hard by a reduction from the Minimum Hitting Set problem and we prove that its decision version is in NP. We further consider the following extremal combinatoric question, which is also of practical relevance: given the number n of nodes of the network and a non-negative integer value k for the identifiability, what is the minimal number m of measurement paths over the n nodes to consider in such a way that the maximal identifiability is at least k? A folklore result shows that to have maximal identifiability at least 1, then m≥log(n+1) (or, equivalently, that if n>2m−1, then the maximal identifiability is less than or equal 0). In this work we answer this question for each n∈N and for each k≥2, proving that, there is constant C such that if n>Cm1+[Formula presented], then the maximal identifiability value is strictly smaller than k (and when k=2, n>Cmm suffices). Finally, we study upper and lower bounds on the number of unambiguously identifiable nodes, introducing new identifiability conditions which strictly imply and are strictly implied by unambiguous identifiability. We use these new conditions to design algorithmic heuristics to count defective nodes in a fine-grained way. In particular we introduce a random model to study lower bounds on the number of unambiguously identifiable defective nodes and we use this model to estimate lower bounds on the number of identifiable nodes on real networks by a maximum likelihood estimate approach.