Testing Spreading Behavior in Networks with Arbitrary Topologies

Given the full topology of a network, how hard is it to test if it is evolving according to a local rule or is far from doing so? Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every “infected” node stays infected forever, and each “healthy” node becomes infected if and only if it has at least one infected neighbor. Our results are subdivided into two main groups: If we are testing a single time step of evolution, then the query complexity is O(∆/ε) or Õ(√n/ε) (whichever is smaller), where ∆ and n are the maximum degree of a node and the number of vertices in the underlying graph, respectively. We also give lower bounds for both one- and two-sided error testers that match our upper bounds up to ∆ = o(√n) and ∆ = O(n¹/³), respectively. If ε is constant, then the first of these also holds against adaptive testers. When testing the environment over T time steps, we have two algorithms that need O(∆^T−1/εT) and Õ(|E|/εT) queries, respectively, where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T = 2.