From 6c7791182ea6fa73905e8aaec7e4cf373ef56b6c Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 2 Apr 2008 17:21:08 +0200 Subject: [PATCH] Partitioning done. --- macros.tex | 6 +++ opt.tex | 116 ++++++++++++++++++++++++++++++----------------------- 2 files changed, 72 insertions(+), 50 deletions(-) diff --git a/macros.tex b/macros.tex index c25d711..f70ca7f 100644 --- a/macros.tex +++ b/macros.tex @@ -164,6 +164,12 @@ %%% FIXME \footline={\hss\twelverm\folio\hss} +% We have to redefine \big and friends as we are using 12pt symbols +\def\big#1{{\hbox{$\left#1\vbox to11.5\p@{}\right.\n@space$}}} +\def\Big#1{{\hbox{$\left#1\vbox to14.5\p@{}\right.\n@space$}}} +\def\bigg#1{{\hbox{$\left#1\vbox to17.5\p@{}\right.\n@space$}}} +\def\Bigg#1{{\hbox{$\left#1\vbox to20.5\p@{}\right.\n@space$}}} + %%% Enumerated lists %%% \newif\ifitem\itemtrue diff --git a/opt.tex b/opt.tex index 07da833..32477d9 100644 --- a/opt.tex +++ b/opt.tex @@ -564,7 +564,7 @@ A~subgraph $C\subseteq G$ is \df{contractible} iff for every pair of edges $e,f\ 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 +\example\id{jarniscont}% 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$), @@ -612,24 +612,24 @@ graph are pairwise distinct. While this is technically not true for the corrupti 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)$). +one endpoint lies in~$C$ by~$R^C$ (i.e., $R^C = R\cap \delta(C)$). -\lemman{Robust contraction} +\lemman{Robust contraction}\id{robcont}% 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$. +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$. +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 +(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 @@ -641,19 +641,7 @@ Our plan still is to mimic the Iterative Jarn\'\i{}k's algorithm. We will grow a 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 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. More precisely: - -\corn{Gradual robust contraction}\id{gradrc}% -Suppose that $G$~is a~weighted graph, $R$~a~set of its edges, and $\C=\{C_1,\ldots,C_k\}$ is a~collection -of subgraphs contractible in~$G\crpt R_\C$, where $R_\C = R_{C_1} \cup \ldots \cup R_{C_k}$. Then: -$$ -\msf(G) = \msf\left( \bigcup_i \msf(C_i) \cup \msf\biggl( \biggl( G / \bigcup_i C_i \biggr) \setminus R_\C \biggr) \cup R_\C \right). -$$ - -\proof -By iterating the previous lemma and noting that subgraphs contractible in~$G\crpt R^\prime_\C$ -for a~subset~$R^\prime_\C$ of $R_\C$ are also contractible in~$G\crpt R_\C$. -\qed +the final MSF, but a~sparser graph containing it, on which we can continue. We can formulate the exact partitioning algorithm as follows: @@ -662,47 +650,47 @@ We can formulate the exact partitioning algorithm as follows: \algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the subgraphs, and an~accuracy parameter~$\varepsilon$. \:Mark all vertices as ``live''. -\:$\C\=\emptyset$, $R_\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.} +\:$\C\=\emptyset$, $R^\C\=\emptyset$. \cmt{Start with an~empty collection and no corrupted edges.} \:While there is a~live vertex~$v_0$: -\::$K=\{v_0\}$. \cmt{vertices of the tree we currently grow} -\::$R=\emptyset$. \cmt{edges known to be corrupted} +\::$T=\{v_0\}$. \cmt{the tree we currently grow} +\::$K=\emptyset$. \cmt{edges known to be corrupted} \::\ a~soft heap with accuracy~$\varepsilon$ and \ the edges adjacent to~$v_0$ in it. -\::While the heap is not empty and $\vert K\vert \le t$: -\:::\ an~edge $uv$ from the heap, assume $u\in K$. -\:::If $uv$ was corrupted, add it to~$R$. -\:::If $v\in K$, drop the edge and repeat the previous two steps. -\:::$K\=K\cup\{v\}$. +\::While the heap is not empty and $\vert T\vert \le t$: +\:::\ an~edge $uv$ from the heap, assume $u\in T$. +\:::If $uv$ was corrupted, add it to~$K$. +\:::If $v\in T$, drop the edge and repeat the previous two steps. +\:::$T\=T\cup\{v\}$. \:::If $v$ is dead, break out of the current loop. \:::Insert all edges incident with~$v$ to the heap. -\::$\C\=\C \cup \{G[K]\}$. \cmt{Record the subgraph.} -\::\ the heap and add all remaining corrupted edges to~$R$. -\::$R_\C\=R_\C \cup \{ R_K \}$. \cmt{Record the ``interesting'' corrupted edges.} -\::$G\=G\setminus R_K$. \cmt{Remove the corrupted edges from~$G$.} -\::Mark all vertices of~$K$ as ``dead''. -\algout The collection $\C$ of contractible subgraphs and the set~$R_\C$ of +\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the subgraph induced by the tree.} +\::\ the heap and add all remaining corrupted edges to~$K$. +\::$R^\C\=R^\C \cup \{ K^T \}$. \cmt{Record the ``interesting'' corrupted edges.} +\::$G\=G\setminus K^T$. \cmt{Remove the corrupted edges from~$G$.} +\::Mark all vertices of~$T$ as ``dead''. +\algout The collection $\C$ of contractible subgraphs and the set~$R^\C$ of corrupted edges in the neighborhood of these subgraphs. \endalgo -\lemman{Partitioning to contractible subgraphs, Pettie \cite{pettie:optimal}}\id{partlemma}% +\thmn{Partitioning to contractible subgraphs, Pettie \cite{pettie:optimal}}\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: +$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges such that: \numlist\ndotted -\:All the $C_i$'s and the set~$R_\C$ are edge-disjoint. +\:All the $C_i$'s and the set~$R^\C$ are edge-disjoint. \:Each $C_i$ contains at most~$t$ vertices. \:Each vertex of~$G$ is contained in at least one~$C_i$. \:The connected components of the union of all $C_i$'s have at least~$t$ vertices each, - except perhaps for those which are equal to a~connected component of~$G\setminus R_\C$. -\:$\vert R_\C\vert \le 2\varepsilon m$. -\:$\msf(G) = \msf\Bigl( \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R_\C\bigr) \cup R_C \Bigr)$. + except perhaps for those which are equal to a~connected component of~$G\setminus R^\C$. +\:$\vert R^\C\vert \le 2\varepsilon m$. +\:$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\bigl((G / \bigcup_i C_i) \setminus R^\C\bigr) \cup R^\C$. \:The algorithm runs in time $\O(n+m\log (1/\varepsilon))$. \endlist \proof The 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 +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. @@ -711,24 +699,52 @@ Claim~4: We can show that each connected component has $t$~or more vertices as w 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 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~$G\setminus R^\C$). -Claim~5: The set~$R_\C$ contains a~subset of edges corrupted by the soft heaps over +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 in every direction, the heaps can corrupt at worst $2\varepsilon m$ edges altogether. -Claim~6 follows from the above Corollary \ref{gradrc} on Gradual robust contraction. -\FIXME{It does not so far!} +We will prove the remaining two claims as separate lemmata. +\qed + +\lemman{Correctness of Partition, Claim 6 of Theorem \ref{partthm}} +$$\msf(G) \subseteq \bigcup_i \msf(C_i) \cup \msf\biggl( \bigl(G / \bigcup_i C_i \bigr) \setminus R^\C\biggr) \cup R^\C.$$ -It remains to calculate the time complexity (claim~7): -The inner loop (steps 7--13) processes the edges of the current subgraph~$G[K]$ and also -the edges in its neighborhood $\delta(G[K])$. Steps 6 and~13 insert each such edge to the heap +\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. +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