Complete proof for LCA closure

1 files changed, 37 insertions, 2 deletions

diff --git a/mgr.tex b/mgr.tex
index 7bc1ef2..27bdeba 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -833,7 +833,7 @@ minimal partition ready set containing $W$.
 
 \subsection{Computing the LCA closure}\label{computing-closure}
 
-\begin{lemma}
+\begin{lemma}\label{lca-lemma}
     After linear preprocessing of a tree $T$, the LCA closure of a set of $m$
     tree vertices $W \subseteq V(T)$ can be computed in time $O(m \log m)$, and
     the size of the closure is linear in the size of $W$.
@@ -846,7 +846,7 @@ Now to compute the closure of $W$, we first sort the vertices in $W$ with
 respect to their in-order numbers, so we end up with a list $v_1, \ldots, v_m$
 of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$.
 
-\begin{observation}
+\begin{observation}\label{infix-observation}
     If $\infixtable[u] < \infixtable[v] < \infixtable[w]$, then $\mathlca(u, w)$
     is equal to either $\mathlca(u, v)$ or $\mathlca(v, w)$.
 \end{observation}
@@ -877,6 +877,41 @@ $U$ is of size $O(m)$ and can be computed in time $O(m)$ by issuing LCA queries
 to successive pairs of the sorted $W$. We claim that $W' := W \cup U$ is the LCA
 closure of $W$.
 
+Let's define $u_i := LCA(v_i, v_{i+1})$. By Observation
+\ref{lca-observation}, each $u_i$ falls between $v_i$ and $v_{i+1}$ in the infix
+order, i.e. $W'$ sorted is the sequence $v_1, u_1, v_2, u_2, \ldots, u_{m - 1},
+v_m$ (note that in the way this sequence is written, some vertices might be
+repeated, e.g. it might be the case that $LCA(v_2, v_3) = v_2$, in which case
+$u_2$ will be equal to $v_2$). We claim that for every pair of vertices in $W'$,
+their LCA is also in $W'$. We'll proceed by induction, and it will be easier if
+we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2, \ldots, w_{2m-2} :=
+u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following are properties of the
+sequence of $w_i$'s:
+
+\begin{enumerate}
+    \item For $i < j$, $\infixtable[w_i] \leq \infixtable[w_j]$.
+    \item For odd $i$, $w_i$ comes from the original set $W$.
+    \item For even $i$, $w_i$ comes from the set of added vertices $U$. In
+        particular, $w_i$ is equal to $LCA(w_{i-1}, w_{i+1})$.
+\end{enumerate}
+
+We prove that $W'$ is LCA closed by showing that for all pairs $w_i, w_j$, their
+LCA belongs to $W'$, by induction on the difference between $i$ and $j$.
+
+The base case is to show that the LCA of $w_i$ and $w_{i+1}$ is in $W'$ for
+every pair of successive vertices. Suppose $i$ is odd, then $w_{i+1}$ comes from
+$U$ and was constructed as the LCA of $w_i$ and $w_{i+2}$. Then $w_{i+1}$ must
+be on the path from $w_i$ to the root and is the LCA of the pair. Similarly for
+when $i$ is even.
+
+Now assume that for all $w_i$, $w_j$, if $j - i < k$ then $LCA(w_i, w_j)$ is in
+$W'$. We want to show the same is true when $j - i \leq k$. Take $w_i$ and $w_j$
+with $j - i = k$. Consider the triple $w_i$, $w_{i+1}$, $w_j$. By Observation
+\ref{infix-observation}, $LCA(w_i, w_j)$ is equal to $LCA(w_i, w_{i+1})$ or
+$LCA(w_{i+1}, w_j)$. By the induction assumption, we already know both of these
+are in $W$, thus showing $W'$ is LCA closed and finishing the proof of Lemma
+\ref{lca-lemma}
+
 \section{Computing root states of parts}
 
 Let's now discuss how we will use LCA paritions to solve the relabel query