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) outcome1. Such end-to-end measurements paths are usually described by an incidence boolean matrix M with rows (the measurements paths) and columns (the nodes of the network). A key notion used in practice in this approach is that of -identifiability . Loosely speaking, a set of boolean measurements paths over nodes is -identifiable, where is a non-negative integer, if, whenever there are fewer than + 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 [1, 2, 3, 4], this work establishes the complexity of the optimization problem that determines the maximal for which a set of measurement paths is -identifiable ( MID). We prove that such a problem is NP-hard by a reduction from the Minimum Hitting Set problem. To our knowledge the NP-hardness of MID and the relation with the Minimum Hitting Set problem are new and not known before. We further consider the following extremal combinatoric question: given the number of nodes of the network and a non-negative integer value for the identifiability, what is the minimal number of measurement paths over the nodes to consider in such a way that the maximal identifiability value is at least ? A folklore result shows that to have maximal identifiability at least 1, then ≥ log( + 1) (or, equivalently, that if > 2 − 1, then the maximal identifiability is less than or equal 0). In this work we answer this question for each ∈ N and for each ≥ 2, proving that, there exists a constant such that if > 1+ −1 , then the maximal identifiability value is strictly smaller than (and when = 2, > sufices). To show these results we consider two notions that we prove to be equivalent to -identifiability: one is from the field of non-adaptive group testing (NAGT) and the other is the notion of union-free set families [5]. The connection between identifiability and group testing was mentioned in [6]; we make this connection precise towards a solution of our problem.
Network Tomography is a general inference technique based on end-to-end measurements aimed to extract not only internal network characteristics such as link delays and link loss rates but also defective items. In Boolean Network Tomography (BNT) the outcome of the measurements 1In this paper we consider only identifying failure nodes but all the results work for links as well. ICTCS’24: Italian Conference on Theoretical Computer Science, September 11–13, 2024, Torino, Italy * Supported by the project PRIN 2022 "Logical Methods in Combinatorics" N. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR). $ nicola.galesi@uniroma1.it (N. Galesi); fariba.ranjbar@luiss.it (F. Ranjbar) 0000-0002-8522-362X (N. Galesi); 0000-0001-6432-3683 (F. Ranjbar)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). is a Boolean value. Dufield in [ 7], introduced the Boolean network tomography approach to identify sets of failure links in networks and later this was also applied for node failure identification, in the works [ 8, 9, 10, 1, 3, 2, 4]. The BNT approach is rather simple: each measurement path is routed with a suitable data packet and the received data at the end of the path is one bit capturing the presence or the absence of failures along the path: for a failure the output bit is intended to be 1 and for a properly working path the output bit is 0. Such a method can be applied to detect both node and link failures in a network. In this work we always deal with nodes, but all the results can be similarly applied to capture defective links.
Since in each path the outcome of a measurement indicates only whether a failure occurred somewhere in the path, in the BNT approach the position of the nodes in the paths is not taken into account and paths are regarded as sets of nodes.
The problem of identifying failing nodes is approached by studying the solutions ⃗ of a Boolean system M⃗ = ⃗, where M is the incidence {0, 1}-matrix of the measurement paths over the nodes, ⃗ is the vector of length of the Boolean outcomes of the measurement paths and ⃗ is the Boolean vector of length indicating whether each node is failing or not. To be consistent with the BNT terminology, in this work we keep the names nodes and paths respectively for the columns and the rows of M. The challenge of localizing failure nodes is that diferent sets of failure nodes can produce the same measurement along the paths and so are indistinguishable from each other with only using the measurements. This led to the following question: given the set of paths, what is the maximal set of defective nodes one can hope to identify unambiguously?
-identifiability (for a set M of paths over nodes) states that any two distinct node sets and of size at most can be separated by at least one path in M, that is, there is at least one path touching nodes of only one of them. It was observed in [9] that having maximal -identifiability for a set of paths M ensures that if there are at most failing nodes, then these nodes can be identified unambiguously using the BNT approach: this was exactly what was needed towards node failure identification. Concretely, we are interested in understanding the maximal such that M is -identifiable. This measure - which we call (M, , ) - was introduced and investigated especially from an applied perspective in the works [8, 9, 10]. The book [6] presents a comprehensive treatment of -identifiability and boolean network tomography.
Identifiability however is a precise combinatorial definition and therefore it was interesting to research it also from a theoretical and combinatorial perspective complementing the applied results. In a series of recent works [1, 2, 3, 4] focusing on theoretical aspects of identifiability we studied the relations of maximal -identifiability with the topology of the network and some of its structural properties, like vertex connectivity.
This work contributes to the research line of boolean network tomography and maximal -identifiability. We consider two problems: the first question we approach is that of understanding the computational complexity of maximal -identifiability. We consider the following optimization problem: given a set M of measurement paths over nodes, determine the maximal for which M is -identifiable ( MID).
We consider the question of proving that MID is NP-hard. In Theorem 3.4 we prove this result using a reduction from the well-known Minimum Hitting Set problem (MHS). The complexity of MID was not known before and to our knowledge this is the first time that the optimization problem of maximizing -identifiability is shown to be strictly related to the Minimum Hitting Set problem. We complement the MID hardness result: first we prove that the problem of deciding whether a set of paths is not -identifiable, for a given ∈ N, is in NP (Theorem 3.7). Second we prove that if MHS is computable in polynomial time, then also MID is computable in polynomial time (Theorem 3.6). Together with the hardness result this establish a strict relationships between Minimum Hitting Set problem and the MID problem. This relation might be interesting from an applied point view for algorithms approximating -identifiability: indeed it is known that there are -approximation algorithms for the Minimum Hitting Set problem where edges have cardinality at most [11, 12], which is the case of our reduction in theorem 3.6 when the paths in M has length at most . The reduction used in Theorem 3.6 to prove the hardness result works by first reducing MID to a maximal -identifiability problem scaled to each single node: a node is -identifiable in M if any two node sets and of size at most and difering on (that is such that is only in one of them) are separated by at least a path in M (that is there exists a path intersecting one of them but not the other).
The second problem we face is an extremal combinatoric question: imagine a network topology with nodes is given, and let us say we establish a non-negative integer value for the number of defective nodes we aim to identify: what is the minimal number of measurement paths over the nodes we have to consider in such a way that the maximal identifiability is at least ? This is an extremal question on the incidence matrix M. The answer to this question for = 1 follows immediately by the pigeonhole principle argument: if we have more than 2 binary strings of length there are at least two identical strings. The result for = 1 can be formalized as follows (see Lemma 4.1 for the details): if (M, , ) ≥ 1, then ≥ log( + 1), or, equivalently, saying that if > 2 − 1, then (M, , ) < 1. Nothing is known for a generic > 1 and here we answer this question for any ∈ N and for any ∈ N, 1 < ≤ in Theorem 4.7.
It is not dificult to see, and it is also explicitly mentioned in [6], that -identifiability is related to similar concepts in Group Testing [13]. Approaching our second question we first make this connection precise to solve our question. We identify precisely in [13] a central notion defined in non-adaptive group testing (NAGT) (the so-called ¯-separability) which we prove to be equivalent to -identifiability (see Definition 2.3 and Lemma 2.4 for the precise definition of ¯-separability and the proof of the equivalence). Using a known theorem in NAGT (Theorem 2.6) we can answer our question but only for + 1 (Theorem 4.2). However to prove the result for , using known results in NAGT is not suficient, and new techniques are needed. Towards this goal and looking again at M as a hypergraph, we observe that -identifiability is strictly related to the combinatorial notion called union-free families of sets. This was a combinatorial notion on sets introduced in [5] and studied in [5, 14] which we observe to be strictly related to -identifiability (Theorem 4.4). Using a recent result on uniform union-free families, proved in [14], we can eventually fully answer to our question: Theorem 4.7 states that there is a constant such that > 1+ −1 ⇒ (M, , ) < if ≥ 3 and > ⇒ (M, , ) < 2.
Finally, in the last subsection, we use these results to provide bounds on the maximal number of -identifiable nodes, for each ∈ N.
Let , ∈ N, ≤ . [] = {1, . . . , } and (︀ [])︀ is the set of subsets of [] of size . 2 is the set of subsets of the set .
Let and be positive integers. Following previous works on Boolean network tomography [6] we see a set M of paths over nodes in [] as a {0, 1}-matrix of rows and columns1. On M we use the following notations: 1. We see M as a collection of -bit vectors, that is the columns of the matrix M, that are vectors of length , all diferent from the -bit zero vector2. 2. For ∈ [], M() is the set of rows ∈ [], such that belongs to , that is such that M[, ] = 1. In the simpler BNT terminology, we say that M() is the set of paths in [] passing through (or intersecting) the node . If ⊆ [], then M( ) = ⋃︀∈M() so, if ⊆ , then M( ) ⊆ M( ). In the following we will use the BNT terminology talking of nodes and paths in M to mean columns and rows of M and see them simply as sets of Boolean values.
Definition 2.1. (Identifiability) A Boolean matrix M over rows and columns is -identifiable if for all , ⊆ [] such that | |, | | ≤ and ̸= , it holds that M( ) ̸= M( ). We denote by (M) = (M, , ) the maximal ≤ such that M is -identifiable.
We observe next that -identifiability is strictly related to some notions in non-adaptive group testing. Consider the following definitions given in [ 13]. First, notice that the union (or Boolean sums) of any columns in a Boolean matrix M is, the bitwise OR that is a binary operation that takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1. Moreover, in terms of the union (or Boolean sums) of columns in a Boolean matrix M over rows and columns, in the definition 2.1 we have for ⊆ [] with | | ≤ , M( ) = ⋃︀∈M() which is the union (or Boolean sums) of up to columns. Definition 2.2. (Disjunctness) A Boolean matrix M with rows and columns is called disjunct if the union (or Boolean sums) of any columns in M does not contain any other column in M. Notice that this also implies that the union of any up to columns does not contain any other column.
Definition 2.3. (-separability and ¯-separability) A Boolean matrix M of rows and columns is called -separable (respectively -separable) if the unions (or Boolean sums) of columns (respectively of up to columns) are all distinct. 1Notice that this encoding does not keep track of the order of the nodes in the path, but this is usual in Boolean network tomography approaches for identifying failing nodes since the position of the nodes in the paths is not taken into account and hence paths are regarded as sets of nodes. 2Notice that when M is a real set of paths, the condition means that each node is used in at least one path. Lemma 2.4. A Boolean matrix M with rows and column is ¯-separable if and only if it is -identifiable Proof. First assume that M is -identifiable. Then for all , ⊆ [] such that | |, | | ≤ and ̸= , we have M( ) ̸= M( ). Moreover M( ) = ⋃︀∈M() which is the union of up to columns. The unions of up to columns are thus all distinct and M is ¯-separable. Similarly if M is ¯-separable, the unions of up to columns are all distinct i.e., for all , ⊆ [] such that | |, | | ≤ and ̸= , ⋃︀∈M() = M( ) ̸= M( ) = ⋃︀∈M(). Therefore M is -identifiable.
A close relation between disjunctness and separability of M was proved in [13] (Lemma 7.2.2 and Lemma 7.2.4) Lemma 2.5 ([13]). For a {0, 1}-matrix M of rows and columns: 1. if M is -disjunct, then M is -separable. 2. if M is ( + 1)-separable, then M is a -disjunct.
Let (, ) denotes the minimum number of rows for a -disjunct matrix with columns.
We have the following theorem (Theorem 7.2.13 in [13]):
Theorem 2.6 ([13]). For fixed and → ∞, there is a constant such that
(, ) ≥ (1 + (
We have seen that -identifiability is a reasonable combinatorial notion. In this section we clarify what is its computational complexity. We consider the following optimization problem: MID: Input: A Boolean × matrix M.
Output: The maximal ≤ such that M is -identifiable.
Let M be a × Boolean matrix. We say that two sets of nodes , ⊆ [] difer on if belongs to exactly one of them, that is ∩ {} ≠ ∩ {}. Furthermore we say that a path ∈ [] separates and in M if belongs to exactly one between M( ) and M( ). The definition of -identifiability can be scaled to nodes ∈ [] as follows: Definition 3.1. (-identifiable nodes) A node ∈ [] is -identifiable in M, if for all , ⊆ [] of size at most difering on , it holds that M( ) ̸= M( ).
Scaling identifiability to nodes does not afect the -identifiability of the whole M. The next theorem has been proven in [9], but we decide to show the proof again for the sake of completeness.
Theorem 3.2. ([9]) Let M be a set of paths over nodes. M is -identifiable if and only if every node in [] is -identifiable in M.
Proof. First assume that M is -identifiable and let ∈ []. Since M is -identifiable, for all , ⊆ [] of size at most such that ̸= , M( ) ̸= M( ) holds. Therefore for all , ⊆ [] such that | |, | | ≤ and difering on , we also have M( ) ̸= M( ). This proves that is -identifiable.
Now let every node in [] be -identifiable in M. Assume by contradiction that M is not -identifiable. This means that there exist two subsets , ⊆ [] of size at most such that ̸= and M( ) = M( ). Since ̸= , without loss of generality we can say that there is a node ∈ ∖ (or in ∖ if ⊂ ). Hence, for node , we have the two subsets , ⊆ [] such that | |, | | ≤ and difering on and we also have M( ) = M( ) which means the node is not -identifiable and this is a contradiction.
Let ID(M) be the set of -identifiable nodes in M.
Lemma 3.3. ID(M) ⊆ ID′ (M) for ′ ≤ ≤ .
Proof. From Definitions 2.1 and 3.1 it is immediate to see that -identifiability implies ′identifiability for any ′ < . Hence the claim.
Theorem 3.4. MID is NP-hard.
NID: Input: A Boolean × matrix M, an element ∈ [].
Output: The maximal ≤ such that ∈ ID(M).
By Theorem 3.2 MID and NID are polynomially equivalent (MID ≡ NID, that is polynomially reducible to each other). So to prove the NP-hardness of MID it is suficient to prove the NPhardness of NID.
As noticed before ID(M) ⊆ ID′ (M) for any ′ ≤ , hence to solve NID it is suficient to know the minimal ℓ such ̸∈ IDℓ(M): indeed, given such an ℓ, it is suficient to set = ℓ − 1 to get a solution for NID. We call this problem NID⊤.
NID⊤: Input: A Boolean × matrix M, an element ∈ [].
Output: The minimal ℓ ≤ such that ̸∈ IDℓ(M).
NID and NID⊤ are clearly polynomially equivalent and to prove the NP-hardness of NID, we work with the problem NID⊤.
Consider a hypergraph (a set-system) ℋ = ([], ), where ⊆ 2[] with || = . A set ⊆ [] is a hitting set for ℋ if ∩ ̸= ∅ for all ∈ . is minimal if no other subset ′ of [] smaller than has the same property.
The optimization problem Minimum Hitting Set, MHS, is MHS: Input: A hypergraph ℋ = ([], ).
Output: A minimal hitting set of ℋ.
MHS is a well-known NP-hard problem [15, 16]. The next claim concludes the proof of the theorem.
Claim 3.5. MHS ≤ NID⊤.
Proof. Let ℋ = ([], ) be a hypergraph. We define an instance (Mℋ, ℋ) for NID⊤ as follows: • Mℋ has + 1 columns, • the set of rows of Mℋ is , • ℋ = + 1 and M(ℋ) = , namely every path touches the node ℋ.
We prove that ℋ ∈ MHS if and only if (Mℋ, ℋ) ∈ NID⊤. We first prove the soundness of the reduction, that is (Mℋ, ℋ) ∈ NID⊤. Let be a minimal hitting set of size for the instance ℋ of MHS. We need to prove that 1. ℋ ̸∈ ID(Mℋ), and 2. ℋ ∈ ID(Mℋ) for all ≤ − 1.
To show ℋ ̸∈ ID(Mℋ), by the definition of -identifiability we have to find two subsets and of [ + 1] and of size at most difering on ℋ such that M( ) = M( ). So we fix = and = {ℋ}. Since = and is an hitting set in ℋ = ([], ), then ⊆ [] and since ℋ = + 1, and difer on ℋ, but by construction of (Mℋ, ℋ), M( ) = M( ) = . Hence ℋ ̸∈ ID(M). To prove the optimality condition, that is, ℋ ∈ ID(Mℋ) for all ≤ − 1, assume by contradiction that there exist two subsets of [ + 1], ′ and ′ of size ≤ − 1 difering on ℋ such that M( ′) = M( ′). Since ′ and ′ difer on ℋ, ℋ is in exactly one of them, say ′. Given that M(ℋ) = , it follows that M( ′) = . Hence ′ ⊆ [] is a hitting set for ℋ of size strictly smaller than = | |, and this is a contradiction.
To prove the completeness of the reduction, given (Mℋ, ℋ) ∈ NID⊤ we prove that ℋ ∈ MHS. Since (Mℋ, ℋ) ∈ NID⊤, we know that: 1. in (Mℋ, ℋ), there exist two subsets of [ + 1], and of size at most difering on ℋ such that M( ) = M( ) (i.e., ℋ ̸∈ ID(Mℋ)), and 2. for any pair of distinct subsets ′ and ′ of size ≤ − 1 difering on ℋ we have
M( ′) ̸= M( ′) (namely ℋ ∈ ID(Mℋ) for all ≤ − 1).
Observe that since and difer on ℋ, ℋ belongs to only one of them, say . Hence
⊆ []. Furthermore, since = M(ℋ) and ℋ ∈ , thus = M( ) = M( ). Therefore,
if we fix = , we have that ∩ ̸= ∅ for all ∈ and is a hitting set in ℋ. To prove the
optimality of , assume by contradiction that there exists a set ′ ⊆ [], with | ′| < | | ≤
such that ′ is also a hitting set in ℋ. Let ′ = ′ and ′ = {ℋ}. These are two subsets of
[ + 1] of size at most − 1 such that = M( ′) = M( ′) and this contradicts Condition
(
We conclude this section investigating the inverse reduction between MHS and MID. First we show that an algorithm solving MHS raises an algorithm to solve NID⊤ and therefore MID. Theorem 3.6. Let be an algorithm solving MHS. Then, there is an algorithm ℬ solving NID⊤. Furthermore if works in polynomial time then ℬ works in polynomial time too. Proof. The algorithm ℬ solving NID⊤ works in this way: Algorithm 1 Algorithm ℬ Input: a Boolean × matrix M and a node ∈ [] 1. Define ℋM = ( ∖ {}, M()), where M() = { ∈ [] | ∈ } 2. Run on ℋM and let be its output 3. Output: = | |
The algorithm ℬ works clearly in polynomial time if works in polynomial time. To prove its correctness we need to prove that is the minimal ℓ such that ̸∈ IDℓ(M). First we argue that ̸∈ ID(M). By Definition 3.1 we have to find two sets , difering on and of size at most such that M( ) = M( ). Define = and = {}. Since is a hitting set in ℋM, it contains all the edges in ℋM, which are exactly M(). Hence M( ) = M() = M( ).
To prove that is the minimal value with that property, assume by contradiction that ̸∈ IDℓ(Mℋ) for some ℓ < | | = . Since ̸∈ IDℓ(M), there exist two subsets and of size at most ℓ difering on such that M( ) = M( ). Say without loss of generality that ∈ . Hence M() ⊆ M( ) = M( ). Therefore is covering M() which is the set of edges in ℋM. Hence is a hitting set of ℋM. But | | < | | where was the minimal hitting set. A contradiction.
Finally we consider the decision version DMID of the problem MID, that is - given a Boolean × matrix M and an integer , 0 ≤ ≤ , decide whether M is -identifiable. We prove that DMID in coNP.
Theorem 3.7. DMID is in coNP. Therefore the problem of deciding, given a set of paths over nodes M and an integer ≤ , whether M is not -identifiable is in NP.
Proof. We have to prove that DMID ∈ coNP. A certificate for this problem is any pair of sets , ⊆ [] with | |, | | ≤ and such that ̸= . This certificate is linear in the size of the input of DMID. According to Definition 2.1 to decide DMID, an algorithm has to verify whether M( ) ̸= M( ). Given and , this task can can be clearly accomplished in polynomial time in the size of M and . Notice that DMID is ∀-problem: it follows that DMID ∈ coNP. Of course the dual of this problem, that is decide if M is not -identifiable is, by the same proof, in NP.
In this section we consider the following question: given a network on nodes and a nonnegative integer value for the identifiability, what is the minimal number of measurement paths over the nodes we have to consider in such a way that we will be able to identify uniquely and unambiguously at least failing nodes (or in other words, in such a way that the maximal identifiability value is at least )?
Let us consider first a toy example for = 1.
Lemma 4.1. Let M be a Boolean × matrix. If < log( + 1) then (M, , ) < 1. Proof. We prove the equivalent statement that if > 2 − 1, then (M, , ) < 1. Since > 2 − 1 and the 0-column (i.e., the column with all entries equal to zero) cannot be in M, in M there are at least two identical columns, that is two distinct nodes , ∈ [] which belong to the same set of paths. Therefore there are = {} and = {} of size 1 such that M( ) = M( ). It follows that (M, , ) < 1.
In this subsection we generalize this result for a generic integer , with 1 < ≤ . First
notice that some partial result can be obtained from Theorem 2.6 but only for + 1.
Theorem 4.2. Let M be a Boolean matrix with rows and columns. Let be the constant in
Theorem 2.6. If < (1 + (
Proof. Assume by contradiction that for M we have < (1+(
Proving the result for instead of + 1, cannot be obtained from Theorem 2.6. This requires a diferent approach. We start by giving some preliminary definitions following [ 14]. A hypergraph ℱ on the set [] is a family of distinct subsets of [], called (hyper-)edges of ℱ . If each edge is of fixed size ≤ , then ℱ is said to be -uniform, i.e., ℱ ⊂ (︀ [])︀ . Definition 4.3. ([5, 14]) For a positive integer , ℱ is called -union-free if for any two distinct subsets of edges , ℬ ⊆ ℱ , with 1 ≤ || , |ℬ| ≤ , it holds that ∪∈ ̸= ∪∈ℬ.
Union-free uniform hypergraphs are investigated in extremal combinatorics [5].
A set M of paths over nodes defines a hypergraph ℱM with vertices in [] and hyperedges included in [] in the following way: for ∈ [] let be the set of paths ∈ [] the node belongs to, that is = { ∈ []|M[, ] = 1}. Define ℱM = {, | ∈ []}.
Given a set of nodes ⊆ [] in M, let the subset of ℱM, made by the such that ∈ , that is = { ∈ ℱM| ∈ }. Notice that, by definition of M( ), M( ) = ⋃︀∈ which can be written as ⋃︀∈ .
Theorem 4.4. If M is a set of paths over nodes and (M, , ) ≥ , then ℱM is -union free.
Proof. Assume that (M, , ) ≥ . Let and be two distinct subsets of ℱM of size at most . Let and such that = { ∈ ℱM| ∈ } and = { ∈ ℱM| ∈ }. Since and are distinct, then also and are distinct and furthermore and are of cardinality at most by the cardinality constraint on and . That means that M( ) ̸= M( ) since (M, , ) ≥ . But ⋃︀∈ = M( ) ̸= M( ) = ⋃︀∈ . The claim is proved.
Notice that ℱM is not necessarily a uniform hypergraph. Let ∈ [], then the subfamily of
ℱM defined by ℱM() = { ∈ ℱM||| = } is trivially a -uniform hypergraph on [] for any
∈ []. Notice that if 1, 2 ∈ [] with 1 ̸= 2, then ℱM(1) ∩ ℱM(2) = ∅. Therefore the
subfamilies ℱM(
Since |ℱM| = , it follows that: Lemma 4.5. ∑︀∈[] |ℱM()| = .
Furthermore notice that if ℱM is -union free, then ℱM() for each ∈ [] will also be -union free.
Let > and ∈ [] with ≥ 2, and let (, , ) denote the maximum cardinality of a -union-free -uniform hypergraph over []. The next theorem for ≥ 3 is Theorem 1.3 in [14] and for the case = 2 in [5, 14].
Furthemore (2, , ) = Θ( ⌈42/3⌉ ).
Theorem 4.6 ([5, 14]). For fixed integers , ≥ 3 it holds that (, , ) ≤ (⌈ − 1 ⌉).
Theorem 4.7. There exist two constants 0 ∈ N and , such that for all ≥ 0 if M is a set of paths over nodes, then 1. for ≥ 3, if > 1+ −1 then (M) < , and 2. if > , then (M) < 2.
Proof. Let 0 ∈ N be the integer and let be the constant obtained from the (· )-notations of the previous theorem such that for all ≥ 0, we have both (, , ) ≤ ⌈ − 1 ⌉ and (2, , ) ≤ ⌈4/3⌉
2 .
Let us prove the case ≥ 3. Assume by contradiction that > 1+ −1 and (M) ≥ . Since ∑︀∈[] ⌈ − 1 ⌉ ≤ −1 , therefore > ∑︀∈[] ⌈ − 1 ⌉. By Theorem 4.4 ℱM is -union free. Hence, by definition of -identifibility and -union freeness (see observation after Lemma 4.5) it follows that for each ∈ [], ℱM() is a -uniform -union free hypergraph and hence by the previous theorem |ℱM()| ≤ ⌈ − 1 ⌉. The ℱM() partition ℱM and by Lemma 4.5 we have = ∑︀∈[] |ℱM()| ≤ ∑︀∈[] ⌈ − 1 ⌉ < and this is a contradiction.
The case = 2 follows exactly the same reasoning observing that ⌈42/3⌉ ≤ .
In many practical applications it might be useful to know an upper bound on the maximal number of failure nodes we can hope to identify unambiguously by Boolean methods based on -identifiability. Previous results in this section can be used to obtain upper bounds on ID(M). Corollary 4.8. Let and 0 be as in Theorem 4.7. For all ≥ 0, let M be a set of paths over nodes. Then 1. | ID(M)| ≤ 2. | ID2(M)| ≤ min{, }.
min{, 1+ −1 }, for all ≥ 3; Proof. Let us prove the result for = 1 using Lemma 4.1. The claims for > 1 follow the same argument using Theorem 4.7.
| ID1(M)| ≤ since it is a set of nodes. Assume that > 2 − 1, hence by Lemma 4.1 (M) = 0, hence there are at least two nodes 1 ̸= 2 not 1-identifiable. Hence | ID1(M)| ≤ 2 − 1.
Notice that our results can be expressed also in terms of the number of paths as follows: for example for = 2 we observe that if > , then < 1+√ ︀log(/) for any > 0. Here we use the bound that log < 1+ for any > 0. A similar result can be easily obtained for the case ≥ 3.
We would like to thank Navid Talebanfard to point us the paper [14] and the anonymous reviewers of ICTCS 24 for their useful comments that helped us to improve the presentation and the readability of our paper.