diff options
| -rw-r--r-- | mgr.tex | 60 |
1 files changed, 44 insertions, 16 deletions
@@ -783,22 +783,50 @@ singletons constructed according to the following rules: were assigned to parts when its children were handled. \end{enumerate} -Note that in the last rule, both $v_l$ and $v_r$ will either themselves be -elements of $W$ or will have descendants in $W$ in only one of their subtrees. -In the first case, we will have already handled them. Otherwise, we will handle -them with a rule different than the last one, thus only one part will be added -to the partition for each of them. In particular, each element of $W$ will -contribute only a constant number of parts to the partition (one part if handled -with one of the first three rules, three parts if handled with the last one). - -To see that indeed, for example $v_l$, won't need to be handled with rule 4, if -it wasn't in $W$ but had descendants from $W$ in both its subtrees, then $W$ -wouldn't have been LCA closed. - -Thus the partition covers the entire tree with $O(|W|)$ parts. - -If $W$ is not LCA closed, we will call the LCA partition with respect to $W$ -simply the partition with respect to $W$'s LCA closure. +If $W$ is not parition ready, we will call the LCA partition with respect to $W$ +the partition with respect to the minimal partition ready set that contains $W$. +Skipping ahead, the LCA partition of the set of vertices relabeled in a +relabeling question will be the partition we alluded to at the end of the +previous section. We promised that this partition will have $O(m)$ parts, so we +must show that for a set $W$, the minimal partition ready set containing it is +of size $O(|W|)$. + +Take a set of $m$ tree vertices $W$ and consider the following procedure: + +\begin{enumerate} + \item Let $W'$ be $W$ with the tree's root added. + \item\label{partition-ready-lca-step} Let $W''$ be the LCA closure of $W'$. + \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every element of $W''$ that has + elements of $W''$ in both its subtrees, the element's both children. +\end{enumerate} + +\begin{claim} + The above procedure produces the minimal parition ready set containing $W$ + and each step adds at most $O(m)$ new vertices. +\end{claim} + +By defintition of LCA closure, $W''$ above is the smallest LCA closed set +containing $W$ and the tree's root. Step \ref{partition-ready-last-step} adds at +most $2|W''|$ new vertices, we will now prove that these are exactly the only +vertices still needed to be added to arrive at a partition ready set. That only +$O(m)$ vertices are added in step \ref{partition-ready-lca-step} will be proved in +the next section. + +It's easy to see that $W'''$ is still LCA closed. It is obvious that it is +necessary to add at least all the vertices added in step +\ref{partition-ready-last-step}, otherwise property \ref{both-subtrees-property} +of partition readiness won't be satisfied. What we will show is that no other +new vertices need to be added. Take $v \in W''$ that had descendants in $W''$ in +both its subtrees, let $v_l$ and $v_r$ be its left and right child, +respectively. Without loss of generality, suppose $v_l$ was not an element of +$W''$. Then we claim that it has descendants in $W''$ in only one of its +subtrees. Indeed, if it did have descendants from $W''$ in both its subtrees, +$W''$ wouldn't have been LCA closed -- $v_l$ would have been the LCA of the +topmost members of $W''$ of its left and right subtrees. Note that newly added +elements of $W'''$ can appear only underneath vertices that were originally in +$W''$, so if $v_l$ didn't have an element of $W''$ in one of its subtrees, then +it also doesn't have elements of $W'''$ in that subtree. Thus $W'''$ is indeed +the minimal partition ready set containing $W$. \subsection{Computing the LCA closure}\label{computing-closure} |