From 769daee04c48cffa7bc414bdb35988ea21bb060a Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 3 Apr 2008 21:48:39 +0200
Subject: [PATCH] More on optimal decision trees.

---
 opt.tex | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 101 insertions(+)

diff --git a/opt.tex b/opt.tex
index 7c2d308..dca9bd5 100644
--- a/opt.tex
+++ b/opt.tex
@@ -859,8 +859,109 @@ $\O(\poly(k))$ per object. The time complexity of the whole algorithm is therefo
 $\O(2^{k^2} \cdot 2^{2^{3k^2}} \cdot 2^{k^3} \cdot \poly(k)) = \O(2^{2^{4k^2}})$.
 \qed
 
+\paran{Basic properties of decision trees}
+The following properties will be useful for analysis of algorithms based
+on precomputed decision trees. We will omit some technical details, referring
+the reader to section 5.1 of the Pettie's paper \cite{pettie:optimal}.
 
+\lemma
+The decision tree complexity $D(m,n)$ of the MSF satisfies:
+\numlist\ndotted
+\:$D(m,n) \ge m/2$ for $m,n > 2$.
+\:$D(m',n') \ge D(m,n)$ whenever $m'\ge m, n'\ge n$.
+\endlist
+
+\proof
+For every $m,n>2$ there is a~graph on $n$~vertices and $m$~edges such that
+every edge lies on a~cycle. Every correct MSF decision tree for this graph
+has to compare each edge at least once. Otherwise the decision tree cannot
+distinguish between the case when the edge has the lowest of all weights (and
+thus it is forced to belong to the MSF) and when it has the highest weight (so
+it is forced out of the MSF).
+
+Decision trees for graphs on $n'$~vertices can be used for graphs with $n$~vertices
+as well --- it suffices to add isolated vertices, which does not change the MSF.
+Similarly, we can increase $m$ to~$m'$ by adding edges parallel to an~existing
+edge and making them heavier than the rest of the graph, so that they can never
+belong to the MSF.
+\qed
+
+\defn
+Subgraphs $C_1,\ldots,C_k$ of a~graph~$G$ are called the \df{compartments} of~$G$
+iff they are edge-disjoint, their union is the whole graph~$G$ and
+$\msf(G) = \bigcup_i \msf(C_i)$ for every permutation of edge weights.
+
+\lemma\id{partiscomp}%
+The subgraphs $C_1,\ldots,C_k$ generated by the Partition procedure of the
+previous section (Algorithm \ref{partition}) are compartments of the graph
+$H=\bigcup_i C_i$.
+
+\proof
+The first and second condition of the definition of compartments follow
+from the Partitioning theorem (\ref{partthm}), so it remains to show that $\msf(H)$
+is the union of the MSF's of the individual compartments. By the Cycle rule
+(\ref{cyclerule}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
+it is the heaviest edge on some cycle. It is therefore sufficient to prove that
+every cycle in~$H$ is contained within a~single~$C_i$.
+
+Let us consider a~cycle $K\subseteq H$ and a~subgraph~$C_i$ such that it contains
+an~edge~$e$ of~$K$ and all subgraphs constructed later by the procedure do not contain
+any. If $K$~is not fully contained in~$C_i$, we can extend the edge~$e$ to a~maximal
+path contained in both~$K$ and~$C_i$. Since $C_i$ shares at most one vertex with the
+earlier components, there can be at most one edge from~$K$ adjacent to the maximal path,
+which is impossible.
+\qed
+
+\lemma
+Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then there exists an~optimal
+MSF decision tree for~$G$ that does not compare edges from distinct compartments.
+
+\proofsketch
+Consider a~subset~$\cal P$ of edge weight permutations~$w$ that satisfy $w(e) < w(f)$
+whenever $e\in C_i, f\in C_j, i<j$. For such permutations, no decision tree can
+gain any information on relations between edge weights in a~single compartment by
+inter-compartment comparisons --- the results of all such comparisons are determined
+in advance.
+
+Let us take an~arbitrary correct decision tree for~$G$ and restrict it to
+vertices reachable by computations on~$\cal P$. Whenever a~vertex contained
+an~inter-compartment comparison, it has lost one of its sons, so we can remove it
+by contracting its only outgoing edge. We observe that we get a~decision tree
+satisfying the desired condition and that this tree is correct.
+
+As for the correctness, the MSF of a~single~$C_i$ is uniquely determined by
+comparisons of its weights and the set~$\cal P$ contains all combinations
+of orderings of weights inside individual compartments. Therefore every
+spanning tree of every~$C_i$ and thus also of~$H$ is properly recognized.
+\qed
 
+\lemma\id{compartsum}%
+Let $C_1,\ldots,C_k$ be compartments of a~graph~$G$. Then $D(G) = \sum_i D(C_i)$.
+
+\proofsketch
+A~collection of decision trees for the individual compartments can be ``glued together''
+to a~decision tree for~$G$. We take the decision tree for~$C_1$, replace every its leaf
+by a~copy of the tree for~$C_2$ and so on. Every leaf~$\ell$ of the compound tree will be
+labeled with the union of labels of the original leaves encountered on the path from
+the root to the new leaf~$\ell$. This proves that $D(G) \le \sum_i D(C_i)$.
+
+The other inequality requires more effort. We use the previous lemma to transform
+the optimal decision tree for~$G$ to another of the same depth, but without inter-compartment
+comparisons. Then we prove by induction on~$k$ and then on the depth of the tree
+that the tree can be re-arranged, so that every computation first compares edges
+from~$C_1$, then from~$C_2$ and so on. This means that the tree can be decomposed
+to decision trees for the $C_i$'s and without loss of generality all trees for
+a~single~$C_i$ can be made isomorphic.
+\qed
+
+\cor
+If $C_1,\ldots,C_k$ are the subgraphs generated by the Partition procedure (Algorithm \ref{partition}),
+then $D(\bigcup_i C_i) = \sum_i D(C_i)$.
+
+\proof
+Lemma \ref{partiscomp} tells us that $C_1,\ldots,C_k$ are compartments of the graph
+$\bigcup C_i$, so we can apply Lemma \ref{compartsum} on them.
+\qed
 
 %--------------------------------------------------------------------------------
 
-- 
2.39.2