An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem

We consider the problem of preprocessing an edge-weighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T ∪ {e}? Whereas the offline minimum spanning tree verification problem admits a lovely linear time solution, we demonstrate an inherent inverse-Ackermann type tradeoff in the online MST verification problem. In particular, any scheme that answers queries in t comparisons must invest Ω(n log λ_t (n)) time preprocessing the tree, where λ_t is the inverse of the t^th row of Ackermann´s function. This implies a query lower bound of Ω(α(n)) for the case of linear preprocessing time. We also show that our lower bound is tight to within a factor of 2 in the t parameter.