+A~better algorithm will be shown in Chapter~\ref{optchap}.
+
+%--------------------------------------------------------------------------------
+
+\section{Verification of minimality}\id{verifysect}%
+
+Now we will turn our attention to a~slightly different problem: given a~spanning
+tree, how to verify that it is minimum? We will show that this can be achieved
+in linear time and it will serve as a~basis for a~randomized linear-time
+MST algorithm in Section~\ref{randmst}.
+
+MST verification has been studied by Koml\'os \cite{komlos:verify}, who has
+proven that $\O(m)$ edge comparisons are sufficient, but his algorithm needed
+super-linear time to find the edges to compare. Dixon, Rauch and Tarjan \cite{dixon:verify}
+have later shown that the overhead can be reduced
+to linear time on the RAM using preprocessing and table lookup on small
+subtrees. Later, King has given a~simpler algorithm in \cite{king:verifytwo}.
+
+In this section, we will follow Koml\'os's steps and study the comparisons
+needed, saving the actual efficient implementation for later.
+
+\para
+To verify that a~spanning tree~$T$ is minimum, it is sufficient to check that all
+edges outside~$T$ are $T$-heavy (by the Minimality Theorem, \ref{mstthm}). In fact, we will be
+able to find all $T$-light edges efficiently. For each edge $uv\in E\setminus T$,
+we will find the heaviest edge of the tree path $T[u,v]$ and compare its weight
+to $w(uv)$. It is therefore sufficient to solve the following problem:
+
+\problem
+Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] \mid u,v\in V(T) \}$
+specified by their endpoints, find the heaviest edge \df{(peak)} of every path in~$Q$.
+
+\paran{Bor\o{u}vka trees}%
+Finding the peaks can be burdensome if the tree~$T$ is degenerated,
+so we will first reduce it to the same problem on a~balanced tree. We run
+the Bor\o{u}vka's algorithm on~$T$, which certainly produces $T$ itself, and we
+record the order, in which the subtrees have been merged, in another tree~$B(T)$.
+The peak queries on~$T$ can be then easily translated to peak queries on~$B(T)$.
+
+\defn
+For a~weighted tree~$T$ we define its \df{Bor\o{u}vka tree} $B(T)$ as a~rooted tree which records
+the execution of the Bor\o{u}vka's algorithm run on~$T$. The leaves of $B(T)$
+are all the vertices of~$T$, an~internal vertex~$v$ at level~$i$ from the bottom
+corresponds to a~component tree~$C(v)$ formed in the $i$-th iteration of the algorithm. When
+a~tree $C(v)$ selects an adjacent edge~$e$ and gets merged with some other trees to form
+a~component $C(u)$, we add an~edge $uv$ to~$B(T)$ and set its weight to $w(e)$.
+
+\figure{bortree.eps}{\epsfxsize}{An octipede and its Bor\o{u}vka tree}
+
+\obs
+As the algorithm finishes with a~single component in the last phase, the Bor\o{u}vka tree
+is really a~tree. All its leaves are on the same level and each internal vertex has
+at least two sons. Such trees will be called \df{complete branching trees.}
+
+\lemma
+For every tree~$T$ and every pair of its vertices $x,y\in V(T)$, the peak
+of the path $T[x,y]$ has the same weight as the peak of~the path $B(T)[x,y]$.
+
+\proof
+Let us denote the path $T[x,y]$ by~$P$ and its heaviest edge by~$h=ab$. Similarly,
+let us use $P'$ for $B(T)[x,y]$ and $h'$ for the heaviest edge of~$P'$.
+
+We will first prove that~$h$ has its counterpart of the same weight in~$P'$,
+so $w(h') \ge w(h)$. Consider the lowest vertex $u$ of~$B(T)$ such that the
+component $C(u)$ contains both $a$ and~$b$, and consider the sons $v_a$ and $v_b$ of~$u$
+for which $a\in C(v_a)$ and $b\in C(v_b)$. As the edge~$h$ must have been
+selected by at least one of these components, we assume without loss of generality that
+it was $C(v_a)$, and hence we have $w(uv_a)=w(h)$. We will show that the
+edge~$uv_a$ lies in~$P'$, because exactly one of the vertices $x$, $y$ lies
+in~$C(v_a)$. Both cannot lie there, since it would imply that $C(v_a)$,
+being connected, contains the whole path~$P$, including~$h$. On the other hand,
+if $C(v_a)$ contained neither~$x$ nor~$y$, it would have to be incident with
+another edge of~$P$ different from~$h$, so this lighter edge would be selected
+instead of~$h$.
+
+In the other direction: for any edge~$uv\in P'$, the tree~$C(v)$ is incident
+with at least one edge of~$P$, so the selected edge must be lighter or equal
+to this edge and hence also to~$h$.
+\qed
+
+\para
+We will simplify the problem even further: For an~arbitrary tree~$T$, we split each
+query path $T[x,y]$ to two half-paths $T[x,a]$ and $T[a,y]$ where~$a$ is the
+\df{lowest common ancestor} of~$x$ and~$y$ in~$T$. It is therefore sufficient to
+consider only paths that connect a~vertex with one of its ancestors.
+
+When we combine the two transforms, we get:
+
+\lemman{Balancing of trees}\id{verbranch}%
+For each tree~$T$ on $n$~vertices and a~set~$Q$ of $q$~query paths on~$T$, it is possible
+to find a~complete branching tree~$T'$, together with a~set~$Q'$ of paths on~$T'$,
+such that the weights of the heaviest edges of the paths in~$Q$ can be deduced from
+the same of the paths in~$Q'$. The tree $T'$ has at most $2n$ vertices and $\O(\log n)$
+levels. The set~$Q'$ contains at most~$2q$ paths and each of them connects a~vertex of~$T'$
+with one of its ancestors. The construction of~$T'$ involves $\O(n)$ comparisons
+and the transformation of the answers takes $\O(q)$ comparisons.
+
+\proof
+The tree~$T'$ will be the Bor\o{u}vka tree for~$T$, obtained by running the
+contractive version of the Bor\o{u}vka's algorithm (Algorithm \ref{contbor})
+on~$T$. The algorithm runs in linear time, for example because trees are planar
+(Theorem \ref{planarbor}). We therefore spend $\O(n)$ comparisons in it.
+
+As~$T'$ has~$n$ leaves and it is a~complete branching tree, it has at most~$n$ internal vertices,
+so~$n(T')\le 2n$ as promised. Since the number of iterations of the Bor\o{u}vka's
+algorithm is $\O(\log n)$, the depth of the Bor\o{u}vka tree must be logarithmic as well.
+
+For each query path $T[x,y]$ we find the lowest common ancestor of~$x$ and~$y$
+and split the path by the two half-paths. This produces a~set~$Q'$ of at most~$2q$ half-paths.
+The peak of every original query path is then the heavier of the peaks of its halves.
+\qed
+
+\paran{Bounding comparisons}%
+We will now describe a~simple variant of the depth-first search which finds the
+peaks of all query paths of the balanced problem. As we promised,
+we will take care of the number of comparisons only, as long as all other operations
+are well-defined and they can be performed in polynomial time.
+
+\defn
+For every edge~$e=uv$, we consider the set $Q_e$ of all query paths containing~$e$.
+The vertex of a~path, that is closer to the root, will be called the \df{top} of the path,
+the other vertex its \df{bottom.}
+We define arrays $T_e$ and~$P_e$ as follows: $T_e$~contains
+the tops of the paths in~$Q_e$ in order of their increasing depth (we
+will call them \df{active tops} and each of them will be stored exactly once). For
+each active top~$t=T_e[i]$, we define $P_e[i]$ as the peak of the path $T[v,t]$.
+
+\obs
+As for every~$i$ the path $T[v,T_e[i+1]]$ is contained within $T[v,T_e[i]]$,
+the edges of~$P_e$ must have non-increasing weights, that is $w(P_e[i+1]) \le
+w(P_e[i])$.
+This leads to the following algorithm:
+
+\alg $\<FindPeaks>(u,p,T_p,P_p)$ --- process all queries located in the subtree rooted
+at~$u$ entered from its parent via an~edge~$p$.
+\id{findpeaks}
+
+\algo
+\:Process all query paths whose bottom is~$u$ and record their peaks.
+This is accomplished by finding the index~$i$ of each path's top in~$T_p$ and reading
+the desired edge from~$P_p[i]$.
+
+\:For every son~$v$ of~$u$, process the edge $e=uv$:
+
+\::Construct the array of tops~$T_e$ for the edge~$e$: Start with~$T_p$, remove
+ the tops of the paths that do not contain~$e$ and add the vertex~$u$ itself
+ if there is a~query path which has~$u$ as its top and whose bottom lies somewhere
+ in the subtree rooted at~$v$.
+
+\::Prepare the array of the peaks~$P_e$: Start with~$P_p$, remove the entries
+ corresponding to the tops that are no longer active. If $u$ became an~active
+ top, append~$e$ to the array.
+
+\::Finish~$P_e$:
+ Since the paths leading to all active tops have been extended by the
+ edge~$e$, compare $w(e)$ with weights of the edges recorded in~$P_e$ and replace
+ those edges which are lighter by~$e$.
+ Since $P_p$ was sorted, we can use binary search
+ to locate the boundary between the lighter and heavier edges in~$P_e$.
+
+\::Recurse on~$v$: call $\<FindPeaks>(v,e,T_e,P_e)$.
+\endalgo
+
+\>As we need a~parent edge to start the recursion, we add an~imaginary parent
+edge~$p_0$ of the root vertex~$r$, for which no queries are defined. We can
+therefore start with $\<FindPeaks>(r,p_0,\emptyset,\emptyset)$.
+
+Let us account for the comparisons:
+
+\lemma\id{vercompares}%
+When the procedure \<FindPeaks> is called on the balanced problem, it
+performs $\O(n+q)$ comparisons, where $n$ is the size of the tree and
+$q$ is the number of query paths.
+
+\proof
+We will calculate the number of comparisons~$c_i$ performed when processing the edges
+going from the $(i+1)$-th to the $i$-th level of the tree.
+The levels are numbered from the bottom, so leaves are at level~0 and the root
+is at level $\ell\le \lceil \log_2 n\rceil$. There are $n_i\le n/2^i$ vertices
+at the $i$-th level, so we consider exactly $n_i$ edges. To avoid taking a~logarithm\foot{All logarithms are binary.}
+of zero, we define $\vert T_e\vert=1$ for $T_e=\emptyset$.
+\def\eqalign#1{\null\,\vcenter{\openup\jot
+ \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
+ \crcr#1\crcr}}\,}
+$$\vcenter{\openup\jot\halign{\strut\hfil $\displaystyle{#}$&$\displaystyle{{}#}$\hfil&\quad#\hfil\cr
+c_i &\le \sum_e \left( 1 + \log \vert T_e\vert \right)&(Total cost of the binary searches.)\cr
+ &\le n_i + \sum_e \log\vert T_e\vert&(We sum over $n_i$ edges.)\cr
+ &\le n_i + n_i \cdot {\sum_e \log\vert T_e\vert \over n_i}&(Consider the average of logarithms.) \cr
+ &\le n_i + n_i \cdot \log{\sum_e \vert T_e\vert \over n_i}&(Logarithm is concave.) \cr
+ &\le n_i + n_i \cdot \log{q+n\over n_i}&(Bound the number of tops by queries.) \cr
+ &= n_i \cdot \left( 1 + \log\left({q+n\over n}\cdot{n\over n_i}\right) \right)\cr
+ &= n_i + n_i\log{q+n\over n} + n_i\log{n\over n_i}.\cr
+}}$$
+Summing over all levels, we estimate the total number of comparisons as:
+$$
+c = \sum_i c_i = \left( \sum_i n_i \right) + \left( \sum_i n_i \log{q+n\over n}\right) + \left( \sum_i n_i \log{n\over n_i}\right).
+$$
+The first part is equal to~$n$, the second one to $n\log((q+n)/n)\le q+n$. For the third
+one, we would like to plug in the bound $n_i \le n/2^i$, but we unfortunately have one~$n_i$
+in the denominator. We save the situation by observing that the function $f(x)=x\log(n/x)$
+is decreasing\foot{We can easily check the derivative: $f(x)=(x\ln n-x\ln x)/\ln 2$, so $f'(x)\cdot \ln2 =
+\ln n - \ln x - 1$. We want $f'(x)<0$ and therefore $\ln x > \ln n - 1$, i.e., $x > n/e$.}
+for $x > n/e$, so for $i\ge 2$ it holds that:
+$$
+n_i\log{n\over n_i} \le {n\over 2^i}\cdot\log{n\over n/2^i} = {n\over 2^i} \cdot i.
+$$
+We can therefore rewrite the third part as:
+$$\eqalign{
+\sum_i n_i\log{n\over n_i} &\le n_0\log{n\over n_0} + n_1\log{n\over n_1} + n\cdot\sum_{i\ge 2}{i\over 2^i} \le\cr
+&\le n\log1 + n_1\cdot {n\over n_1} + n\cdot\O(1) = \O(n).\cr
+}$$
+Putting all three parts together, we conclude that:
+$$
+c \le n + (q+n) + \O(n) = \O(n+q). \qedmath
+$$
+
+\para
+When we combine this lemma with the above reduction from general trees to balanced trees, we get the following theorem:
+
+\thmn{Verification of the MST, Koml\'os \cite{komlos:verify}}\id{verify}%
+For every weighted graph~$G$ and its spanning tree~$T$, it is sufficient to
+perform $\O(m)$ comparisons of edge weights to determine whether~$T$ is minimum
+and to find all $T$-light edges in~$G$.
+
+\proof
+We first transform the problem to finding all peaks of a~set
+of query paths in~$T$ (these are exactly the paths covered by the edges
+of $G\setminus T$). We use the reduction from Lemma \ref{verbranch} to get
+an~equivalent problem with a~full branching tree and a~set of parent-descendant
+paths. The reduction costs $\O(m+n)$ comparisons.
+Then we run the \<FindPeaks> procedure (Algorithm \ref{findpeaks}) to find
+the tops of all query paths. According to Lemma \ref{vercompares}, this spends another $\O(m+n)$
+comparisons. Since we (as always) assume that~$G$ is connected, $\O(m+n)=\O(m)$.
+\qed
+
+\paran{Other applications}%
+The problem of computing path maxima or minima in a~weighted tree has several other interesting
+applications. One of them is computing minimum cuts separating given pairs of vertices in a~given
+weighted undirected graph~$G$. We construct a~Gomory-Hu tree~$T$ for the graph as described in \cite{gomoryhu}
+(see also \cite{bhalgat:ght} for a~more efficient algorithm running in time
+$\widetilde\O(mn)$ for unit-cost graphs). The crucial property of this tree is that for every two
+vertices $u$, $v$ of the graph~$G$, the minimum-cost edge on $T[u,v]$ has the same cost
+as the minimum cut separating $u$ and~$v$ in~$G$. Since the construction of~$T$ generally
+takes $\Omega(n^2)$ time, we could of course invest this time in precomputing the minima for
+all pairs of vertices. This would however require quadratic space, so we can better use
+the method of this section which fits in $\O(n+q)$ space for $q$~queries.
+
+\paran{Dynamic verification}%
+A~dynamic version of the problem is also often considered. It calls for a~data structure
+representing a~weighted forest with operations for modifying the structure of the forest
+and querying minima or maxima on paths. Sleator and Tarjan have shown in \cite{sleator:trees}
+how to do this in $\O(\log n)$ time amortized per operation, which leads to
+an~implementation of the Dinic's maximum flow algorithm \cite{dinic:flow}
+in time $\O(mn\log n)$.