From 9986fbd5d1ee200de6876128901a31884ce88b4a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 6 Apr 2008 18:45:02 +0200 Subject: [PATCH] Corrections to robust contractions. --- opt.tex | 96 ++++++++++++++++++++++++++++++--------------------------- 1 file changed, 50 insertions(+), 46 deletions(-) diff --git a/opt.tex b/opt.tex index 9a3a76f..2d76688 100644 --- a/opt.tex +++ b/opt.tex @@ -516,7 +516,7 @@ against each \. This yields the time bound. \rem When we set $\varepsilon = 1/2n$, the soft heap is not allowed to corrupt any -items, so it can be used like any usual heap. By the standard lower bound on +items, so it can be used like any traditional heap. By the standard lower bound on sorting it therefore requires $\Omega(\log n)$ time per operation, so the time complexity is optimal for this choice of~$\varepsilon$. Chazelle \cite{chazelle:softheap} proves that it is optimal for every choice of~$\varepsilon$. @@ -532,7 +532,7 @@ suffices to decrease~$\varepsilon$ twice. \section{Robust contractions} Having the soft heaps at hand, we would like to use them in a~conventional MST -algorithm in place of a~usual heap. The most efficient specimen of a~heap-based +algorithm in place of a~traditional heap. The most efficient specimen of a~heap-based algorithm we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}). It is based on a~simple, yet powerful idea: Run the Jarn\'\i{}k's algorithm with limited heap size, so that it stops when the neighborhood of the tree becomes @@ -541,11 +541,11 @@ these trees are contained in the MST, so by the Contraction lemma (\ref{contlemma}) we can contract each of them to a~single vertex and iterate the algorithm on the resulting graph. -We can try implanting the soft heap in this algorithm, preferably in the original +We can try implanting the soft heap in this algorithm, preferably in its earlier version without active edges (\ref{jarnik}) as the soft heap lacks the \ -operation. This honest, but somewhat simple-minded attempt is however doomed to +operation. This brave, but somewhat simple-minded attempt is however doomed to fail. The reason is of course the corruption of items inside the heap, which -leads to increase of weights of a~subset of edges. In presence of corrupted +leads to increase of weights of some subset of edges. In presence of corrupted edges, most of the theory we have so carefully built breaks down. For example, the Blue lemma (\ref{bluelemma}) now holds only when we consider a~cut with no corrupted edges, with a~possible exception of the lightest edge of the cut. @@ -559,7 +559,7 @@ we will expand our awareness of subgraphs which can be contracted. \defn A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is, -edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints +of~$G$ edges with exactly one endpoint in~$C$.} there exists a~path in~$C$ connecting the endpoints of the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$. \example\id{jarniscont}% @@ -575,23 +575,23 @@ We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the lan of contractible subgraphs. We again assume that we are working with multigraphs and that they need not be connected. Furthermore, we slightly abuse the notation and we omit the explicit bijection -between $G-C$ and~$G/C$, so we can write $G=C \cup (G/C)$. +between $G-C$ and~$G/C$, so that we can write $G=C \cup (G/C)$. \lemman{Generalized contraction} When~$C\subseteq G$ is a~contractible subgraph, then $\msf(G)=\msf(C) \cup \msf(G/C)$. \proof As both sides of the equality are forests spanning the same graph, it suffices -to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$. We know that the edges which -does not participate in the MSF are exactly those which are the heaviest on some cycle -(this is the Cycle rule \ref{cyclerule}). +to show that $\msf(G) \subseteq \msf(C)\cup\msf(G/C)$. We know that the edges that +do not participate in the MSF of some graph are exactly those which are the heaviest +on some cycle (this is the Cycle rule, \ref{cyclerule}). Whenever an~edge~$g$ lies in~$C$, but not in~$\msf(C)$, then $g$~is the heaviest edge on some cycle in~$C$. As this cycle is also contained in~$G$, the edge $g$~does not participate in $\msf(G)$ either. Similarly for $g\in (G/C)\setminus\msf(G/C)$: when the cycle does not contain -the vertex~$c$ to which we contracted the subgraph~$C$, the cycle is present +the vertex~$c$ to which we have contracted the subgraph~$C$, this cycle is present in~$G$, too. Otherwise we consider the edges $e,f$ adjacent to~$c$ on this cycle. Since $C$~is contractible, there must exist a~path~$P$ in~$C$ connecting the endpoints of~$e$ and~$f$ in~$G$, such that all edges of~$P$ are lighter than either $e$ or~$f$ @@ -605,8 +605,8 @@ of this lemma. A~notation for corrupted graphs will be handy: \nota\id{corrnota}% When~$G$ is a~weighted graph and~$R$ a~subset of its edges, we will use $G\crpt R$ to denote an arbitrary graph obtained from~$G$ by increasing the weights of -some of the edges in~$R$. As usually, we will assume that all edge weights in this -graph are pairwise distinct. While this is technically not true for the corruption +some of the edges in~$R$. As usually, we will assume that all edges of this graph +have pairwise distinct weights. While this is technically not true for the corruption caused by soft heaps, we can easily make the weights unique. If~$C$ is a~subgraph of~$G$, we will refer to the edges of~$R$ whose exactly @@ -618,14 +618,14 @@ for some set of edges~$R$. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setm \proof We will modify the proof of the previous lemma. We will again consider all possible types -of edges which do not belong to the right-hand side and show that they are the +of edges which do not belong to the right-hand side and we will show that they are the heaviest edges of certain cycles. Every edge~$g$ of~$G$ lies either in~$C$, or in $H=(G/C)\setminus R^C$, or possibly in~$R^C$. If $g\in C\setminus\msf(C)$, then the same argument as before applies. -If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $e$~is the heaviest. -When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are finished. +If $g\in H\setminus\msf(H)$, we consider the cycle in~$H$ on which $g$~is the heaviest. +When $c$ (the vertex to which we have contracted~$C$) is outside this cycle, we are done. Otherwise we observe that the edges $e,f$ adjacent to~$c$ on this cycle cannot be corrupted (they would be in~$R^C$ otherwise, which is impossible). By contractibility of~$C$ there exists a~path~$P$ in~$(G\crpt R)\cup C$ such that all edges of~$P$ are lighter than $e$ or~$f$ and hence @@ -635,11 +635,11 @@ trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst \qed \para -Our plan still is to mimic the Iterative Jarn\'\i{}k's algorithm. We will grow a~collection~$\C$ -of non-overlapping contractible subgraphs and put aside the edges which got corrupted in the process. -We recursively compute the MSF of the subgraphs and of the contracted graph. Then we take the +Our plan still is to mimic the Iterative Jarn\'\i{}k's algorithm. We will partition the given graph to a~collection~$\C$ +of non-overlapping contractible subgraphs and put aside all edges which got corrupted in the process. +We recursively compute the MSF of that subgraphs and of the contracted graph. Then we take the union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce -the final MSF, but a~sparser graph containing it, on which we can continue. +the MSF of~$G$, but a~sparser graph containing it, on which we can continue. We can formulate the exact partitioning algorithm as follows: @@ -650,8 +650,8 @@ We can formulate the exact partitioning algorithm as follows: \:Mark all vertices as ``live''. \:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.} \:While there is a~live vertex~$v_0$: -\::$T=\{v_0\}$. \cmt{the tree we currently grow} -\::$K=\emptyset$. \cmt{edges known to be corrupted} +\::$T=\{v_0\}$. \cmt{the tree that we currently grow} +\::$K=\emptyset$. \cmt{edges known to be corrupted in the current iteration} \::\ a~soft heap with accuracy~$\varepsilon$ and \ the edges adjacent to~$v_0$ in it. \::While the heap is not empty and $\vert T\vert \le t$: \:::\ an~edge $uv$ from the heap, assume $u\in T$. @@ -671,8 +671,8 @@ corrupted edges in the neighborhood of these subgraphs. \thmn{Partitioning to contractible subgraphs, Chazelle \cite{chazelle:almostacker}}\id{partthm}% Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$) -and~$t$, the Partition algorithm \ref{partition} constructs a~collection -$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges such that: +and~$t$, the Partition algorithm (\ref{partition}) constructs a~collection +$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of edges such that: \numlist\ndotted \:All the $C_i$'s and the set~$R^\C$ are edge-disjoint. @@ -686,18 +686,22 @@ $\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges such th \endlist \proof -The algorithm grows a~series of trees. A~tree is built from edges adjacent to live vertices +Claim~1: The Partition algorithm grows a~series of trees. A~tree is built from edges adjacent to live vertices and once it is finished, all vertices of the tree die, so no edge is ever reused in another -tree. Edges of~$R^\C$ are immediately deleted from the graph, so they never participate -in any tree. The algorithm stops only if all vertices are dead, so each vertex must have -entered some tree. Each $C_i$ is induced by some tree and the trees have at most~$t$ vertices -each, which limits the size of the $C_i$'s as well. This proves claims 1--3. +tree. The edges of~$R^\C$ are immediately deleted from the graph, so they never participate +in any tree. + +Claim~2: The algorithm stops only if all vertices are dead, so each vertex must have +entered some tree. + +Claim~3: Each $C_i$ is induced by some tree and the trees have at most~$t$ vertices +each, which limits the size of the $C_i$'s as well. Claim~4: We can show that each connected component has $t$~or more vertices as we already did -in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it already -has~$t$ vertices, or it joins one of the existing trees (which only increases the +in the proof of Lemma \ref{ijsize}: How can a~new tree stop growing? Either it gathers +$t$~vertices, or it joins one of the existing trees (this only increases the size of the component), or the heap becomes empty (which means that the tree spans -a~full component of the current graph and hence also of~$G\setminus R^\C$). +a~full component of the current graph and hence also of the final~$G\setminus R^\C$). Claim~5: The set~$R^\C$ contains a~subset of edges corrupted by the soft heaps over the course of the algorithm. As every edge is inserted to a~heap at most once @@ -711,24 +715,24 @@ $$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\biggl( \bigl(G / \bigcup_i C_i \proof By iterating the Robust contraction lemma (\ref{robcont}). Let $K_i$ be the set of edges -corrupted when constructing the subgraph~$C_i$ in the $i$-th phase (iteration of the outer -loop) of the algorithm, and similarly for the state of the other variables at that time. +corrupted when constructing the subgraph~$C_i$ in the $i$-th phase of the algorithm, +and similarly for the state of the other variables at that time. We will use induction on~$i$ to prove that the lemma holds at the end of every phase. At the beginning, the statement is obviously true, even as an~equality. -In the $i$-th phase, we construct the subgraph~$C_j$ by running the partial Jarn\'\i{}k's algorithm on the graph -$G_i = G\setminus\bigcup_{j