From 19014393105b83a20f611cb978d939b71edaa533 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 1 Apr 2008 23:07:12 +0200 Subject: [PATCH] Robust contraction lemma. --- macros.tex | 1 + notation.tex | 2 + opt.tex | 120 +++++++++++++++++++++++++++++++++++++++++++-------- 3 files changed, 105 insertions(+), 18 deletions(-) diff --git a/macros.tex b/macros.tex index d29bd47..c25d711 100644 --- a/macros.tex +++ b/macros.tex @@ -52,6 +52,7 @@ \def\per{\mathop{\rm per}} \def\poly{\mathop{\rm poly}} \def\E{{\bb E}} +\def\crpt{\mathop{\Uparrow}} \def\brk{\hfil\break} diff --git a/notation.tex b/notation.tex index 83c6292..f954ee3 100644 --- a/notation.tex +++ b/notation.tex @@ -83,6 +83,8 @@ \n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]} \n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]} \n{$\per M$}{the permanent of a~square matrix~$M$} +\n{$G\crpt R$}{graph~$G$ with edges in~$R$ corrupted \[corrnota]} +\n{$R_C$}{$R_C = R\cup \delta(C)$ \[corrnota]} } %-------------------------------------------------------------------------------- diff --git a/opt.tex b/opt.tex index 95acd7e..7aa4c54 100644 --- a/opt.tex +++ b/opt.tex @@ -514,30 +514,114 @@ suffices to decrease~$\varepsilon$ twice. 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 we have seen so far is the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}). -It is based on a~simple, yet powerful idea: Use the Jarn\'\i{}k's algorithm with -limited heap size, so that it stops when the tree becomes large. Grow multiple -such trees, always starting in vertex not visited yet. All these trees lie 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 -version without active edges \ref{jarnik} as we the soft heap lacks the \ -operation) and patching the holes by some sort of duct tape. This honest, 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 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. Similarly, the Red lemma -(\ref{redlemma}) is true only if the heaviest edge on the cycle is not corrupted. +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 +large. Grow multiple such trees, always starting in a~vertex not visited yet. All +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 +version without active edges (\ref{jarnik}) as the soft heap lacks the \ +operation. This honest, 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 +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. +Similarly, the Red lemma (\ref{redlemma}) is true only if the heaviest edge on +the cycle is not corrupted. There is fortunately some light in this darkness. While the basic structural properties of MST's no longer hold, there is a~weaker form of the Contraction -lemma which takes the corrupted edges into account. Before we prove this lemma, +lemma that takes the corrupted edges into account. Before we prove this lemma, we will expand our awareness of subgraphs which can be contracted. \defn -A~subgraph $C\subset G$ is \df{contractible} iff for every pair of edges $e,f\in\delta(C)$\foot{That is, -with one endpoint in~$C$.} the subset +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 the edges $e,f$ such that all edges on this path are lighter than either $e$ or~$f$. + +\example +Let us see that when we stop the Jarn\'\i{}k's algorithm at some moment and +we take a~subgraph~$C$ induced by the constructed tree, this subgraph is contractible. +Indeed, when we consider any two distinct edges $uv, xy$ ($u,x\in C$ and $v,y\not\in C$), +they enter the algorithm's heap at some time. Without loss of generality $uv$~is the first. +Before the algorithm reaches the vertex~$x$, it adds the whole path $ux$ to the tree. +As the edge~$uv$ never leaves the heap, all edges on the path $ux$ must be lighter +than this edge. + +We can now easily reformulate the Contraction lemma (\ref{contlemma}) in the language +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)$. + +\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 trees on the same number of vertices, 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}). + +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 +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$ +and hence also than~$g$. Expanding~$c$ in the cycle to the path~$P$ then produces +a~cycle in~$G$ whose heaviest edge is~$g$. +\qed + +We are ready to bring corruption back to the game now and state a~``robust'' version +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 +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 +one endpoint lies in~$C$ by~$R_C$ (i.e., $R_C = R\cap \delta(C)$). + +\lemman{Robust contraction} +Let $G$ be a~weighted graph and $C$~its subgraph contractible in~$G\crpt R$ +for some set of edges~$R$. Then $\msf(G) \subseteq \msf(C) \cup \msf((G/C) \setminus R_C) \cup R_C$. + +\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 +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. +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 +also than~$g$. The weights of the edges of~$P$ in the original graph~$G$ cannot be higher than +in~$G\crpt R$, so the path~$P$ is lighter than~$g$ even in~$G$ and we can again perform the +trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst(G)$. +\qed + +\para +It therefore suffices to run the Jarn\'\i{}k's algorithm with a~soft heap to find the +$(G\crpt R)$-contractible subgraph~$C$ and then recurse three times: first find $\msf(C)$ +and $\msf((G/C)\setminus R_C)$, then put together the pieces which are known to contain +$\msf(G)$ by the Robust contraction lemma and find the MSF of this graph. As in the Iterative +Jarn\'\i{}k's algorithm, we will construct as many non-overlapping contractible subgraphs in a~single +phase of the algorithm as possible. Formally speaking, we will use the following partitioning +procedure. -- 2.39.2