Tight bounds on the message complexity of distributed tree verification

We consider the message complexity of verifying whether a given subgraph of the communication network forms a tree with specific properties both in the KTρ (nodes know their ρ-hop neighborhood, including node ids) and the KT0 (nodes do not have this knowledge) models. We develop a rather general framework that helps in establishing tight lower bounds for various tree verification problems. We also consider two different verification requirements: namely that every node detects in the case the input is incorrect, as well as the requirement that at least one node detects. The results are stronger than previous ones in the sense that we assume that each node knows the number n of nodes in the graph (in some cases) or an α approximation of n (in other cases). For spanning tree verification, we show that the message complexity inherently depends on the quality of the given approximation of n: We show a tight lower bound of Ω(n2) for the case α≥2 and a much better upper bound (i.e., O(nlogn)) when nodes are given a tighter approximation. On the other hand, even for the case when nodes have perfect knowledge of the network size, our framework yields an Ω(n2) lower bound on the message complexity of verifying a minimum spanning tree (MST). This result holds for randomized algorithms with perfect knowledge of the network size, and even when just one node detects illegal inputs, thus improving over the work of Kor et al. (Theory Comput Syst 53(2):318-340, 2013). Moreover, it also reveals a polynomial separation between ST verification (when nodes know a sufficiently good network-size approximation) and MST verification. For verifying a d-approximate BFS tree, we show that the same lower bound holds even if nodes know n exactly, however, the lower bound is sensitive to d, which is the stretch parameter. First, under the KT0 assumption, we show a tight message complexity lower bound of Ω(n2) in the LOCAL model, when d≤n2+Ω1. For the KTρ assumption, we obtain an upper bound on the message complexity of O(nlogn) in the CONGEST model, when d≥n-1max{2,ρ+1}, and use a novel charging argument to show that Ω1ρnρ1+cρ messages are required even in the LOCAL model for comparison-based algorithms. For the well-studied special case of KT1, we obtain a tight lower bound of Ω(n2).