From 25ba24c0773c8e4f2536f0f9d868b4f6f9005d89 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 17 Mar 2008 18:29:11 +0100 Subject: [PATCH] More KKT. --- adv.tex | 53 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 44 insertions(+), 9 deletions(-) diff --git a/adv.tex b/adv.tex index 99d8002..58d3c5c 100644 --- a/adv.tex +++ b/adv.tex @@ -1145,17 +1145,20 @@ we do not mention it in the algorithm. Let us analyse the time complexity this algorithm by studying properties of its \df{recursion tree.} The tree describes the subproblems processed by the recursive calls. For any vertex~$t$ of the tree, we denote the number of vertices and edges of the corresponding subproblem~$G_t$ -by~$n_t$ and~$m_t$ respectively. If $m_t>0$, the recursion continues: the left son of~$t$ -corresponds to the call on the sampled subgraph~$H$, the right son to the reduced -graph~$G'$. The root of the recursion tree is obviously the original graph~$G$, the -leaves are trivial graphs with no edges. +by~$n_t$ and~$m_t$ respectively. +If $m_t>0$, the recursion continues: the left son of~$t$ corresponds to the +call on the sampled subgraph~$H_t$, the right son to the reduced graph~$G^\prime_t$. +(Similarly, we use letters subscripted with~$t$ for the state of the other variables +of the algorithm.) +The root of the recursion tree is obviously the original graph~$G$, the leaves are +trivial graphs with no edges. \obs The Bor\o{u}vka steps together with the removal of isolated vertices guarantee that the number of vertices drops at least by a~factor of four in every recursive call. The size of a~subproblem~$G_t$ -at level~$\ell$ is therefore at most $n/4^\ell$ and the depth of the tree is at most $\lceil\log_4 n\rceil$. -As there are no more than~$2^\ell$ subproblems at level~$\ell$, the sum of all~$n_t$'s -on that level is at most $n/2^\ell$, which is at most~$2n$ summed over the whole tree. +at level~$i$ is therefore at most $n/4^i$ and the depth of the tree is at most $\lceil\log_4 n\rceil$. +As there are no more than~$2^i$ subproblems at level~$i$, the sum of all~$n_t$'s +on that level is at most $n/2^i$, which is at most~$2n$ summed over the whole tree. \lemma For every subproblem~$G_t$, the KKT algorithm spends time $\O(m_t+n_t)$ plus the time @@ -1164,15 +1167,47 @@ spent on the recursive calls. \proof We know from Lemma \ref{contiter} that each Bor\o{u}vka step takes time $\O(m_t+n_t)$.\foot{We add $n_t$ as the graph could be disconnected.} -The selection of the edges of~$H$ is straightforward. -Finding the $F$-heavy edges is not, but we have already shown in Theorem \ref{ramverify} +The selection of the edges of~$H_t$ is straightforward. +Finding the $F_t$-heavy edges is not, but we have already shown in Theorem \ref{ramverify} that linear time is sufficient on the RAM. \qed \thmn{Worst-case complexity of the KKT algorithm} The KKT algorithm runs in time $\O(\min(n^2,m\log n))$ in the worst case on the RAM. +\proof +The argument for the $\O(n^2)$ bound is similar to the analysis of the plain +contractive algorithm. As every subproblem~$G_t$ is a~simple graph, the number +of its edges~$m_t$ is less than~$n_t^2$. By the previous lemma, we spend time +$\O(n_t^2)$ there. Summing over all subproblems yields $\sum_t \O(n_t^2) = +\O((\sum_t n_t)^2) = \O(n^2)$. + +In order to prove the $\O(m\log n)$ bound, it is sufficient to show that the total time +spent on every level of the recursion tree is $\O(m)$. Suppose that $t$~is a~vertex +of the recursion tree with its left son~$\ell$ and right son~$r$. Some edges of~$G_t$ +are removed in the Bor\o{u}vka steps, let us denote their number by~$b_t$. +The remaining edges fall either to~$G_\ell = H_t$, or to $G_r = G^\prime_t$, or possibly +to both. + +We can observe that the intersection $G_\ell\cap G_r$ cannot be large: The edges of~$H_t$ that +are not in the forest~$F_t$ are $F_t$-heavy, so they do not end up in~$G_r$. Therefore the +intersection can contain only the edges of~$F_t$. As there are at most $n_t/4$ such edges, +we have $m_\ell + m_r + b_t \le m_t + n_t/4$. + +On the other hand, the first Bor\o{u}vka step selects at least $n_t/2$ edges, +so $b_t \ge n_t/2$. The duplication of edges between $G_\ell$ and~$G_r$ is therefore +compensated by the loss of edges by contraction and $m_\ell + m_r \le m_t$. So the total +number of edges per level cannot decrease and it remains to apply the previous lemma. +\qed + \thmn{Average-case complexity of the KKT algorithm} +The expected time complexity of the KKT algorithm on the RAM is $\O(m)$. + +\proof + +\qed + +\FIXME{High probability result.} \rem We could also use a~slightly different formulation of the sampling lemma -- 2.39.2