From 13caeb89ef8876aaa087925f238e5f8252e1ce29 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 7 Apr 2008 15:51:02 +0200 Subject: [PATCH] Call subgraphs clusters. --- opt.tex | 70 ++++++++++++++++++++++++++++----------------------------- 1 file changed, 35 insertions(+), 35 deletions(-) diff --git a/opt.tex b/opt.tex index 2d7335f..9de4d64 100644 --- a/opt.tex +++ b/opt.tex @@ -639,16 +639,16 @@ trick with expanding the vertex~$c$ to~$P$ in the cycle~$C$. Hence $g\not\in\mst \para We still intend 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 that got corrupted in the process. +of non-overlapping contractible subgraphs called \df{clusters} and we put aside all edges that 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 MSF of~$G$, but a~sparser graph containing it, on which we can continue. We can formulate the exact partitioning algorithm and its properties as follows: -\algn{Partition a~graph to a~collection of contractible subgraphs}\id{partition}% +\algn{Partition a~graph to a~collection of contractible clusters}\id{partition}% \algo -\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the subgraphs, +\algin A~graph~$G$ with an~edge comparison oracle, a~parameter~$t$ controlling the size of the clusters, 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.} @@ -663,33 +663,33 @@ We can formulate the exact partitioning algorithm and its properties as follows: \:::$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[T]\}$. \cmt{Record the subgraph induced by the tree.} +\::$\C\=\C \cup \{G[T]\}$. \cmt{Record the cluster 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. +\algout The collection $\C$ of contractible clusters and the set~$R^\C$ of +corrupted edges in the neighborhood of these clusters. \endalgo -\thmn{Partitioning to contractible subgraphs, Chazelle \cite{chazelle:almostacker}}\id{partthm}% +\thmn{Partitioning to contractible clusters, 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 edges such that: +$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of edges such that: \numlist\ndotted -\: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$. +\:All the clusters and the set~$R^\C$ are mutually edge-disjoint. +\:Each cluster contains at most~$t$ vertices. +\:Each vertex of~$G$ is contained in at least one cluster. +\:The connected components of the union of all clusters 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) \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 -Claim~1: The Partition algorithm grows a~series of trees which induce the subgraphs~$C_i$ in~$G$. +Claim~1: The Partition algorithm grows a~series of trees which induce the clusters~$C_i$ in~$G$. 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. The edges that enter~$R^\C$ are immediately deleted from the graph, so they never participate @@ -719,15 +719,15 @@ $$\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 of the algorithm, +corrupted when constructing the cluster~$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_i$ by running the partial Jarn\'\i{}k's algorithm on the graph +In the $i$-th phase we construct the cluster~$C_i$ by running the partial Jarn\'\i{}k's algorithm on the graph $G_i = G\setminus\bigcup_{j procedure to split the graph into a~collection of -subgraphs of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision -trees to find the MSF of the subgraphs. The graph obtained by contracting -the subgraphs is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's -algorithm runs on it in linear time. Afterwards we combine the MSF's of the subgraphs +clusters of size~$t$ and a~set of corrupted edges. Then it uses precomputed decision +trees to find the MSF of the clusters. The graph obtained by contracting +the clusters is on the other hand dense enough, so that the Iterated Jarn\'\i{}k's +algorithm runs on it in linear time. Afterwards we combine the MSF's of the clusters and of the contracted graphs, we mix in the corrupted edges and run two iterations of the Contractive Bor\o{u}vka's algorithm. This guarantees reduction in the number of both vertices and edges by a~constant factor, so we can efficiently recurse on the @@ -1004,9 +1004,9 @@ resulting graph. \algo \algin A~connected graph~$G$ with an~edge comparison oracle. \:If $G$ has no edges, return an~empty tree. -\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of subgraphs} +\:$t\=\lfloor\log^{(3)} n\rfloor$. \cmt{the size of clusters} \:Call \ (\ref{partition}) on $G$ and $t$ with $\varepsilon=1/8$. It returns - a~collection~$\C=\{C_1,\ldots,C_k\}$ of subgraphs and a~set~$R^\C$ of corrupted edges. + a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges. \:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees. \:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph} \:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}). @@ -1035,21 +1035,21 @@ The first two steps of the algorithm are trivial as we have linear time at our disposal. By the Partitioning theorem (\ref{partthm}), the call to \ with~$\varepsilon$ -set to a~constant takes $\O(m)$ time and it produces a~collection of subgraphs of size +set to a~constant takes $\O(m)$ time and it produces a~collection of clusters of size at most~$t$ and at most $m/4$ corrupted edges. It also guarantees that the connected components of the union of the $C_i$'s have at least~$t$ vertices (unless there is just a~single component). To apply the decision trees, we will use the framework of topological computations developed -in Section \ref{bucketsort}. We pad all subgraphs in~$\C$ with isolated vertices, so that they +in Section \ref{bucketsort}. We pad all clusters in~$\C$ with isolated vertices, so that they have exactly~$t$ vertices. We use a~computation that labels the graph with a~pointer to its optimal decision tree. Then we apply Theorem \ref{topothm} combined with the brute-force construction of optimal decision trees from Lemma \ref{odtconst}. Together they guarantee -that we can assign the decision trees to the subgraphs in time: +that we can assign the decision trees to the clusters in time: $$\O\Bigl(\Vert\C\Vert + t^{t(t+2)} \cdot \bigl(2^{2^{4t^2}} + t^2\bigr)\Bigr) = \O\Bigl(m + 2^{2^{2^t}}\Bigr) = \O(m).$$ -Execution of the decision tree on each subgraph~$C_i$ then takes $\O(D(C_i))$ steps. +Execution of the decision tree on each cluster~$C_i$ then takes $\O(D(C_i))$ steps. The contracted graph~$G_A$ has at most $n/t = \O(n / \log^{(3)}n)$ vertices and asymptotically the same number of edges as~$G$, so according to Corollary \ref{ijdens}, the Iterated Jarn\'\i{}k's -- 2.39.2