zbMATH — the first resource for mathematics

An inverse-Ackermann type lower bound for online minimum spanning tree verification. (English) Zbl 1121.05067
Summary: Given a spanning tree \(T\) of some graph \(G\), the problem of minimum spanning tree verification is to decide whether \(T = \text{MST}(G)\). A celebrated result of J. Komlós [Combinatorica 5, 57–65 (1985; Zbl 0579.05031)] shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is \(e\) in the MST of \(T\cup \{e\}\)”, where the tree \(T\) is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires \(\Omega(m\alpha(m,n))\) time, where \(\alpha(m,n)\) is the inverse-Ackermann function and \(n\) is the size of the tree. On the other hand, we show that if the weights of \(T\) are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time.

05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI