The right context turns out to be the minor-closed graph classes, which are
closed under contractions and have bounded density.
The right context turns out to be the minor-closed graph classes, which are
closed under contractions and have bounded density.
-minor-closed classes, too (see \cite{lovasz:minors} for a~nice survey
-of this theory and \cite{diestel:gt} for some of the deeper results).
+minor-closed classes, too (see Lov\'asz \cite{lovasz:minors} for a~nice survey
+of this theory and Diestel \cite{diestel:gt} for some of the deeper results).
The most important property is probably the characterization
of such classes in terms of their forbidden minors.
The most important property is probably the characterization
of such classes in terms of their forbidden minors.
--- this follows from the Kuratowski's theorem (the theorem speaks of forbidden
subdivisions, but while in general this is not the same as forbidden minors, it
is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour
--- this follows from the Kuratowski's theorem (the theorem speaks of forbidden
subdivisions, but while in general this is not the same as forbidden minors, it
is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour
\thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
For every non-trivial minor-closed graph class~$\cal C$ there exists
\thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}}
For every non-trivial minor-closed graph class~$\cal C$ there exists
we will make use of another important property --- the bounded density of
minor-closed classes. The connection between minors and density dates back to
Mader in the 1960's and it can be proven without use of the Robertson-Seymour
we will make use of another important property --- the bounded density of
minor-closed classes. The connection between minors and density dates back to
Mader in the 1960's and it can be proven without use of the Robertson-Seymour
-Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$
-to be the infimum of all~$\varrho$'s such that $m(G) \le \varrho\cdot n(G)$
-holds for every $G\in\cal C$.
+Let $G$ be a~graph and $\cal C$ be a class of graphs. We define the \df{edge density}
+$\varrho(G)$ of~$G$ as the average number of edges per vertex, i.e., $m(G)/n(G)$. The
+edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\varrho(G)$ over all $G\in\cal C$.
\thmn{Mader \cite{mader:dens}}
For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
\thmn{Mader \cite{mader:dens}}
For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
Let us fix~$k$ and prove by induction on~$m$ that every graph of average
degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices
Let us fix~$k$ and prove by induction on~$m$ that every graph of average
degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices
as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.
The base case $m=k$: Let us observe that when the average degree
as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$.
The base case $m=k$: Let us observe that when the average degree
Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
assume that the theorem already holds for $m-1$. Without loss of generality,
$G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$
Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and
assume that the theorem already holds for $m-1$. Without loss of generality,
$G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$
in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$,
as otherwise we can add this vertex to~$U$, contradicting its
maximality. By the induction hypothesis, $H$ contains a~subdivision of some
in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$,
as otherwise we can add this vertex to~$U$, contradicting its
maximality. By the induction hypothesis, $H$ contains a~subdivision of some
of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$,
which reveals a~subdivision of a~graph with $m$~edges. \qed
of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$,
which reveals a~subdivision of a~graph with $m$~edges. \qed
-Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$.
-As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(K_x)$, so
+Let~$\cal C$ be any such class, $X$~its excluded minor with the smallest number
+of vertices~$x$.
+As $X\minorof K_x$, the class $\cal C$ is entirely contained in ${\cal C}'=\Forb(K_x)$, so
$\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
theorem for classes excluding a~single complete graph~$K_x$.
$\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the
theorem for classes excluding a~single complete graph~$K_x$.
For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
algorithm (\ref{contbor}) finds the MST of any graph of this class in time
$\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
\proof
Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
algorithm (\ref{contbor}) finds the MST of any graph of this class in time
$\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
\proof
Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered
\qed
\paran{Local contractions}\id{nobatch}%
The contractive algorithm uses ``batch processing'' to perform many contractions
\qed
\paran{Local contractions}\id{nobatch}%
The contractive algorithm uses ``batch processing'' to perform many contractions
batching only the flattenings. A~contraction of an edge~$uv$ can be done
in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
batching only the flattenings. A~contraction of an edge~$uv$ can be done
in time~$\O(\deg(u))$ by removing all edges incident with~$u$ and inserting them back
with $u$ replaced by~$v$. Therefore we need to find a lot of vertices with small
\:While $n(G)>1$:
\::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
\:::Select the lightest edge~$e$ incident with~$v$.
\:While $n(G)>1$:
\::While there exists a~vertex~$v$ such that $\deg(v)\le t$:
\:::Select the lightest edge~$e$ incident with~$v$.
\:::$T\=T + \ell(e)$.
\::Flatten $G$, removing parallel edges and loops.
\algout Minimum spanning tree~$T$.
\:::$T\=T + \ell(e)$.
\::Flatten $G$, removing parallel edges and loops.
\algout Minimum spanning tree~$T$.
For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
have degree at most~$t$. Each selected edge removes one such vertex and
For the choice $t=4\varrho$, the Lemma on low-degree vertices (\ref{lowdeg})
guarantees that at the beginning of the $i$-th iteration, at least $n_i/2$ vertices
have degree at most~$t$. Each selected edge removes one such vertex and
-possibly increases the degree of another, so at least $n_i/4$ edges get selected.
-Hence $n_i\le 3/4\cdot n_{i-1}$ and therefore $n_i\le n\cdot (3/4)^i$ and the
+possibly increases the degree of another one, so at least $n_i/4$ edges get selected.
+Hence $n_i\le 3/4\cdot n_{i-1}$ and $n_i\le n\cdot (3/4)^i$, so the
algorithm terminates after $\O(\log n)$ iterations.
Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
algorithm terminates after $\O(\log n)$ iterations.
Each selected edge belongs to $\mst(G)$, because it is the lightest edge of
described by the Contraction Lemma (\ref{contlemma}) and when
the algorithm stops, $T$~is indeed the minimum spanning tree.
described by the Contraction Lemma (\ref{contlemma}) and when
the algorithm stops, $T$~is indeed the minimum spanning tree.
$m_i\le \varrho n_i \le \varrho n/2^i$.
We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
$m_i\le \varrho n_i \le \varrho n/2^i$.
We will show that the $i$-th iteration is carried out in time $\O(m_i)$.
Steps 5 and~6 run in time $\O(\deg(v))=\O(t)$ for each~$v$, so summed
-over all $v$'s they take $\O(tn_i)$, which is linear for a fixed class~$\cal C$.
-Flattening takes $\O(m_i)$, as already noted in the analysis of the Contracting
+over all $v$'s they take $\O(tn_i)$, which is $\O(n_i)$ for a fixed class~$\cal C$.
+Flattening takes $\O(m_i)$ as already noted in the analysis of the Contracting
Bor\o{u}vka's Algorithm (see \ref{contiter}).
The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
\qed
\paran{Back to planar graphs}%
Bor\o{u}vka's Algorithm (see \ref{contiter}).
The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$.
\qed
\paran{Back to planar graphs}%
-For planar graphs, we can get a sharper version of the low-degree lemma,
-showing that the algorithm works with $t=8$ as well (we had $t=12$ as
+For planar graphs, we can obtain a sharper version of the low-degree lemma
+showing that the algorithm works with $t=8$ as well (we had $t=12$ from
$\varrho=3$). While this does not change the asymptotic time complexity
of the algorithm, the constant-factor speedup can still delight the hearts of
its practical users.
$\varrho=3$). While this does not change the asymptotic time complexity
of the algorithm, the constant-factor speedup can still delight the hearts of
its practical users.
\proof
It suffices to show that the lemma holds for triangulations (if there
are any edges missing, the situation can only get better) with at
\proof
It suffices to show that the lemma holds for triangulations (if there
are any edges missing, the situation can only get better) with at
The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
so by the same argument as in the proof of the general lemma, for at least $n/2$
The numbers $d(v):=\deg(v)-3$ are non-negative and $\sum_v d(v) < 3n$,
so by the same argument as in the proof of the general lemma, for at least $n/2$
\qed
\rem\id{hexa}%
The constant~8 in the previous lemma is the best we can have.
Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
\qed
\rem\id{hexa}%
The constant~8 in the previous lemma is the best we can have.
Consider a $k\times k$ triangular grid. It has $n=k^2$ vertices, $\O(k)$ of them
vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
two colors, black and white. Now add a~new vertex inside each white face and connect
vertices have degree exactly~6. Therefore the number of faces~$f$ is $6/3\cdot n=2n$,
ignoring terms of order $\O(k)$. All interior triangles can be properly colored with
two colors, black and white. Now add a~new vertex inside each white face and connect
-The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt in~\cite{gustedt:parallel}
-who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied
+The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt \cite{gustedt:parallel},
+who studied a~parallel version of the Contractive Bor\o{u}vka's algorithm applied
\section{Iterated algorithms}\id{iteralg}%
We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
\section{Iterated algorithms}\id{iteralg}%
We have seen that the Jarn\'\i{}k's Algorithm \ref{jarnik} runs in $\Theta(m\log n)$ time.
-Fredman and Tarjan have shown a~faster implementation in~\cite{ft:fibonacci}
-using their Fibonacci heaps. In this section, we convey their results and we
-show several interesting consequences.
+Fredman and Tarjan \cite{ft:fibonacci} have shown a~faster implementation
+using their Fibonacci heaps. In this section, we will convey their results and we
+will show several interesting consequences.
The previous implementation of the algorithm used a binary heap to store all edges
separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
The previous implementation of the algorithm used a binary heap to store all edges
separating the current tree~$T$ from the rest of the graph, i.e., edges of the cut~$\delta(T)$.
When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
When we want to extend~$T$ by the lightest edge of~$\delta(T)$, it is sufficient to
find the lightest active edge~$uv$ and add this edge to~$T$ together with the new vertex~$v$.
Then we have to update the active edges as follows. The edge~$uv$ has just ceased to
is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
remembered for it so far), we set the edge~$vw$ as active. Otherwise we check the existing
active edge for~$w$ and replace it by~$vw$ if the new edge is lighter.
The following algorithm shows how these operations translate to insertions, decreases
is needed. If $w$~is outside~$T$ and it was not adjacent to~$T$ (there is no active edge
remembered for it so far), we set the edge~$vw$ as active. Otherwise we check the existing
active edge for~$w$ and replace it by~$vw$ if the new edge is lighter.
The following algorithm shows how these operations translate to insertions, decreases
\algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$v_0\=$ an~arbitrary vertex of~$G$.
\:$T\=$ a tree containing just the vertex~$v_0$.
\algn{Active Edge Jarn\'\i{}k; Fredman and Tarjan \cite{ft:fibonacci}}\id{jarniktwo}%
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$v_0\=$ an~arbitrary vertex of~$G$.
\:$T\=$ a tree containing just the vertex~$v_0$.
-\:$H\=$ a~Fibonacci heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(uv)$, initially empty.
+\:$H\=$ a~Fibonacci heap of active edges stored as pairs $(u,v)$ where $u\in T,v\not\in T$, ordered by the weights $w(uv)$, and initially empty.
\:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
\:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
\:While $H$ is not empty:
\:$A\=$ a~mapping of vertices outside~$T$ to their active edges in the heap; initially all elements undefined.
\:\<Insert> all edges incident with~$v_0$ to~$H$ and update~$A$ accordingly.
\:While $H$ is not empty:
theorem on~complexity of the Fibonacci heap:
\thmn{Fibonacci heaps, Fredman and Tarjan \cite{ft:fibonacci}} The~Fibonacci heap performs the following operations
with the indicated amortized time complexities:
\itemize\ibull
\:\<Insert> (insertion of a~new element) in $\O(1)$,
theorem on~complexity of the Fibonacci heap:
\thmn{Fibonacci heaps, Fredman and Tarjan \cite{ft:fibonacci}} The~Fibonacci heap performs the following operations
with the indicated amortized time complexities:
\itemize\ibull
\:\<Insert> (insertion of a~new element) in $\O(1)$,
\:\<Merge> (merging of two heaps into one) in $\O(1)$,
\:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
\:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
\:\<Merge> (merging of two heaps into one) in $\O(1)$,
\:\<DeleteMin> (deletion of the minimal element) in $\O(\log n)$,
\:\<Delete> (deletion of an~arbitrary element) in $\O(\log n)$,
for example \cite{clrs}), so the other data structures can improve only
multiplicative constants or offer an~easier implementation.
for example \cite{clrs}), so the other data structures can improve only
multiplicative constants or offer an~easier implementation.
in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
in the form of a~complete $d$-regular tree. \<Insert>, \<Decrease> and other operations
involving bubbling the values up spend $\O(1)$ time at a~single level, so they run
in~$\O(\log_d n)$ time. \<Delete> and \<DeleteMin> require bubbling down, which incurs
As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
for sufficiently dense graphs. In some cases, it is useful to combine it with
another MST algorithm, which identifies a~part of the MST edges and contracts
As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time
for sufficiently dense graphs. In some cases, it is useful to combine it with
another MST algorithm, which identifies a~part of the MST edges and contracts
-the graph to increase its density. For example, we can perform several Bor\o{u}vka
-steps and find the rest of the MST by the Active Edge Jarn\'\i{}k's algorithm.
+them to increase the density of the graph. For example, we can perform several Bor\o{u}vka
+steps and then find the rest of the MST by the Active Edge Jarn\'\i{}k's algorithm.
\paran{Iterating Jarn\'\i{}k's algorithm}%
Actually, there is a~much better choice of the algorithms to combine: use the
\paran{Iterating Jarn\'\i{}k's algorithm}%
Actually, there is a~much better choice of the algorithms to combine: use the
A~good choice of the stopping condition is to place a~limit on the size of the heap.
We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
we conserve the current tree and start with a~different vertex and an~empty heap. When this
process runs out of vertices, it has identified a~sub-forest of the MST, so we can
A~good choice of the stopping condition is to place a~limit on the size of the heap.
We start with an~arbitrary vertex, grow the tree as usually and once the heap gets too large,
we conserve the current tree and start with a~different vertex and an~empty heap. When this
process runs out of vertices, it has identified a~sub-forest of the MST, so we can
\:::Denote the resulting tree~$R$.
\:::$F\=F\cup R$.
\::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
\:::Denote the resulting tree~$R$.
\:::$F\=F\cup R$.
\::$T\=T\cup \ell[F]$. \cmt{Remember MST edges found in this phase.}
\proof
As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
to establish that there are at least~$t_i$ edges incident with every such tree, including
\proof
As every edge of~$G_i$ is incident with at most two trees of~$F_i$, it is sufficient
to establish that there are at least~$t_i$ edges incident with every such tree, including
The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities
how the algorithm could have stopped growing the tree~$R_i^j$:
\itemize\ibull
\:the heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
The forest~$F_i$ evolves by additions of the trees~$R_i^j$. Let us consider the possibilities
how the algorithm could have stopped growing the tree~$R_i^j$:
\itemize\ibull
\:the heap had more than~$t_i$ elements (step~10): since the each elements stored in the heap
\:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing
tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{%
This is the place where we needed to count the interior edges as well.}
\:the algorithm just added a~vertex of~$F_i$ to~$R_i^j$ (step~9): in this case, an~existing
tree of~$F_i$ is extended, so the number of edges incident with it cannot decrease;\foot{%
This is the place where we needed to count the interior edges as well.}
\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
\,\hbox{a~tower of~$i$ exponentials.}
$$
\left. \vcenter{\hbox{$\displaystyle t_i \ge 2^{2^{\scriptstyle 2^{\scriptstyle\rddots^{\scriptstyle m/n}}}} $}}\;\right\}
\,\hbox{a~tower of~$i$ exponentials.}
$$
-As soon as~$t_i\ge n$, the $i$-th phase must be final, because at that time
-there is enough space in the heap to process the whole graph. So~there are
+As soon as~$t_i\ge n$, the $i$-th phase is final, because at that time
+there is enough space in the heap to process the whole graph without stopping. So~there are
at most~$\beta(m,n)$ phases and we already know that each phase runs in linear
time (Lemma~\ref{ijphase}).
\qed
at most~$\beta(m,n)$ phases and we already know that each phase runs in linear
time (Lemma~\ref{ijphase}).
\qed
The algorithm spends most of the time in phases which have small heaps. Once the
heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
to guarantee that at most~$k$ phases remain. This means that if we are able to
The algorithm spends most of the time in phases which have small heaps. Once the
heap grows to $\Omega(\log^{(k)} n)$ for any fixed~$k$, the graph gets dense enough
to guarantee that at most~$k$ phases remain. This means that if we are able to
We modify the first pass of the algorithm to choose $t=\log n$ and use the Q-heap tree instead
of the Fibonacci heap. From Theorem \ref{qh} and Remark \ref{qhtreerem} we know that the
operations on the Q-heap tree run in constant time, so the modified first phase takes time~$\O(m)$.
Following the analysis of the original algorithm in the proof of Theorem \ref{itjarthm} we obtain
$t_2\ge 2^{t_1} = 2^{\log n} = n$, so the algorithm stops after the second phase.\foot{%
We modify the first pass of the algorithm to choose $t=\log n$ and use the Q-heap tree instead
of the Fibonacci heap. From Theorem \ref{qh} and Remark \ref{qhtreerem} we know that the
operations on the Q-heap tree run in constant time, so the modified first phase takes time~$\O(m)$.
Following the analysis of the original algorithm in the proof of Theorem \ref{itjarthm} we obtain
$t_2\ge 2^{t_1} = 2^{\log n} = n$, so the algorithm stops after the second phase.\foot{%
Gabow et al.~\cite{gabow:mst} have shown how to speed up the Iterated Jarn\'\i{}k's algorithm to~$\O(m\log\beta(m,n))$.
They split the adjacency lists of the vertices to small buckets, keep each bucket
sorted and consider only the lightest edge in each bucket until it is removed.
The mechanics of the algorithm is complex and there is a~lot of technical details
which need careful handling, so we omit the description of this algorithm.
Gabow et al.~\cite{gabow:mst} have shown how to speed up the Iterated Jarn\'\i{}k's algorithm to~$\O(m\log\beta(m,n))$.
They split the adjacency lists of the vertices to small buckets, keep each bucket
sorted and consider only the lightest edge in each bucket until it is removed.
The mechanics of the algorithm is complex and there is a~lot of technical details
which need careful handling, so we omit the description of this algorithm.
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
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
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
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
-have later shown in \cite{dixon:verify} that the overhead can be reduced
+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}.
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}.
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
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
\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
\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
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
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
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)$.
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)$.
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
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 endpoints of~$h$ lies
-in~$C(v_a)$. Both endpoints cannot lie there, since it would imply that $C(v_a)$,
+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
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
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
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
\paran{Bounding comparisons}%
We will now describe a~simple variant of the depth-first search which finds the
\paran{Bounding comparisons}%
We will now describe a~simple variant of the depth-first search which finds the
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$.
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, which is closer to the root, will be called its \df{top,}
+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
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
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])$.
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])$.
\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$.
\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$.
\::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
\::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
in the subtree rooted at~$v$.
\::Prepare the array of the peaks~$P_e$: Start with~$P_p$, remove the entries
in the subtree rooted at~$v$.
\::Prepare the array of the peaks~$P_e$: Start with~$P_p$, remove the entries
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
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
\::Recurse on~$v$: call $\<FindPeaks>(v,e,T_e,P_e)$.
\endalgo
\::Recurse on~$v$: call $\<FindPeaks>(v,e,T_e,P_e)$.
\endalgo
performs $\O(n+q)$ comparisons, where $n$ is the size of the tree and
$q$ is the number of query paths.
performs $\O(n+q)$ comparisons, where $n$ is the size of the tree and
$q$ is the number of query paths.
\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
\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
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}
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}
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.
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.
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}
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}
\section{Verification in linear time}\id{verifysect}%
We have proven that $\O(m)$ edge weight comparisons suffice to verify minimality
\section{Verification in linear time}\id{verifysect}%
We have proven that $\O(m)$ edge weight comparisons suffice to verify minimality
which finds the required comparisons in linear time. We will follow the idea
of King from \cite{king:verifytwo}, but as we have the power of the RAM data structures
from Section~\ref{bitsect} at our command, the low-level details will be easier,
which finds the required comparisons in linear time. We will follow the idea
of King from \cite{king:verifytwo}, but as we have the power of the RAM data structures
from Section~\ref{bitsect} at our command, the low-level details will be easier,
in the proof, the Bor\o{u}vka's algorithm runs in linear time. Constructing
the Bor\o{u}vka tree in the process adds at most a~constant overhead to every
step of the algorithm.
in the proof, the Bor\o{u}vka's algorithm runs in linear time. Constructing
the Bor\o{u}vka tree in the process adds at most a~constant overhead to every
step of the algorithm.
of Algorithm \ref{findpeaks} efficiently. We need a~compact representation of
the arrays $T_e$ and~$P_e$, which will allow to reduce the overhead of the algorithm
of Algorithm \ref{findpeaks} efficiently. We need a~compact representation of
the arrays $T_e$ and~$P_e$, which will allow to reduce the overhead of the algorithm
this goal, we will encode the arrays in RAM vectors (see Section \ref{bitsect}
for the vector operations).
this goal, we will encode the arrays in RAM vectors (see Section \ref{bitsect}
for the vector operations).
bits. As every tree edge is uniquely identified by its bottom vertex, we can
use the same encoding for \df{edge labels.}
bits. As every tree edge is uniquely identified by its bottom vertex, we can
use the same encoding for \df{edge labels.}
in constant time on the RAM, we precompute tables for these operations
like we did in the Q-heaps (cf.~Lemma \ref{qhprecomp}). A~table for word-sized
arguments would take too much time to precompute, so we will generally store
our data structures in \df{slots} of $s=\lceil 1/3\cdot\log n\rceil$ bits each.
in constant time on the RAM, we precompute tables for these operations
like we did in the Q-heaps (cf.~Lemma \ref{qhprecomp}). A~table for word-sized
arguments would take too much time to precompute, so we will generally store
our data structures in \df{slots} of $s=\lceil 1/3\cdot\log n\rceil$ bits each.
function whose arguments fit in two slots.
\em{Top masks:} The array~$T_e$ will be represented by a~bit mask~$M_e$ called the \df{top mask.} For each
of the possible tops~$t$ (i.e., the ancestors of the current vertex), we store
a~single bit telling whether $t\in T_e$. Each top mask fits in $\lceil\log n\rceil$
bits and therefore in a~single machine word. If needed, it can be split to three slots.
function whose arguments fit in two slots.
\em{Top masks:} The array~$T_e$ will be represented by a~bit mask~$M_e$ called the \df{top mask.} For each
of the possible tops~$t$ (i.e., the ancestors of the current vertex), we store
a~single bit telling whether $t\in T_e$. Each top mask fits in $\lceil\log n\rceil$
bits and therefore in a~single machine word. If needed, it can be split to three slots.
on the top masks.
\em{Small and big lists:} The heaviest edge found so far for each top is stored
by the algorithm in the array~$P_e$. Instead of keeping the real array,
we store the labels of these edges in a~list encoded in a~bit string.
Depending on the size of the list, we use one of two possible encodings:
on the top masks.
\em{Small and big lists:} The heaviest edge found so far for each top is stored
by the algorithm in the array~$P_e$. Instead of keeping the real array,
we store the labels of these edges in a~list encoded in a~bit string.
Depending on the size of the list, we use one of two possible encodings:
is stored in $\O(\log\log n)$ words, each of them containing a~slot-sized
vector. Unlike the small lists, we use the big lists as arrays. If a~top~$t$ of
depth~$d$ is active, we keep the corresponding entry of~$P_e$ in the $d$-th
is stored in $\O(\log\log n)$ words, each of them containing a~slot-sized
vector. Unlike the small lists, we use the big lists as arrays. If a~top~$t$ of
depth~$d$ is active, we keep the corresponding entry of~$P_e$ in the $d$-th
A~pointer is an~index to the nearest big list on the path from the small
list containing the pointer to the root. As each big list has at most $\lceil\log n\rceil$
fields, the pointer fits in~$\ell$ bits, but we need one extra bit to distinguish
A~pointer is an~index to the nearest big list on the path from the small
list containing the pointer to the root. As each big list has at most $\lceil\log n\rceil$
fields, the pointer fits in~$\ell$ bits, but we need one extra bit to distinguish
precompute a~table of the values of~$f$ for all values of arguments that fit
in a~single slot. The precomputation takes $\O(n)$ time.
precompute a~table of the values of~$f$ for all values of arguments that fit
in a~single slot. The precomputation takes $\O(n)$ time.
we can assume that we can compute the following functions in constant time:
\itemize\ibull
\:$\<Weight>(x)$ --- the Hamming weight of a~slot-sized number~$x$
(we already considered this operation in Algorithm \ref{lsbmsb}, but we needed
we can assume that we can compute the following functions in constant time:
\itemize\ibull
\:$\<Weight>(x)$ --- the Hamming weight of a~slot-sized number~$x$
(we already considered this operation in Algorithm \ref{lsbmsb}, but we needed
by splitting the number in three slots and adding their weights.
\:$\<FindKth>(x,k)$ --- the $k$-th set bit from the top of the slot-sized
by splitting the number in three slots and adding their weights.
\:$\<FindKth>(x,k)$ --- the $k$-th set bit from the top of the slot-sized
can be retained as they still refer to the same ancestor list.
\:\em{Big from big:} We can copy the whole~$P_p$, since the layout of the
can be retained as they still refer to the same ancestor list.
\:\em{Big from big:} We can copy the whole~$P_p$, since the layout of the
\>We are now ready to combine these steps and get the following theorem:
\thmn{Verification of MST on the RAM}\id{ramverify}%
\>We are now ready to combine these steps and get the following theorem:
\thmn{Verification of MST on the RAM}\id{ramverify}%
\paran{Verification on the Pointer Machine}\id{pmverify}%
Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time
verification can be achieved even on the Pointer Machine. They first solve the
problem of finding the lowest common ancestors for a~set of pairs of vertices
by batch processing: They combine an~algorithm of time complexity $\O(m\timesalpha(m,n))$
based on the Disjoint Set Union data structure with the framework of topological graph
\paran{Verification on the Pointer Machine}\id{pmverify}%
Buchsbaum et al.~\cite{buchsbaum:verify} have recently shown that linear-time
verification can be achieved even on the Pointer Machine. They first solve the
problem of finding the lowest common ancestors for a~set of pairs of vertices
by batch processing: They combine an~algorithm of time complexity $\O(m\timesalpha(m,n))$
based on the Disjoint Set Union data structure with the framework of topological graph
technique for finding the peaks themselves.
\paran{Online verification}%
The online version of this problem has turned out to be more difficult. It calls for an~algorithm
that preprocesses the tree and then answers queries for peaks of paths presented online. Pettie
\cite{pettie:onlineverify} has proven an~interesting lower bound based on the inverses of the
technique for finding the peaks themselves.
\paran{Online verification}%
The online version of this problem has turned out to be more difficult. It calls for an~algorithm
that preprocesses the tree and then answers queries for peaks of paths presented online. Pettie
\cite{pettie:onlineverify} has proven an~interesting lower bound based on the inverses of the
-Ackermann's function (see \ref{ackerinv}). If we want to answer queries within $t$~comparisons, we
-have to invest $\Omega(n\log\lambda_t(n))$ time into preprocessing. This implies that with
+Ackermann's function. If we want to answer queries within $t$~comparisons, we
+have to invest $\Omega(n\log\lambda_t(n))$ time into preprocessing.\foot{$\lambda_t(n)$ is the
+$t$-th row inverse of the Ackermann's function, $\alpha(n)$ is its diagonal inverse. See
+\ref{ackerinv} for the exact definitions.} This implies that with
preprocessing in linear time, the queries require $\Omega(\alpha(n))$ time.
%--------------------------------------------------------------------------------
\section{A randomized algorithm}\id{randmst}%
preprocessing in linear time, the queries require $\Omega(\alpha(n))$ time.
%--------------------------------------------------------------------------------
\section{A randomized algorithm}\id{randmst}%
we observed that while the number of vertices per iteration decreases exponentially,
the number of edges generally does not, so we spend $\Theta(m)$ time on every phase.
Karger, Klein and Tarjan \cite{karger:randomized} have overcome this problem by
we observed that while the number of vertices per iteration decreases exponentially,
the number of edges generally does not, so we spend $\Theta(m)$ time on every phase.
Karger, Klein and Tarjan \cite{karger:randomized} have overcome this problem by
Since we need the MST verification algorithm for finding the $T$-heavy edges,
we will assume that we are working on the RAM.
Since we need the MST verification algorithm for finding the $T$-heavy edges,
we will assume that we are working on the RAM.
-with probability~$p$ and $F$~the minimum spanning forest of~$H$. Then the
-expected number of $F$-nonheavy\foot{These include $F$-light edges and also
-edges of~$F$ itself.}
+with probability~$p$. Let further $F$~be the minimum spanning forest of~$H$. Then the
+expected number of $F$-nonheavy\foot{That is, $F$-light edges and also edges of~$F$ itself.}
edges in~$G$ is at most $n/p$.
\proof
Let us observe that we can obtain the forest~$F$ by running the Kruskal's algorithm
(\ref{kruskal}) combined with the random process producing~$H$ from~$G$. We sort all edges of~$G$
by their weights and we start with an~empty forest~$F$. For each edge, we first
edges in~$G$ is at most $n/p$.
\proof
Let us observe that we can obtain the forest~$F$ by running the Kruskal's algorithm
(\ref{kruskal}) combined with the random process producing~$H$ from~$G$. We sort all edges of~$G$
by their weights and we start with an~empty forest~$F$. For each edge, we first
tails, we discard the edge. Otherwise we perform a~single step of the Kruskal's
algorithm: We check whether $F+e$ contains a~cycle. If it does, we discard~$e$, otherwise
we add~$e$ to~$F$. At the end, we have produced the subgraph~$H$ and its MSF~$F$.
tails, we discard the edge. Otherwise we perform a~single step of the Kruskal's
algorithm: We check whether $F+e$ contains a~cycle. If it does, we discard~$e$, otherwise
we add~$e$ to~$F$. At the end, we have produced the subgraph~$H$ and its MSF~$F$.
The number of $F$-nonheavy edges is therefore equal to the total number of the coin
flips in step~2 of this algorithm. We also know that the algorithm stops before
it adds $n$~edges to~$F$. Therefore it flips at most as many coins as a~simple
The number of $F$-nonheavy edges is therefore equal to the total number of the coin
flips in step~2 of this algorithm. We also know that the algorithm stops before
it adds $n$~edges to~$F$. Therefore it flips at most as many coins as a~simple
-random process which repeatedly flips until it gets~$n$ heads. As waiting for
-every occurence of heads takes expected time~$1/p$, waiting for~$n$ heads
+random process that repeatedly flips until it gets~$n$ heads. As waiting for
+every occurrence of heads takes expected time~$1/p$, waiting for~$n$ heads
must take $n/p$. This is the bound we wanted to achieve.
\qed
\para
We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
must take $n/p$. This is the bound we wanted to achieve.
\qed
\para
We will formulate the algorithm as a~doubly-recursive procedure. It alternatively
As in all contractive algorithms, we use edge labels to keep track of the
original locations of the edges in the input graph. For the sake of simplicity,
As in all contractive algorithms, we use edge labels to keep track of the
original locations of the edges in the input graph. For the sake of simplicity,
\algn{MSF by random sampling --- the KKT algorithm}\id{kkt}%
\algo
\algin A~graph $G$ with an~edge comparison oracle.
\:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
\:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
\algn{MSF by random sampling --- the KKT algorithm}\id{kkt}%
\algo
\algin A~graph $G$ with an~edge comparison oracle.
\:Remove isolated vertices from~$G$. If no vertices remain, stop and return an~empty forest.
\:Perform two Bor\o{u}vka steps (iterations of Algorithm \ref{contbor}) on~$G$ and
- remember the set~$B$ of edges contracted.
-\:Select subgraph~$H\subseteq G$ by including each edge independently with
+ remember the set~$B$ of the edges having been contracted.
+\:Select a~subgraph~$H\subseteq G$ by including each edge independently with
probability $1/2$.
\:$F\=\msf(H)$ calculated recursively.
\:Construct $G'\subseteq G$ by removing all $F$-heavy edges of~$G$.
probability $1/2$.
\:$F\=\msf(H)$ calculated recursively.
\:Construct $G'\subseteq G$ by removing all $F$-heavy edges of~$G$.
of the tree, we denote the number of vertices and edges of the corresponding subproblem~$G_v$
by~$n_v$ and~$m_v$ respectively.
If $m_v>0$, the recursion continues: the left son of~$v$ corresponds to the
of the tree, we denote the number of vertices and edges of the corresponding subproblem~$G_v$
by~$n_v$ and~$m_v$ respectively.
If $m_v>0$, the recursion continues: the left son of~$v$ corresponds to the
of vertices drops at least by a~factor of four in every recursive call. The size of a~subproblem~$G_v$
at level~$i$ is therefore at most $n/4^i$ and the depth of the tree is at most $\lceil\log_4 n\rceil$.
As there are no more than~$2^i$ subproblems at level~$i$, the sum of all~$n_v$'s
of vertices drops at least by a~factor of four in every recursive call. The size of a~subproblem~$G_v$
at level~$i$ is therefore at most $n/4^i$ and the depth of the tree is at most $\lceil\log_4 n\rceil$.
As there are no more than~$2^i$ subproblems at level~$i$, the sum of all~$n_v$'s
We are going to show that the worst case of the KKT algorithm is not worse than
of the plain contractive algorithm, while the average case is linear.
\lemma
We are going to show that the worst case of the KKT algorithm is not worse than
of the plain contractive algorithm, while the average case is linear.
\lemma
but as its worst-case depth is at most~$\lceil \log_4 n\rceil$, the tree
is always a~subtree of the complete binary tree of that depth. We will
therefore prove the theorem by examining the complete tree, possibly with
but as its worst-case depth is at most~$\lceil \log_4 n\rceil$, the tree
is always a~subtree of the complete binary tree of that depth. We will
therefore prove the theorem by examining the complete tree, possibly with
son) form a~set of \df{left paths.} Let us consider the expected time spent on
a~single left path. When walking the path downwards from its top vertex~$r$,
the expected size of the subproblems decreases exponentially: for a~son~$\ell$
son) form a~set of \df{left paths.} Let us consider the expected time spent on
a~single left path. When walking the path downwards from its top vertex~$r$,
the expected size of the subproblems decreases exponentially: for a~son~$\ell$
With the exception of the path going from the root of the tree,
the top~$r$ of a~left path is always a~right son of a~unique parent vertex~$v$.
Since the subproblem~$G_r$ has been obtained from its parent subproblem~$G_v$
With the exception of the path going from the root of the tree,
the top~$r$ of a~left path is always a~right son of a~unique parent vertex~$v$.
Since the subproblem~$G_r$ has been obtained from its parent subproblem~$G_v$
$\E m_r \le 2n_v$. The sum of the expected sizes of all top subproblems is
then $\sum_r n_r + m_r \le \sum_v 3n_v = \O(n)$. After adding the exceptional path
from the root, we get $\O(m+n)=\O(m)$.
$\E m_r \le 2n_v$. The sum of the expected sizes of all top subproblems is
then $\sum_r n_r + m_r \le \sum_v 3n_v = \O(n)$. After adding the exceptional path
from the root, we get $\O(m+n)=\O(m)$.
-We could also use a~slightly different formulation of the sampling lemma
-suggested by Chan \cite{chan:backward}. It changes the selection of the subgraph~$H$
+We could also use a~slightly different formulation of the Sampling lemma
+suggested by Chan \cite{chan:backward}. He changes the selection of the subgraph~$H$
to choosing an~$mp$-edge subset of~$E(G)$ uniformly at random. The proof is then
a~straightforward application of the backward analysis method. We however preferred
the Karger's original version, because generating a~random subset of a~given size
to choosing an~$mp$-edge subset of~$E(G)$ uniformly at random. The proof is then
a~straightforward application of the backward analysis method. We however preferred
the Karger's original version, because generating a~random subset of a~given size