2^{i+1-\ell(\overline{v})}$.

Since a non-root never becomes a root, it remains to assume that $v$ is a root
and does not increase level during round $i$. Since we assumed that the
corresponding vertex $\overline{v}$ of $v\in P_{i}$ is on $P_{i+1}$ and
active, the vertex $v^{\prime}$ that replaces $v$ on $P_{i}$ in Phase 1 of
PathConstruction$(H,P)$ (i.e., $\underline{v^{\prime}}.p=v^{\prime}$) is
exactly $v$, and is not removed in Phase 4 and remains to be active before
Phase 6. Moreover, by Step 1 of Definition 5.12,
$\Phi_{i,1}(v^{\prime})=\Phi_{i,1}(v)=\Phi_{i}(v)$.

  1. 1.

Suppose the index $j$ of $v$ on $P_{i,1}$ satisfies that (i)
$j\geq|P_{i,1}|-1$, or (ii) $j<|P_{i,1}|-1$ and $P_{i,1}(j+1)$ is passive. We
prove that $j$ is the maximum integer such that $P_{i,1}(j)$ is active. Case
(i) is easy since $j$ is the last vertex on $P_{i,1}$. It remains to prove
case (ii). Assume for contradiction that there exists $j^{\prime}>j$ such that
$P_{i,1}(j^{\prime})$ is active. Then we have $j^{\prime}>j+1$ since
$P_{i,1}(j+1)$ is passive. Since $P_{i,1}(j+1)$ is passive before Phase 3 of
round $i$ in PathConstruction$(H,P)$, in some round $i^{\prime}<i$ the
PathConstruction$(H,P)$ marks $j+1$ from active to passive, which means $j+1$
is maximum integer such that $P_{i^{\prime},1}(j+1)$ is active, and
$P_{i^{\prime},1}(j^{\prime})$ must be passive. This implies that the
$j^{\prime}$-th vertex on this path remains to be passive starting from round
$i^{\prime}$, contradicting with the fact that $P_{i,1}(j^{\prime})$ is
active. As a result, $j$ must be the maximum integer such that $P_{i,1}(j)$ is
active, and $v=P_{i,1}(j)$ is marked as passive in Phase 3 of round $i$ in
PathConstruction$(H,P)$. This contradicts with the fact that the corresponding
vertex $\overline{v}$ of $v$ is active on $P_{i+1}$ (the first paragraph of
this proof).

  2. 2.

Suppose the index $j$ of $v$ on $P_{i,1}$ satisfies that $j<|P_{i,1}|-1$ and
$P_{i,1}(j+1)$ is active.

    1. (a)

Suppose $P_{i,1}(j+2)$ is an active vertex on $P_{i,1}$. Observe that
$P_{i,1}(j+2)$ is the parent $u^{\prime}$ of a vertex in $N^{*}(N^{*}(v))$
(where $N^{*}$ is defined at the beginning of round $i$) after Step 2 within
Expand-Maxlink$(H)$ of round $i$, which must be in $\mathcal{H}(v)$ after Step
6 by Lemma 5.11. Therefore, the current graph contains edge $(v,u^{\prime})$
and $w\coloneqq P_{i,1}(j+1)$ is skipped by Phase 2a in
PathConstruction$(H,P)$, thus

$\Phi_{i,3}(v)=\Phi_{i,1}(v)+\Phi_{i,1}(w)$ (3)

by Step 2 in Definition 5.12. Next, we prove that $\ell(w)\leq\ell(v)$ at the
beginning of round $i$. Assume for contradiction that $\ell(w)>\ell(v)$. Then,
$w\in N^{*}(v)$ by Step 4 and Step 6 of Expand-Maxlink$(H)$, where $N^{*}(v)$
is defined in Step 4. Since $v$ does not increase its level during round $i$,
$v$ is not dormant in Step 8. Therefore, there is no collision in the hash
tables of $v$ in Step 6 and Step 5, and there is no collision in the hash
table of $w$ in Step 5. This means $w\in\mathcal{H}(w)=N^{*}(w)$ in Step 5,
and $w\in\mathcal{H}(v)$ in Step 6. Now we have $w\in N^{*}(v)$ before Step 7.
Consider the Maxlink$(V)$ in Step 7. Since $v$ does not increase its level and
the level of $w$ cannot decrease, $\ell(w)>\ell(v)$ still holds at this point.
In the first iteration of Maxlink$(V)$, there exists a $u^{\prime}\in
N^{*}(v).p$ such that $\ell(u^{\prime})>\ell(v)$ due to the existence of $w$
and the fact that $\ell(w.p)\geq\ell(w)$. As a result, $v$ will be a non-root
at the end of that iteration. Since a non-root never becomes a root, we have
that $v$ is a non-root after this Maxlink$(V)$, contradicting with the fact
that $v$ is a root in round $i$. Therefore, we have that $\ell(w)\leq\ell(v)$
at the beginning of round $i$. Note that vertex $\underline{w}$ (the vertex
that is replaced by $w$ in the Alter$(E)$ in Step 2 of Expand-Maxlink$(H)$,
see Phase 1 in PathConstruction$(H,P)$) is on $P_{i}$ and
$\ell(\underline{w})\leq\ell(w)\leq\ell(v)$ since $w=\underline{w}.p$.
Therefore, by the induction hypothesis, we obtain

$\Phi_{i}(\underline{w})\geq 2^{i-\ell(\underline{w})}\geq 2^{i-\ell(v)}.$ (4)

Combining, we obtain

$\displaystyle\Phi_{i+1}(v)$ $\displaystyle=\Phi_{i,3}(v)$
$\displaystyle=\Phi_{i,1}(v)+\Phi_{i,1}(w)$
$\displaystyle=\Phi_{i}(v)+\Phi_{i}(\underline{w})$ $\displaystyle\geq
2^{i-\ell(v)}+2^{i-\ell(v)}=2^{i+1-\ell(v)},$

where the first line is by the fact that $v$ is a root in round $i$ and Step 4
in Definition 5.12, the second line is by Equation (3), the third line is by
Step 1 in Definition 5.12, the fourth line is by the induction hypothesis on
$v$ and Equation (4). This finishes the inductive step for this case.

    2. (b)

Suppose $j+2\geq|P_{i,1}|$ or $P_{i,1}(j+2)$ is passive. Then, using the same
argument in case 1 of this proof, we get that $w\coloneqq P_{i,1}(j+1)$ is the
last active vertex on $P_{i,1}$, and $w$ is marked as passive in Phase 3 of
round $i$ in PathConstruction$(H,P)$. Since $v$ is active, we have that
$\Phi_{i,3}(v)=\Phi_{i,1}(v)+\Phi_{i,1}(w)$ by Step 2 in Definition 5.12.
Since $w$ is active before Phase 3 of round $i$ in PathConstruction$(H,P)$, we
can use the same argument in case 2a of this proof to obtain that
$\Phi_{i+1}(v)\geq 2^{i+1-\ell(v)}$.

As a result, the lemma holds for any active vertex $\overline{v}$ on
$P_{i+1}$, finishing the induction and giving the lemma. ∎

######  Lemma 5.15.

Given graph $H$ and integer $b\geq(\log n)^{100}$. Let $r=9\log b-1$. W.p.
$1-1/(\log n)^{9}$, for any shortest path $P$ in $H$ such that there are at
most $b^{7}$ vertices on $P$, there are at most $10\log b$ vertices on
$P_{r}$, where $P_{r}$ is defined in PathConstruction$(H,P)$.

###### Proof.

W.p. $1-1/(\log n)^{9}$, suppose Lemma 5.7 holds.

Firstly, we prove that there are at most $3$ active vertices on $P_{r}$.
Assume for contradiction that there are at least $4$ active vertices on
$P_{r}$. By an induction on round $i\in[0,r]$, Lemma 5.13, and the fact that
each vertex on $P_{0}=P$ has potential $1$ and the potentials are non-negative
(Definition 5.12), we get

$\sum_{v\text{~{}is~{}active~{}and~{}on~{}}P_{r}}\Phi_{r}(v)\leq\sum_{v\text{~{}is~{}on~{}}P_{r}}\Phi_{r}(v)\leq
b^{7}.$ (5)

Since $P_{r}$ has at least $4$ active vertices, by Lemma 5.14 we get for any
active vertex $v$ on $P_{r}$,

$\Phi_{r}(v)\geq 2^{r-\ell(v)}\geq 2^{9\log b-1-100\log\log n}=2^{8\log
b-1}>b^{7},$

where we have used $b\geq(\log n)^{100}$ and $\ell(v)\leq 100\log\log n$ for
all $v\in V(H)$. This contradicts with Equation (5).

Secondly, we show that there are at most $9\log b$ passive vertices on
$P_{r}$. This is because in each of the $9\log b$ rounds of
PathConstruction$(H,P)$, we mark at most $1$ vertex from active to passive
(Phase 3). Since all skipped vertices are removed from the path (Phase 4), we
obtain that the number of vertices on $P_{r}$ is at most $9\log b+3\leq 10\log
b$. ∎

Now we reduce the length of any shortest path with length at most $b^{7}$ to
$10\log b$. To reduce its length even further, we need an addition path
construction.

PassivePathConstruction$(H,P)$:

Let $r=9\log b-1$. For any integer $i\in[0,r]$, let path $P_{i}$ be defined as
in PathConstruction$(H,P)$.

For any integer $i\in[r,20\log b]$, given path $P_{i}$ with at least $3$
vertices at the beginning of round $i$, Expand-Maxlink$(H)$ constructs
$P_{i+1}$ by the following $3$ phases:

  1. 1.

The Alter$(E)$ in Step 2 replaces each vertex $v$ on $P_{i}$ by
$v^{\prime}\coloneqq v.p$ to get path $P_{i,1}$. For any $v^{\prime}$ on
$P_{i,1}$, let $\underline{v^{\prime}}$ be on $P_{i}$ such that
$\underline{v^{\prime}}.p=v^{\prime}$.

  2. 2.

After Step 6, let $v^{\prime}\coloneqq P_{i,1}(0)$, i.e., the first vertex on
$P_{i,1}$. If $\underline{v^{\prime}}$ is a root at the end of round $i$ and
does not increase level during round $i$ then: if the current graph contains
edge $(v^{\prime},P_{i,1}(2))$ then remove $P_{i,1}(1)$. After removing all
such vertices from $P_{i,1}$ we obtain $P_{i,2}$.

  3. 3.

The Alter$(E)$ in Step 7 replaces each vertex $v$ on $P_{i,2}$ by $v.p$ to get
path $P_{i+1}$.

For any vertex $v$ on $P_{i}$ that is replaced by $v^{\prime}$ in Phase 1, if
$v^{\prime}$ is not removed in Phase 2, then let $\overline{v}$ be the vertex
replacing $v^{\prime}$ in Phase 3, and call $\overline{v}$ the _corresponding
vertex_ of $v$ in round $i+1$.

######  Lemma 5.16.

Given graph $H$ and integer $b\geq(\log n)^{100}$. Let $R=20\log b$. W.p.
$1-1/(\log n)^{8}$, for any shortest path $P$ in $H$ such that there are at
most $b^{7}$ vertices on $P$, there are at most $2$ vertices on $P_{R}$, where
$P_{R}$ is defined in PassivePathConstruction$(H,P)$.

###### Proof.

By Lemma 5.15, at the beginning of round $r=9\log b-1$, w.p. $1-1/(\log
n)^{9}$, $P_{r}$ has length $10\log b$. We shall condition on this happening
and apply a union bound at the end of the proof.

In any round $i\geq r$, for any path $P_{i}$ with $|P_{i}|\geq 3$, consider
the first vertex $v^{\prime}=P_{i,1}(0)$ on $P_{i,1}$ (defined in
PassivePathConstruction$(H,P)$). If $\underline{v^{\prime}}$ is a non-root or
increases its level during round $i$, then by the first $4$ paragraphs in the
proof of Lemma 5.14, it must be
$\ell(\overline{v^{\prime}})\geq\ell(\underline{v^{\prime}})+1$. If this is
not the case, by Lemma 5.11, there is an edge between $v^{\prime}$ and
$P_{i,1}(2)$ in the graph after Step 6, which means the successor $P_{i,1}(1)$
of $v^{\prime}$ on $P_{i,1}$ is removed in Phase 2 of
PassivePathConstruction$(H,P)$. Therefore, the number of vertices on $P_{i+1}$
is $1$ less than $P_{i}$ if
$\ell(\overline{v^{\prime}})=\ell(\underline{v^{\prime}})$ as the level of a
corresponding vertex cannot be lower (by examining Maxlink$(V)$). By Lemma
5.7, w.p. $1-1/(\log n)^{9}$, the level of any vertex cannot be higher than
$100\log\log n$. As $P_{r}$ has at most $10\log b$ vertices, in round
$R=20\log b\geq r+10\log b+100\log\log n$, the number of vertices on any
$P_{R}$ is at most $2$. The lemma follows from a union bound. ∎

######  Lemma 5.17.

Given graph $H$ and integer $b\geq(\log n)^{100}$. For any shortest path $P$
in $H$ such that there are at most $b^{7}$ vertices on $P$, let $P_{R}$ be
defined in PassivePathConstruction$(H,P)$. Let path $P_{R+1}$ be defined by
replacing each vertex $v$ on $P_{R}$ with $v.p$ in Step 3 of Densify$(H,b)$,
and let path $P_{\text{final}}$ be defined by replacing each vertex $v$ on
$P_{R+1}$ with $v.p$ in Step 6 of Densify$(H,b)$. W.p. $1-1/(\log n)^{8}$,
there are at most $2$ vertices on $P_{\text{final}}$.

###### Proof.

By Lemma 5.16, there are at most $2$ vertices on path $P_{R}$ w.p. $1-1/(\log
n)^{8}$. The Alter$(E(H))$ in Step 3 of Densify$(H,b)$ replaces vertices by
their parents in each path, so $P_{R+1}$ has at most $2$ vertices. Since Step
5 of Densify$(H,b)$ only alters edges locally without changing
$E_{\text{close}}$, the path $P_{R+1}$ is unchanged. The following
Alter$(E_{\text{close}})$ in Step 6 replaces each vertex on $P_{R+1}$ by its
parent. As a result, $P_{\text{final}}$ has at most $2$ vertices. ∎

###  5.3 Increasing Vertex Degrees

In this section, we present the detailed algorithm Increase$(V,E,b)$ and prove
that it increase the minimum degree of the current graph to at least $b$.

####  5.3.1 Algorithmic Framework of Increase

During the execution of Increase$(V,E,b)$, the subroutine Densify$(H,b)$ calls
Expand-Maxlink$(H)$ (Step 1 of Densify$(H,b)$) for $R=20\log b$ times, where
each Expand-Maxlink$(H)$ calls Alter$(E)$ for $2$ times (Step 2 and Step 7 of
Expand-Maxlink$(H)$). Increase$(V,E,b)$ needs to use addition information of
the execution, so we modify it as follows:

  * •

In Step 1 of Densify$(H,b)$, pass the round id $i\in[0,R)$ to Expand-Maxlink
as an additional parameter.

  * •

Within Expand-Maxlink$(H,i)$, in Step 2, pass the integer $2i$ to Alter$(E)$
as an additional parameter.

  * •

Within Expand-Maxlink$(H,i)$, in Step 7, pass the integer $2i+1$ to
Alter$(E(V))$ as an additional parameter.

  * •

For each Alter$(E,j)$ called within Expand-Maxlink$(H,i)$, execute
$v.p_{j}=v.p$ for each vertex $v\in V(E)$.

  * •

In the Alter$(E(H))$ within Step 3 of Densify$(H,b)$, execute $v.p_{2R}=v.p$
for each vertex $v\in V(H)$.

  * •

In the Alter$(E_{\text{close}})$ within Step 6 of Densify$(H,b)$, execute
$v.p_{2R+1}=v.p$ for each vertex $v\in V(E_{\text{close}})$. The field $p_{j}$
for all $j\in[0,2R+1]$ is global.

All $v.p_{j}$ for all $v\in V$ and all $j\in[0,2R+1]$ can be written in a cell
indexed by $(v,j)$ in the public RAM in $O(1)$ using the processor
corresponding to $v$, and the total space (and work) used for this part is at
most $|V|\cdot O(R)\leq n/b^{10}\cdot O(\log n)$. The modified Alter$(E)$
still takes $O(|E|)$ work and $O(1)$ time, so Lemma 5.10 still holds.

######  Definition 5.18.

For any vertex $v\in V$, define $v.p^{(0)}\coloneqq v.p_{0}=v$, and for any
integer $j\in[2R+1]$, define $v.p^{(j)}\coloneqq(v.p^{(j-1)}).p_{j}$.

Increase$(V,E,b)$:

  1. 1.

Subgraph $H=(V,E^{\prime})=\textsc{Build}(V,E,b)$.

  2. 2.

$(V,E_{\text{close}})=\textsc{Densify}(H,b)$.

  3. 3.

For each vertex $v\in V$: assign a block of $b^{9}$ processors, which will be
used as an indexed hash table $\mathcal{H}^{\prime}(v)$ of size $b^{9}$.

  4. 4.

Choose a random hash function $h:[n]\to[b^{9}]$. For each vertex $v\in V$:
compute $u\coloneqq v.p^{(2R+1)}$, then write $v$ into the $h(v)$-th cell of
$\mathcal{H}^{\prime}(u)$ and update $v.p=u$.

  5. 5.

For each vertex $v\in V$: if the number of vertices in
$\mathcal{H}^{\prime}(v)$ is at least $2b$ then mark $v$ as a _head_.

  6. 6.

For each non-loop edge $(v,w)\in E_{\text{close}}$: if $v$ is a head and $w$
is a non-head then $w.p=v$.

  7. 7.

Shortcut$(V)$.

  8. 8.

For each vertex $v\in V$: sample $v$ as a _leader_ w.p. $1/2$. For each non-
loop edge $(v,w)\in E_{\text{close}}$: if $v$ is a leader and $w$ is a non-
leader then $w.p.p=v.p$.

  9. 9.

Shortcut$(V)$.

  10. 10.

Alter$(E)$.

######  Lemma 5.19.

W.p. $1-1/(\log n)^{2}$, Increase$(V,E,b)$ runs in $O(\log b)$ time and
$O(m+n)$ work on an ARBITRARY CRCW PRAM.

###### Proof.

By Lemma 5.1, Step 1 takes $O(\log b)$ time and $O(m+n)$ work w.p. $1-n^{-8}$.
By Lemma 5.10, w.p. $1-1/(\log n)^{3}$, Step 2 takes $O(\log b)$ time and
$(m+n)/(\log n)^{3}$ work. Using approximate compaction (Lemma 4.2), Step 3
takes $O(\log^{*}n)$ time and $O(|V|\cdot b^{9})$ work (to notify each indexed
processor the block it belongs to) w.p. $1-n^{-9}$.

In Step 4, each vertex in $V$ chooses and stores a random number from
$[b^{9}]$, giving function $h$, which takes $O(|V|)$ works and $O(1)$ time.
Next, the algorithm computes $u\coloneqq v.p^{(2R+1)}$ for each $v\in V$.
Since each $v.p_{j}$ for each $v\in V$ and each $j\in[0,2R+1]$ is written in a
cell indexed by $(v,j)$ in the public RAM, we can compute $v.p^{(j)}$ ($j\geq
1$) (by Definition 5.18) for each $v$ using the processor of $v$ in $O(1)$
time, given that $v.p^{(j-1)}$ is stored in the private memory of $v$.
Therefore, $u=v.p^{(2R+1)}$ is computed iteratively in $O(R)=O(\log b)$ time.
The following hashing and parent update take $O(1)$ time and $O(|V|)$ work.
Therefore, Step 4 takes $O(|V|\cdot\log b)$ works and $O(\log b)$ time.

In Step 5, we use the binary tree technique in the proof of Lemma 5.1 to count
the number of occupied items in $\mathcal{H}(v)$ for each $v$ in $O(\log b)$
time, which takes $O(\log b)$ time and $O(|V|\cdot\log b)$ work. By the proof
of Lemma 5.10, $O(|E_{\text{close}}|)\leq O(m+n)/(\log n)^{4}$ w.p. $1-1/(\log
n)^{4}$, so Step 6 takes $O(m+n)/(\log n)^{4}$ work and $O(1)$ time w.p.
$1-1/(\log n)^{4}$. Step 8 takes $O(|V|)+O(m+n)/(\log n)^{4}$ work and $O(1)$
time w.p. $1-1/(\log n)^{4}$. Step 7 and Step 9 take $O(|V|)$ work and $O(1)$
time.141414Note that the total work performed from Step 2 to Step 9 is at most
$O(m+n)/(\log n)^{3}+O(|V|\cdot b^{9})\leq(m+n)/(\log n)^{2.5}$ w.p.
$1-2/(\log n)^{3}$. In §8 we will boost the success probability to
$1-1/\text{poly}(n)$, which is obtained by running $\Theta(\log n)$ instances
of Step 2 to Step 9 in parallel (along with other techniques), so the overall
work will be $O(m+n)$.  Step 10 takes $O(m)$ work and $O(1)$ time. Summing up
and by a union bound, the lemma follows. ∎

####  5.3.2 Properties of Increase

######  Lemma 5.20.

For any vertex $v\in V$, if $v.p^{(2R+1)}\neq v$ then $v$ is a non-root from
Step 3 to Step 7 (inclusive) of Increase$(V,E,b)$.

###### Proof.

Let $j\in[0,2R+1]$ be minimum integer such that
$v.p^{(j)}=(v.p^{(j-1)}).p_{j}\neq v$ (Definition 5.18), then $v.p$ is updated
to a vertex $w\neq v$ within the call to Expand-Maxlink$(H)$ in round $\lfloor
j/2\rfloor$ of Step 1 of Densify$(H,b)$ (if $j\leq 2R-1$) or within Step 5 of
Densify$(H,b)$ (if $j=2R+1$), all within Step 2 of Increase$(V,E,b)$. Recall
that a non-root can never become a root during Expand-Maxlink$(H)$ or during
Step 5 of Densify$(H,b)$ ([LTZ20]), so $v$ is a non-root right after Step 2 of
Increase$(V,E,b)$. The parent updates in Step 4 of Increase$(V,E,b)$ cannot
make $v$ a root since $v.p^{(2R+1)}\neq v$. The Shortcut$(V)$ in Step 7 cannot
make a non-root into a root. Moreover, the parent updates in Step 6 cannot
make a non-root into a root either cause it only uses non-loop edges. As a
result, $v$ must be a non-root from Step 3 to Step 7 (inclusive) of
Increase$(V,E,b)$. ∎

######  Lemma 5.21.

W.p. $1-1/(\log n)^{8}$, for any vertex $u\in V$, if there exists vertex $v\in
V$ such that $v.p^{(2R+1)}=u$ then $u$ is a root before Step 5 of
Increase$(V,E,b)$.

###### Proof.

By Definition 5.18, $u=(v.p^{2R}).p_{2R+1}$, where $p_{2R+1}$ is the parent
filed in Step 6 of Densify$(H,b)$. By Lemma 5.9, w.p. $1-1/(\log n)^{8}$, at
the end of Densify$(H,b)$, for any vertex $v\in V$, $v$ is either a root or a
child of a root, which also holds in Step 6 of Densify$(H,b)$. Since $u$ is a
parent of another vertex at that time, $u$ must be a root. So $u$ is a root
right after Densify$(H,b)$ (Step 2 of Increase$(V,E,b)$). Note that $u$ cannot
update its parent to a vertex $w\neq u$ in Step 4 of Increase$(V,E,b)$.
Because otherwise, $u.p^{(2R+1)}=w\neq u$, making $u$ a non-root after Step 2
by Lemma 5.20, a contradiction. Therefore, $u$ remains to be a root after Step
4 of Increase$(V,E,b)$. ∎

######  Lemma 5.22.

Given input graph $G=(V,E)$ and parameter $b\geq(\log n)^{100}$, at the end of
Increase$(V,E,b)$, w.p. $1-1/(\log n)^{7}$, all vertices in $V$ must be roots
or children of roots and both ends of any edge in $E$ must be roots.

###### Proof.

After Stage $1$, all trees are flat and both ends of any edge in $E$ are roots
(Lemma 4.21). By Lemma 5.9, w.p. $1-1/(\log n)^{8}$, at the end of
Densify$(H,b)$ (Step 2 of Increase$(V,E,b)$), for any vertex $v\in V$, $v$ is
either a root or a child of a root and both ends of any edge in
$E_{\text{close}}$ are roots. We shall condition on this.

By Lemma 5.21, w.p. $1-1/(\log n)^{8}$, if $v.p^{(2R+1)}=v$ then $v$ is a root
before Step 4 of Increase$(V,E,b)$ and continues to be a root after this step.
By Lemma 5.20 and Lemma 5.21, w.p. $1-1/(\log n)^{8}$, if $v$ updates its
parent to a vertex $u\neq v$ in Step 4 of Increase$(V,E,b)$, then $v$ is a
non-root and $u$ is a root before Step 4, which means $v$ is a child of a root
and $u$ is a root before executing $v.p=u$ by the previous paragraph.
Therefore, each vertex in $V$ is either a root or a child of a root after Step
4 of Increase$(V,E,b)$.

In Step 6 of Increase$(V,E,b)$, a non-head updates its parent to be a head if
possible, which makes each vertex in $V$ a root, a child of a root, or a
grandchild of a root. The Shortcut$(V)$ in Step 7 makes all vertices in $V$
roots or children of roots.

In Step 8, $w.p.p$ is updated to $v.p$ if possible, which makes each vertex in
$V$ a root, a child of a root, or a grandchild of a root, because $w.p$ and
$v.p$ are both roots by the previous paragraph. The Shortcut$(V)$ in Step 9
makes all vertices in $V$ roots or children of roots.

Now both ends of any edges in $E$ are roots or children of roots. So, the
Alter$(E)$ in Step 10 makes all ends of all edges in $E$ roots by the previous
paragraph. ∎

######  Lemma 5.23.

W.p. $1-1/(\log n)^{7}$, for any vertex $v\in V$, if $v.p^{(2R+1)}\neq v$ then
$v$ is a non-root from Step 3 till the end of Increase$(V,E,b)$.

###### Proof.

By Lemma 5.20, if $v.p^{(2R+1)}\neq v$ then $v$ is a non-root from Step 3 to
Step 7 (inclusive) of Increase$(V,E,b)$. By the last but two paragraph in the
proof of Lemma 5.22, w.p. $1-1/(\log n)^{7}$, all vertices in $V$ are roots or
children of roots right after Step 7. So, the parent updates in Step 8
($w.p.p=v.p$) can only update the parent of a root ($w.p$), which cannot turn
a non-root into a root (which requires to update the parent of a non-root to
itself). ∎

######  Lemma 5.24.

Given input graph $G=(V,E)$ and parameter $b\geq(\log n)^{100}$, let
$H=\textsc{Build}(V,E,b)$ be computed in Step 1 of Increase$(V,E,b)$. W.p.
$1-1/(\log n)^{6}$, for any component $\mathcal{C}$ in $H$ such that
$|\mathcal{C}|$ (the number of vertices in $\mathcal{C}$) is less than
$b^{6}$, at the end of Increase$(V,E,b)$, all vertices in $\mathcal{C}$ must
be roots or children of roots and all edges in $E$ adjacent to these vertices
must be loops.

###### Proof.

W.p. $1-n^{-8}$, assuming the statement in Lemma 5.4 always holds. We get that
$V(\mathcal{C})=V(\mathcal{C}_{G})$, where $\mathcal{C}_{G}$ is the component
in $G$ induced on vertex set $V(\mathcal{C})$.

Note that for any shortest path $P$ in $\mathcal{C}$, there are at most
$b^{6}$ vertices on $P$. So by Lemma 5.16, w.p. $1-1/(\log n)^{8}$, any
shortest path in $\mathcal{C}$ at the end of Step 1 in Densify$(H,b)$ has
length at most $1$, so any vertex pair in $\mathcal{C}$ (with all edges in
$E_{\text{close}}$) has distance at most $1$. By the proof of Lemma 5.9, w.p.
$1-1/(\log n)^{8}$, both ends of any edge in $E_{\text{close}}$ are roots.
Also note that the Alter$(E(H))$ in Step 3 of Densify$(H,b)$ never increases
the diameter of any component since it only replaces edges on any shortest
path. So, the component in graph $(V(E_{\text{close}}),E_{\text{close}})$
corresponding to $\mathcal{C}$ has diameter at most $1$ and Theorem 2 is
applicable. After Step 5 of Densify$(H,b)$, w.p. $1-1/(\log n)^{9}$, for any
such component $\mathcal{C}$, the vertices in $\mathcal{C}$ must be in the
same tree (the algorithm in Theorem 2 runs independently on each component, so
the success probability is not for all vertices in a fix $\mathcal{C}$, but
for all vertices in all such $\mathcal{C}$), and these vertices must be roots
or children of roots.

Consider the parent updates in Step 4 of Increase$(V,E,b)$. By Lemma 5.20 and
Lemma 5.21, w.p. $1-1/(\log n)^{8}$, if $v$ updates its parent to a vertex
$u\neq v$ in Step 4 of Increase$(V,E,b)$, then $v$ is a non-root and $u$ is a
root before Step 4. By an induction on $j$ from $0$ to $2R+1$, one can show
that $u=v.p^{(2R+1)}$ is in the same component $\mathcal{C}$ of $v$. By the
previous paragraph, $u,v$ are in the same tree rooted at $u$ and $v.p=u$
before Step 4, so the parent update does not change the parent of $v$. On the
other hand, if $v.p^{(2R+1)}=v$ then $v$ is a root before Step 4 of
Increase$(V,E,b)$ w.p. $1-1/(\log n)^{8}$ by Lemma 5.21 and continues to be a
root. Therefore, the tree corresponding to any such component $\mathcal{C}$
does not change during Step 4.

By Lemma 5.9, w.p. $1-1/(\log n)^{8}$, the edge in $E_{\text{close}}$ are only
adjacent to roots before Step 4. By the previous paragraph, w.p. $1-1/(\log
n)^{8}$, Step 4 never turns a root into a non-root. So, w.p. $1-1/(\log
n)^{7}$, the edge in $E_{\text{close}}$ are only adjacent to roots before Step
6. Since any vertex pair $v,w$ in $\mathcal{C}$ are in the same tree, if there
is an edge in $E_{\text{close}}$ between $v,w$, the edge must be a loop. So
the parent updates in Step 6 of Increase$(V,E,b)$ do not change the tree
corresponding to any such component $\mathcal{C}$, because only non-loop edges
are used.

The Shortcut$(v)$ in Step 7 does not change the tree since all vertices in
$\mathcal{C}$ must be roots or children of roots. Step 8 does not change the
tree corresponding to any $\mathcal{C}$ because all edges between vertices in
$\mathcal{C}$ remain to be loops. The Shortcut$(v)$ in Step 9 does not change
these trees either. We shall prove the lemma by contradiction based on Lemma
5.22: w.p. $1-1/(\log n)^{7}$, both ends of any edge in $E$ are roots at the
end of Increase$(V,E,b)$.

Assume for contradiction that there exists a component $\mathcal{C}$ in $H$
such that there exists an edge $(v,w)\in E$ (where the edge set $E$ here is
already altered by the Alter$(E)$ in Step 10 of Increase$(V,E,b)$) such that
$v\neq w$ at the end of Increase$(V,E,b)$. Then by the previous paragraph we
know that both $v,w$ are roots. Since $(v,w)\in E$, we have that $v,w$ are in
the same component $\mathcal{C}_{G}$.151515We omit the proof that during the
algorithm, $v,v.p$ are in the same component of $G$ and so do $v,w$ if edge
$(v,w)$ presents in the current graph, which is by a standard induction by
steps, e.g., see [LTZ20] or [LT22] for a proof. By the second sentence of this
proof, $V(\mathcal{C})=V(\mathcal{C}_{G})$. So $v,w$ must be in the same
component $\mathcal{C}$. By the previous paragraph, $v,w$ must be within the
same tree in the labeled digraph, contradicting with the fact that $v\neq w$
and they are both roots. As a result, $v=w$ and thus all edges adjacent to
vertices in $\mathcal{C}$ must be loops. The lemma follows from a union bound.
∎

Lemma 5.24 means that such small component (with size less than $b^{6}$) in
$H$ can be _ignored_ in the rest of the entire algorithm as the connectivity
computation on them is already _finished_. In our presentation, we do not
detect and delete all loops from the current graph, because although the loop-
deletion does not affect the components that are already finished, it might
decrease the spectral gap of other unfinished components, hurting the running
time of our algorithm.

Our edge sampling in Stage $3$ (§6) will operate on all edge including loops.
Since each small component is contracted to $1$ vertex,161616Strictly
speaking, such components are not fully contracted due to the existence of
non-roots at the end of Stage $1$. The contraction will be done at the end of
the algorithm, see footnote 12. the execution of our algorithm after Stage $2$
does not affect such components, and it is equivalent to ignore all such
components in the graph.

######  Lemma 5.25.

Given input graph $G=(V,E)$ and parameter $b\geq(\log n)^{100}$, w.p.
$1-1/(\log n)^{5}$, for any root $v\in V$ at the end of Increase$(V,E,b)$, the
degree of $v$ in the current graph is at least $b$.

###### Proof.

By Lemma 5.24 and the discussion following it, w.p. $1-1/(\log n)^{6}$, any
vertex in a component of $H$ with size less than $b^{6}$ is ignored in the
rest of the algorithm since the computation of its component is finished.
Therefore, we assume that any vertex $v\in V$ is in a component of $H$ with
size at least $b^{6}$.

Suppose any shortest path in $\mathcal{C}_{H}(v)$ (Definition 5.3) has less
than $b^{6}$ vertices on it. Then, using the same argument in the proof of
Lemma 5.24, w.p. $1-1/(\log n)^{6}$, all shortest paths in
$\mathcal{C}_{H}(v)$ have length at most $1$ at the end of Step 3 of
Densify$(H,b)$, and the following Step 5 makes all vertices in
$\mathcal{C}_{H}(v)$ the root of a tree or the children of the root of this
same tree. The parent updates after Step 2 of Increase$(V,E,b)$ do not change
the tree corresponding to $\mathcal{C}_{H}(v)$ by the same argument in the
proof of Lemma 5.24. Let $u$ be the root of the tree containing $v$. By
$|\mathcal{C}_{H}(v)|\geq b^{6}$, we get that the number of vertices $v\in V$
with $v.p=u$ is at least $b^{6}$ ($u.p=u$ also contributes $1$). Since each
vertex in $\mathcal{C}_{H}(v)$ has at least one adjacent edge (otherwise it is
a singleton and cannot be presented in a component of size at least $b^{6}$),
it must have at least one adjacent edge in $G$, so the number of edges in $G$
adjacent to vertices in $\mathcal{C}_{H}(v)$ is at least $b^{6}/2\geq b$. By
the proof of Lemma 5.22, all these edges are altered to be adjacent to root
$u$ at the end of Increase$(V,E,b)$, so the degree of $u$ in the current graph
is at least $b$.

Suppose there exists a shortest path in $\mathcal{C}_{H}(v)$ with at least
$b^{6}$ vertices on it. Consider a shortest path $P$ in $\mathcal{C}_{H}(v)$
starting at $v$ such that $|P|\geq b^{6}/2$. Such a path $P$ must exist,
otherwise any vertex $u\in\mathcal{C}_{H}(v)$ can travel to $v$ then travel to
any vertex $w\in\mathcal{C}_{H}(v)$ (by connectivity), giving a path of less
than $b^{6}$ vertices, a contradiction. Recall that for each integer
$i\in[0,|P|-1]$, $P(i)$ is the $i$-th vertex on $P$. For each integer
$i\in[3,|P|-1]$, let path $P^{(i)}$ be the subpath from $P(0)$ to $P(i)$
(inclusively) using edges on $P$, and let $P^{(i)}_{\text{final}}$ be defined
in Lemma 5.17 given $P^{(i)}$ as the initial shortest path in $H$. By Lemma
5.17, $|P^{(i)}_{\text{final}}|\leq 2$ w.p. $1-1/(\log n)^{8}$ for any
shortest $P$ and any integer $i\in[3,|P|-1]$.

Consider the (multi-)set of paths
$\mathcal{P}\coloneqq\\{P^{(i)}_{\text{final}}\mid i\in[3,|P|-1]\\}$. There
are two cases.

  1. 1.

Suppose the set $\mathcal{P}$ contains at most $b^{2}$ distinct elements
(paths). Note that each path in $\mathcal{P}$ has form
$(P(0).p^{(2R+1)},P(i).p^{(2R+1)})$ for some $i\in[3,|P|-1]$ by Definition
5.18 and the fact that all such paths have length at most $1$. So, the vertex
set

$V_{P}\coloneqq\\{P(0).p^{(2R+1)}\\}\cup\\{P(i).p^{(2R+1)})\mid
i\in[3,|P|-1]\\}$

contains at most $b^{2}+1$ distinct elements. Observe that all vertices
originally on path $P$ are distinct since $P$ is a shortest path. Therefore,
there exists a vertex $v^{*}\in V_{P}$ such that at least

$\frac{|P|-3}{b^{2}+1}\geq\frac{b^{6}/2-3}{b^{2}+1}\geq b^{2}$

different $v^{\prime}$ on $P$ satisfies $v^{\prime}.p^{(2R+1)}=v^{*}$. In Step
4 of Increase$(V,E,b)$, each such vertex $v^{\prime}$ writes itself to the
$h(v^{\prime})$-th cell of $\mathcal{H}^{\prime}(v^{*})$. The probability that
at most $2b$ vertices are in $\mathcal{H}^{\prime}(v^{*})$ is at most

$\binom{b^{9}}{2b}\cdot\left(\frac{2b}{b^{9}}\right)^{b^{2}}\leq b^{18b}\cdot
b^{-7b^{2}}\leq b^{-b}\leq n^{-9}$

by $b\geq(\log n)^{100}$. Therefore, by a union bound over all vertices, w.p.
$1-n^{-8}$, any of such vertex $v^{*}$ is marked as a head in Step 5 of
Increase$(V,E,b)$.

If $v\notin V_{P}$ then there exists a vertex $u\neq v$ such that $u\in V_{P}$
and $v.p^{(2R+1)}=u$, which means $v$ is a non-root w.p. $1-1/(\log n)^{7}$ by
Lemma 5.23, and the lemma holds for this case. Now suppose $v\in V_{P}$, we
have that $v=P(0).p^{(2R+1)}$ by the fact that $v$ is the first vertex on $P$.
There are two cases.

    1. (a)

If $v=v^{*}$ then the number of vertices $w\in\mathcal{C}_{H}(v)$ with
$w.p^{(2R+1)}=v$ is at least $b^{2}$, and all such $w$’s update their parents
to $v$ in Step 4 of Increase$(V,E,b)$. Note that for any vertex $w$,
$w.p^{(2R+1)}$ is unique, so the number of children of $v$ after (parallel
execution of) Step 4 is at least $b^{2}$. The parent updates in Step 6 can
only increase the number of children of $v$ or make $v$ a non-root, because
w.p. $1-1/(\log n)^{7}$, the edge in $E_{\text{close}}$ are only adjacent to
roots before Step 6 by the fourth paragraph in the proof of Lemma 5.24.
Suppose $v$ is a root after Step 6. Step 7 can only increase the number of
children of $v$ since $v$ is a root. Step 8 can only increase the number of
children of $v$ or make $v$ a non-root, because Step 7 makes all vertex in $V$
roots or children of roots such that Step 8 can only update the parents of
roots. By the proof of Lemma 5.23, w.p. $1-1/(\log n)^{7}$, a non-root can
never become a root, thus if $v$ is a root at the end of Increase$(V,E,b)$,
then the degree of $v$ is at least $b^{2}/2\geq b$ by the same argument in the
second paragraph of this proof.

    2. (b)

If $v\neq v^{*}$ then the path from $v$ to $v^{*}$ is an element in
$\mathcal{P}$ with path length $1$. Therefore, $(v,v^{*})$ is an edge in
$E_{\text{close}}$ after Step 2 of Increase$(V,E,b)$ and remains to be in
$E_{\text{close}}$ right before Step 6. If $v$ is a head then the number of
distinct vertices in $\mathcal{H}^{\prime}(v)$ is at least $2b$ by Step 5,
giving at least $2b$ vertices whose parent is $v$ (a root) by Step 4, which
continues to hold till Step 7 because Step 6 cannot make $v$ a non-root nor
remove any child from $v$ (since any child of $v$ has no adjacent edge). Step
8 can only increase the number of children of $v$ or make $v$ a non-root by
the same argument in the previous case. As a result, if $v$ is a root at the
end of Increase$(V,E,b)$ then the degree of $v$ is at least $b$ by the same
argument in the second paragraph of this proof. Else if $v$ is a non-head,
since $v^{*}$ is marked as a head w.p. $1-n^{-8}$, $v$ becomes a non-root in
Step 6 dues to edge $(v,v^{*})\in E_{\text{close}}$ and remains so till the
end of the algorithm, and the lemma holds for this case.

  2. 2.

Suppose the set $\mathcal{P}$ contains at least $b^{2}$ distinct elements
(paths). By definition, all paths (edges) in $\mathcal{P}$ starts with
$P(0).p^{(2R+1)}$. Excluding the possible loop
$(P(0).p^{(2R+1)},P(0).p^{(2R+1)})\in\mathcal{P}$, there are at least
$b^{2}-1$ paths with length $1$ in $\mathcal{P}$, which correspond to at least
$b^{2}-1$ different non-loop edges in $E_{\text{close}}$ at the end of Step 2
of Increase$(V,E,b)$. If $v$ is a non-root before Step 8, then w.p. $1-1/(\log
n)^{7}$, $v$ is a non-root at the end of Increase$(V,E,b)$ by the proof of
Lemma 5.23, and the lemma holds for this case. Suppose $v$ is a root before
Step 8, which gives $v=P(0).p^{(2R+1)}$ by the argument in the previous case.
There are two cases.

    1. (a)

Suppose $v$ is sampled as a non-leader in Step 8. The number of different non-
loops edges $(v,w)$ adjacent to $v$ in $E_{\text{close}}$ is at least
$b^{2}-1$. So, by a Chernoff bound and $b\geq(\log n)^{100}$, w.p. $1-n^{-8}$,
there exists a leader $w$. Since $v.p=p$, Step 8 updates the parent of the
non-leader $v$ to $w.p$. If $v\neq w.p$ then $v$ is a non-root at the end of
Increase$(V,E,b)$ and the lemma holds for this case. Else if $v=w.p$ before
Step 8, then since $w$ has an adjacent edge $(v,w)\in E_{\text{close}}$, $w$
must be a root before Step 6 w.p. $1-1/(\log n)^{7}$ (the fourth paragraph in
the proof of Lemma 5.24). Since $w\neq v$ and $w$ updates its parent to $v$ in
Step 6, we obtain that $v$ is a head, and the lemma holds in this case by the
proof in case 1b.

    2. (b)

Suppose $v$ is sampled as a leader in Step 8. The number of different non-
loops edges $(v,w)$ adjacent to $v$ in $E_{\text{close}}$ is at least
$b^{2}-1$. By a Chernoff bound and $b\geq(\log n)^{100}$, w.p. $1-n^{-8}$,
there exist $2b$ non-leaders $w$ such that $(v,w)\in E_{\text{close}}$ and
$w\neq v$. So, after Step 8, the number of different vertices $w$ with
$w.p.p=v.p=v$ is at least $2b$. After the Shortcut$(V)$ in Step 9, the number
of children of $v$ is at least $2b$ since $v$ is a root. Since each vertex in
$\mathcal{C}_{H}(v)$ has at least one adjacent edge (otherwise it is a
singleton and cannot be presented in a component of size at least $b^{6}$), it
must have at least one adjacent edge in $G$, so the number of edges in $G$
adjacent to these (at least) $2b$ different vertices (whose parent is $v$) is
at least $2b/2=b$. By the proof of Lemma 5.22, all these edges are altered to
be adjacent to root $v$ at the end of Increase$(V,E,b)$, so the degree of $v$
in the current graph is at least $b$.

By a union bound over all the bad events, the lemma follows. ∎

##  6 Stage 3: Connectivity on the Sampled Graph

After Stage $2$, by Lemma 5.25, w.p. $1-1/(\log n)^{6}$, we can assume
$\deg(G)\geq b$, where $G$ is the current graph at the end of
Increase$(V,E,b)$ and $b=(\log n)^{100}$.

We also assume that the minimum spectral gap $\lambda$ over all connected
components (henceforth also called the component-wise spectral gap) of the
original input graph satisfies

$\lambda\geq b^{-0.1}=(\log n)^{-10}.$

This assumption will be removed in §7 to give a connected component algorithm
for any graphs with any spectral gap and the algorithm does not need any prior
knowledge on the spectral gap.

The following lemma states that Stages 1 and 2 of the algorithm does not
decrease the component-wise spectral gap of the original graph.

######  Lemma 6.1.

Let $\lambda$ be the component-wise spectral gap of the original input graph.
The component-wise spectral gap $\lambda_{G}$ of the current graph $G$ at the
end of Stage $2$ satisfies that $\lambda_{G}\geq\lambda$.

###### Proof.

By Lemma 4.21, the algorithm in Stage $1$ (Reduce$(V,E,k)$) is a contraction
algorithm since all vertices $v$ are contracted to vertex $v.p$, so the
component-wise spectral gap of the graph at the end of Stage $1$ is at least
$\lambda$ since a contraction can only increase the spectral gap of any graph
([CG97] Chapter 1.4, Lemma 1.15).

The algorithm in Stage $2$ (Increase$(V,E,b)$) might create trees of height
$2$ dues to the existence of non-roots created in Stage $1$. By Lemma 5.22,
w.p. $1-1/(\log n)^{8}$, all edges in the current graph are only adjacent on
roots and the algorithm never deletes edges nor add edges (but only replace
them by replacing ends with their parents), so all vertices in a tree rooted
at $v$ are contracted to $v$, giving a contraction algorithm Increase$(V,E,b)$
for Stage $2$ w.p. $1-1/(\log n)^{8}$. As a result, the component-wise
spectral gap $\lambda_{G}$ of the current graph $G$ at the end of Stage $2$ is
at least $\lambda$ w.p. $1-1/(\log n)^{8}$ (this probability will be boosted
to high-probability in §8 ).171717As an alternative proof, one can apply
Cheeger’s inequality for non-simple graph ([Chu96]) and note that a
contraction can only increase the graph conductance since it removes candidate
cuts. This would give $\lambda_{G}\geq\lambda^{3}$ that suffices for our use.
∎

The algorithm below, called SampleSolve$(G=(V,E))$, computes the connected
components of a graph given a promised component-wise spectral gap.
Essentially, the algorithm runs Stages 1 and 2, at the end of which all
vertices have sufficiently large degree (except for the ones in tiny
components which we can ignore). At this moment, we downsample the number of
edges by a $1/\operatorname{poly}\log n$ factor, and then run [LTZ20]. In this
section, we prove that the algorithm achieves $O(\log\log n)$ time and linear
expected work with good probability. We remove the known spectral gap
assumption in § 7 and boost the guarantees to high probability in §8.

SampleSolve$(G=(V,E))$:

  1. 1.

If $|V|\leq n^{0.1}$ then removes parallel edges and loops from $E$ and
compute the connected components of graph $(V,E)$ by Theorem 2 and goto Step
4.

  2. 2.

Sample each edge in $E$ w.p. $1/(\log n)^{7}$ to obtain graph $G^{\prime}$.

  3. 3.

Compute the connected components of graph $G^{\prime}$ by Theorem 2.

  4. 4.

For each vertex $v$ in the original input graph: $v.p=v.p.p.p$.

######  Theorem 3.

There is an ARBITRARY CRCW PRAM algorithm that computes the connected
components of any given graph with component-wise spectral gap
$\lambda\geq(\log n)^{-10}$ in $O(\log\log n)$ time and $O(m)+\overline{O}(n)$
work w.p. $1-1/(\log n)$.

###### Proof.

We run algorithm SampleSolve$(G=(V,E))$ where $G$ is the current graph at the
end of Stage $2$.

By Lemma 4.21, all vertices at the end of Stage $1$ are roots or children of
roots, as required by Stage $2$. By Lemma 5.22, w.p. $1-1/(\log n)^{8}$, all
vertices in $V$ must be roots or children of roots, where $V$ is the set of
roots at the end of Stage $1$. Therefore, all vertices in the input graph are
in trees of height at most $2$. Within SampleSolve$(G)$ in Stage $3$, either
in its Step 1 or Step 3, the contraction algorithm in Theorem 2 makes each
root at the beginning of Stage $3$ a root or a child of root at the end of
Step 3, all vertices in the input graph are in trees of height at most $3$.
Step 4 of SampleSolve$(G)$ makes all trees flat at the end of Stage $3$.

By Lemma 4.25, Stage $1$ runs in $O(\log\log n)$ time and
$O(m)+\overline{O}(n)$ work w.p. $1-n^{-2}$, and $|V|\leq n/b^{10}$ as
required by Stage $2$. By Lemma 5.19, w.p. $1-1/(\log n)^{2}$, Stage $2$ takes
$O(\log b)=O(\log\log n)$ time and $O(m+n)$ work. So, the first two stages
take $O(\log\log n)$ time and $O(m)+\overline{O}(n)$ work w.p. $1-2/(\log
n)^{2}$.

If $|V|\leq n^{0.1}$ at the beginning of Stage $3$ (which can be detected in
$O(\log^{*}n)$ time and $O(n)$ work w.p. $1-n^{-9}$ by approximate
compaction), then in Step 1 of SampleSolve$(G)$ we remove all loops from $E$
in $O(1)$ time and $O(m)$ work; next, we remove all parallel edges from $E$ by
PRAM perfect hashing on all edges of $E$ in $O(m)$ work and $O(\log^{*}n)$
time w.p. $1-n^{-9}$ ([GMV91]). This results in a simple graph with at most
$|V|^{2}\leq n^{0.2}$ edges, so the work of running the algorithm in Theorem 2
on this graph is at most $O(n^{0.2}\cdot\log n)\leq O(n)$ w.p. $1-1/(\log
n)^{9}$, giving $O(m+n)$ total work for Step 1 w.p. $1-1/(\log n)^{8}$. By
Lemma 6.1 and the assumption on $\lambda$, we have $\lambda_{G}\geq(\log
n)^{-10}$ at the beginning of Step 1. Let $d$ be the maximum diameter of any
component in $G$, then $d\leq O(\log n/\lambda)\leq(\log n)^{12}$. Removing
loops and parallel edges from $G$ does not affect the diameter of $G$, nor its
components. Therefore, the algorithm in Theorem 2 computes all connected
components of $G$ in $O(\log d+\log\log n)\leq O(\log\log n)$ time w.p.
$1-1/(\log n)^{9}$. Step 4 takes $O(n)$ work and $O(1)$ time. As a result, if
$|V|\leq n^{0.1}$ at the beginning of Stage $3$, then Stage $3$ takes $O(m+n)$
work and $O(\log\log n)$ time w.p. $1-1/(\log n)^{7}$.

Suppose $|V|>n^{0.1}$ at the beginning of Stage $3$. By Lemma 5.25, w.p.
$1-1/(\log n)^{5}$, we have $\deg(G)\geq b$ at the beginning of Step 2 of
SampleSolve$(G)$. By $|V|>n^{0.1}$ and Corollary C.3 , w.p. $1-n^{-0.1c}\geq
1-n^{-9}$ (choosing $c$ large enough), the spectral gap $\lambda$ of any
component $\mathcal{C}$ in $G$ and the spectral gap $\lambda^{\prime}$ of this
component $\mathcal{C}^{\prime}$ in $G^{\prime}$ after sampling satisfy

$\left|\lambda-\lambda^{\prime}\right|\leq C^{\prime}\cdot\sqrt{\frac{\ln
n}{(1/(\log n)^{7})\cdot\deg(G)}}\leq b^{-0.4}$

by $1/(\log n)^{7}\cdot\deg(G)\geq b/(\log n)^{7}\geq C\ln n$ and $b\geq(\log
n)^{100}$. So $\lambda^{\prime}\geq\lambda-b^{-0.4}\geq b^{-0.2}$ by
$\lambda\geq b^{-0.1}$ from the previous paragraph. Since
$\lambda^{\prime}>0$, the component $\mathcal{C}$ stays connected after
sampling, and thus $V(\mathcal{C})=V(\mathcal{C^{\prime}})$. Therefore, it
remains to prove that each such component $\mathcal{C}^{\prime}$ contracts to
$1$ vertex in Step 3 of SampleSolve$(G)$. Let $d^{\prime}$ be the diameter of
component $\mathcal{C^{\prime}}$. We have $d^{\prime}\leq O(\log
n/\lambda^{\prime})\leq O(b^{0.2}\log n)\leq(\log n)^{30}$ by $b=(\log
n)^{100}$. Therefore, the algorithm in Theorem 2 computes all connected
components of $G^{\prime}$ in $O(\log d^{\prime}+\log\log n)\leq O(\log\log
n)$ time w.p. $1-1/(\log n)^{9}$, giving all connected components of $G$. Now
we compute the work. If $|E|\leq n^{0.2}$ then Step 3 takes $O(n)$ work w.p.
$1-1/(\log n)^{8}$ as discussed in the previous paragraph. Now suppose
$|E|\geq n^{0.2}$. By a Chernoff bound over all edges, after Step 2 of
SampleSolve$(G)$, the number of edges in $G^{\prime}$ is at most $m/(\log
n)^{6}$ w.p. $1-n^{-9}$. So the algorithm in Theorem 2 takes $O(m+n)/(\log n)$
work in Step 3 w.p. $1-1/(\log n)^{9}$. As a result, Stage $3$ takes $O(m+n)$
work and $O(\log\log n)$ time w.p. $1-1/(\log n)^{4}$ for this case.

Summing up all works and running time over all $3$ stages and by a union
bound, the theorem follows. ∎

The total work of the algorithm will be improved to $O(m+n)$, and the success
probability will be boosted to $1-n^{-c}$ for arbitrary constant $c>0$ in §8.
The assumption on the component-wise spectral gap of the input graph will be
removed in §7, resulting in a connected components algorithm for any given
graph with any component-wise spectral gap $\lambda$ over all components that
runs in $O(\log(1/\lambda)+\log\log n)$ time and $O(m)+\overline{O}(n)$ work
w.p. $1-n^{-c}$ for arbitrary constant $c>0$.

##  7 The Overall Algorithm: Removing the Assumption on Spectral Gap

In this section, we remove the assumption that the component-wise spectral gap
$\lambda$ over all components of the input graph is at least $(\log n)^{-10}$,
giving an algorithm that runs in $O(\log(1/\lambda)+\log\log n)$ time.

###  7.1 Algorithmic Framework

The overall algorithm starts with running Reduce$(V,E,k)$ with
$k=10^{6}\log\log n$ on the input graph $(V,E)$ for preprocessing (same as
Stage $1$) such that the number of vertices in the current graph is at most
$n/b^{10}$ w.h.p., where $b=(\log n)^{100}$ initially. Next, we interweave the
algorithms Filter from Stage $1$, Increase from Stage $2$, and SampleSolve
from Stage $3$, such that in each _phase_ $i$ (defined below in the
pseudocode):

  * •

If the component-wise spectral gap $\lambda$ (unknown to the algorithm) is at
least $b^{-0.1}$, then Increase makes $\deg(G)\geq b$ in $O(\log b)$ time, and
SampleSolve (with other subroutines) solves the problem in $O(\log b)$ time.
Otherwise, $\lambda<b^{-0.1}$.

  * •

Revert the state of algorithm Filter to the previous phase. Update
$b\leftarrow b^{1.1}$. Run $O(1.1^{i}\log\log n)$ rounds of Filter (and
algorithm Matching with other subroutines) to reduce the number of vertices in
the current graph to $n/b^{10}$.

Connectivity$(G=(V,E))$:

  1. 1.

Initialize the labeled digraph: for each vertex $v\in V$: $v.p=v$.

  2. 2.

Run Reduce$(V,E,k=10^{6}\log\log n)$ to obtain the current graph $G^{\prime}$.

  3. 3.

Sample each edge of $G^{\prime}$ w.p. $1/(\log n)^{7}$ independently to get
random subgraph $H_{1}$. Sample each edge of $G^{\prime}$ w.p. $1/(\log
n)^{7}$ independently to get random subgraph $H_{2}$. The sampled graphs are
copied out so that $G^{\prime}$ is unchanged.

  4. 4.

Copy the edges of $G^{\prime}$ to create an edge set $E_{\text{filter}}$.

  5. 5.

For _phase_ $i$ from $0$ to $10\log\log n$:
$E_{\text{filter}}=\textsc{Interweave}(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$,
if $E_{\text{filter}}=\emptyset$ then goto Step 6.

  6. 6.

Shortcut$(V)$.

In the above, $H_{1}$ is the edges sampled to create the sparsified graph
before we run Theorem 2 [LTZ20], and $H_{2}$ is an independently sampled set
of edges to help us create the skeleton graph more work-efficiently in Stage
$2$ of the algorithm. In particular, now that we need to run the algorithm for
each assumption of the component-wise $\lambda$, we can no longer afford to
spend $O(m)$ work for each assumption – for this reason, we sparsify the graph
before creating the skeleton graphs such that we can create the skeleton graph
in $O(m/\log^{2}n)$ work. See § 7.3 for more details.

We now describe the Interweave algorithm which essentially searches for the
right spectral gap by squaring the guess in every iteration.

Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$:

  1. 1.

Set $b=(\log n)^{100\cdot 1.1^{i}}$.

  2. 2.

$\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$ — see § 7.3 for more details.

  3. 3.

Run $20\log b$ rounds of $H_{1}=\textsc{Expand-Maxlink}(H_{1})$ then run
$10^{4}\log\log n$ rounds of the algorithm in Theorem 2 on $H_{1}$.
Alter$(H_{1})$.

  4. 4.

If all edges in $E(H_{1})$ are loops then call Remain$(G^{\prime},H_{1})$ and
return $\emptyset$.

  5. 5.

Revert the labeled digraph and graph $H_{1}$ to their states in Step 1.

  6. 6.

Repeat for $10^{6}\cdot 1.1^{i}\log\log n$ rounds:
Matching$(E_{\text{filter}})$, Alter$(E_{\text{filter}})$, delete each edge
from $E_{\text{filter}}$ w.p. $10^{-4}$.

  7. 7.

Repeat for $i+2\log\log n$ times: Shortcut$(V(G^{\prime}))$.

  8. 8.

Edge set $E^{\prime}=\\{(v,w)\in E(G^{\prime})\mid v.p\in
V(G^{\prime})\backslash V(E_{\text{filter}})\\}$. Alter$(E^{\prime})$.

  9. 9.

Repeat for $10^{6}\cdot 1.1^{i}\log\log n$ rounds: Matching$(E^{\prime})$,
Shortcut$(V(G^{\prime}))$, Alter$(E^{\prime})$.

  10. 10.

Reverse$(V(E_{\text{filter}}),E(H_{2}))$.

  11. 11.

Return $E_{\text{filter}}$.

Remain$(G^{\prime},H_{1})$:

  1. 1.

Alter$(E(G^{\prime}))$.

  2. 2.

Edge set $E_{\text{remain}}=E(G^{\prime})\backslash E(H_{1})$.

  3. 3.

Remove loops and parallel edges from $E_{\text{remain}}$.

  4. 4.

Compute the connected components of graph
$(V(E_{\text{remain}}),E_{\text{remain}})$ by Theorem 2.

At the beginning of each phase $i$, the algorithm assumes that $\lambda\geq
b^{-0.1}$ where $b=(\log n)^{100\cdot 1.1^{i}}$. If the assumption is correct,
then the connected components of the input graph is correctly computed in
$O(\log b)=O(\log(1/\lambda))$ time. Otherwise, $b$ is updated to $b^{1.1}$
and the number of vertices is reduces to $n/b^{10}$ for the next phase under
the assumption that $\lambda\geq b^{-0.1}$.

The algorithm eventually succeeds in a phase under the correct assumption.
Since the running time $O(\log b)$ in each phase is geometrically increasing,
the total running time is asymptotically the running time of the phase under
the correct assumption, which is $O(\log(1/\lambda))$ as desired.

An additional technique issue is to reduce the work in each phase from
$O(m+n)$ to $O(m+n)/\log n$ such that the total work over all $O(\log\log n)$
phases are $O(m+n)$, which will be presented later in this section: In §7.3 we
reduce the work of Increase$(G^{\prime},H_{1},H_{2},b)$ by modifying the
algorithm Increase$(V,E,b)$ in §5.3; in §7.4 we reduce the work of computing
the edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$.

###  7.2 Basic Properties of Connectivity

We give some basic properties of the algorithm Connectivity, which will be
used later.

######  Lemma 7.1.

During the execution of Connectivity$(G)$, at the beginning of each phase in
Step 5, all vertices in $V(G^{\prime})$ are roots or children of roots.

###### Proof.

By Lemma 4.21, after Step 2, all trees are flat and edges in $E(G^{\prime})$
are only adjacent to roots, which also holds for edge set $E_{\text{filter}}$
(Step 4). By an induction on phase $i$ from $0$ to $10\log\log n$, it suffices
to prove that for any phase, if at the beginning of the phase all vertices in
$V(G^{\prime})$ are roots or children of roots, then this still holds at the
beginning of the next phase. We do not consider the case of
$E_{\text{filter}}=\emptyset$ in Step 5 because there will be no next phase.
Consider the Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in this
phase. Step 2 to Step 5 can be ignored because
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ does not return
$\emptyset$ and thus the labeled digraph (as well as $H_{1}$) are the same as
in Step 1 dues to Step 5. By an induction on rounds in Step 6 and Lemma 4.5,
the edges in $E_{\text{filter}}$ are only adjacent to roots at the beginning
of each round of Step 6, and any vertex $v\in V(G^{\prime})$ has distance at
most $10^{6}\cdot 1.1^{i}\log\log n$ from the root of the tree containing $v$
because such distance increases by at most $1$ in each round. Each application
of Shortcut$(V(G^{\prime}))$ in Step 7 reduces such distance by a factor of at
least $3/2$ if the distance is at least $2$. Therefore, after $i+2\log\log
n\geq\log_{3/2}(10^{6}\cdot 1.1^{i}\log\log n)$ applications of
Shortcut$(V(G^{\prime}))$, all vertices in $V(G^{\prime})$ are roots or
children of roots after Step 7. The Alter$(E^{\prime})$ in Step 8 moves all
edges only adjacent to roots since $E^{\prime}\subseteq E(G^{\prime})$.
Finally, by an induction on rounds in Step 9 and Lemma 4.5, the edges in
$E^{\prime}$ are only adjacent to roots at the beginning of each round of Step
9 and all vertices in $V(G^{\prime})$ are roots or children of roots at the
beginning of each round of Step 9 dues to the Shortcut$(V(G^{\prime}))$ in
each round. This finishes the total induction and gives the lemma. ∎

######  Definition 7.2.

Let graph $G^{\prime}$ be computed in Step 2 of Connectivity$(G)$. Given a
time $t$ in the execution of Connectivity$(G)$, for each vertex $v\in
V(G^{\prime})$, define
$\overline{\deg}_{G^{\prime}}(v)\coloneqq\left|\left\\{(u,w)\in
E(G^{\prime})\mid u.p=v\right\\}\right|$, and define graph
$\overline{G^{\prime}}$ as the graph $G^{\prime}$ after executing
Alter$(E(G^{\prime}))$, where the parent points are given in the labeled
digraph at time $t$.

In our later analysis, we will frequently use $\overline{G^{\prime}}$, because
we cannot afford executing Alter$(E(G^{\prime}))$ as it would take $\Theta(m)$
work. Recall from §4 that an active root is a vertex that is a root with
adjacent edges to another root in the current graph. Our current graph would
be $G^{\prime}$ if we executed Alter$(E(G^{\prime}))$ at the end of each
phase, which is unaffordable, but we can still define the _current graph_ to
be $\overline{G^{\prime}}$ to be consistent.181818We will show how to detect
active roots in desired work later in the proof of Lemma 7.8. As a result, a
root $u$ that is non-active must be in a tree containing all the vertices in
the component of $u$ in $G^{\prime}$, and thus $u$ and all its descendants can
be ignored in the rest of the execution of the algorithm because the
computation of this component is finished.

######  Lemma 7.3.

During the execution of Connectivity$(G)$, w.p. $1-n^{-7}$, for any integer
$i\in[0,10\log\log n)$, at the beginning of each phase $i$ in Step 5, the
number of active roots in $V(G^{\prime})$ is at most $n/b^{10}$, where
$b=(\log n)^{100\cdot 1.1^{i}}$.

###### Proof.

The proof is by an induction on phase $i\in[0,10\log\log n)$. At the beginning
of phase $0$, $|V(G^{\prime})|\leq n/(\log n)^{1000}$ guaranteed by Stage $1$.
Suppose the number of active roots is at most $n/b^{10}$ at the beginning of
phase $i$ where $b=(\log n)^{100\cdot 1.1^{i}}$, we will show that the number
of active roots decreases to $n/b^{11}$ at the end of phase $i$, giving the
lemma.

Consider the Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in phase
$i$. We shall ignore Step 2 to Step 4 in the analysis, because the labeled
digraph is reverted to Step 1 (by Step 4) if
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ does not return in
Step 3.

By the proof of Lemma 4.14, each round in Step 6 decreases the number of roots
in $V(E_{\text{filter}})$ by a factor of $0.001$ w.p. $1-n^{-9}$. There are at
most $(\log n)^{3}$ rounds in Step 6 by $i\leq 10\log\log n$. So by a union
bound, w.p. $1-n^{-8}$, at the end of Step 6 we have the number of roots in
$V(E_{\text{filter}})$ is at most

$n/b^{10}\cdot 0.999^{10^{6}\cdot 1.1^{i}\log\log n}\leq n/b^{12}.$

After Step 8, the edge set $E^{\prime}$ contains all edges adjacent to all
roots in $V(G^{\prime})\backslash V(E_{\text{filter}})$, because all vertices
in $V(G^{\prime})$ are roots or children of roots by Lemma 7.1 and
Alter$(E^{\prime})$ moves all edges to roots. By the proof of Lemma 4.24, the
number of roots such that the root has an adjacent edge to another root in
$V(E^{\prime})$ decreases by a factor of $0.001$ w.p. $1-n^{-9}$ in each round
of Step 9. By a union bound over all the at most $(\log n)^{3}$ rounds in Step
9, the number of such roots (with an adjacent edge to another root) in
$V(E^{\prime})$ at the end of Step 9 is at most $n/b^{12}$ w.p. $1-n^{-8}$. By
the same proof as in the proof of Lemma 4.24, the
Reverse$(V(E_{\text{filter}}),E(H_{2}))$ in Step 10 makes the number of active
roots at most $2n/b^{12}\leq n/b^{11}$ w.p. $1-n^{-7}$. ∎

###  7.3 Reducing the Work of Increase

In this section, we modify Step 1 and Step 10 in the Increase$(V,E,b)$ in §5.3
such that the new Increase$(G^{\prime},H_{1},H_{2},b)$ takes $(m+n)/(\log
n)^{2}$ work w.p. $1-2/(\log n)^{2}$.

Increase$(G^{\prime},H_{1},H_{2},b)$:

  1. 1.

Edge set $E_{H}=\textsc{SparseBuild}(G^{\prime},H_{2},b)$, vertex set
$V=V(G^{\prime})$, graph $H=(V(E_{H}),E_{H})$.

  2. 2.

Run Step 2 to Step 9 in the Increase$(V,E,b)$ in §5.3.

  3. 3.

Alter$(E(H_{1}))$.

####  7.3.1 Building Sparse Skeleton Graph

Recall that the Build$(V,E,b)$ in Step 1 of the Increase$(V,E,b)$ in §5.3
takes $O(m+n)$ work (Lemma 5.1), because the sparse subgraph $H$ is computed
based on the input graph $(V,E)$ with $n$ vertices and $m$ edges. The
computation of $H$ relies on classifying vertices as high-degree and low-
degree. One of the key observation is that such classification is still
accurate w.h.p. even if we sample the graph $\overline{G^{\prime}}$ to get
random subgraph $H_{2}$ and classify vertices using edges of $H_{2}$: a high-
degree vertex in $\overline{G^{\prime}}$ is still high-degree w.h.p. in
$H_{2}$ (with different classification threshold). The final subgraph $H$
should also contain all edges adjacent to low-degree vertices. Another key
observation is that the number of edges adjacent to low-degree vertices is
bounded, and we present a new technique to extract all these edges from the
original input graph in $n/\operatorname{poly}(\log n)$ work in §7.4.

SparseBuild$(G^{\prime},H_{2},b)$:

  1. 1.

For each active root $v\in V(G^{\prime})$: assign a block of $b^{9}$
processors, which will be used as an indexed hash table $\mathcal{H}(v)$ of
size $b^{9}$.

  2. 2.

For each edge $(u,v)\in E(H_{2})$: write $(u,v)$ into a random indexed cell of
$\mathcal{H}(v)$.

  3. 3.

For each active root $v\in V(G^{\prime})$: if the number of items in
$\mathcal{H}(v)$ is more than $b^{8}$ then mark $v$ as _high_ , else mark $v$
as _low_.

  4. 4.

$E^{\prime}=\\{(u,v)\in E(G^{\prime})\mid
u.p\text{~{}is~{}a~{}low~{}vertex}\\}$. Alter$(E^{\prime})$.

  5. 5.

Return $E^{\prime}\cup E(H_{2})$.

Note that in Step 2 of the SparseBuild$(G^{\prime},H_{2},b)$, we do not use
hashing by vertex index as in Build$(V,E,b)$. This is because we cannot afford
to removing parallel edges and loops in sublinear work as in Build$(V,E,b)$.
As a result, we only obtain bounds on the vertex degrees (including parallel
edges and loops) instead of bounds on the number of neighbors for each vertex
as in §5.1. We will show that under this case,
Increase$(G^{\prime},H_{1},H_{2},b)$ still makes every root high-degree.

######  Lemma 7.4.

During the execution of Connectivity$(G)$, w.p. $1-n^{-9}$, for any vertex
$v\in V(G^{\prime})$ that is marked as high in any call to
SparseBuild$(G^{\prime},H_{2},b)$, $\overline{\deg}_{G^{\prime}}(v)\geq b^{8}$
in that call; and for any vertex $v\in V(G^{\prime})$ that is marked as low,
$\overline{\deg}_{G^{\prime}}(v)\leq b^{9}$ in that call.

###### Proof.

For any high vertex $v$, it must have degree at least $b^{8}$ in graph $H_{2}$
by Step 2 and Step 3. Thus, the degree of $v$ in $\overline{G^{\prime}}$
(Definition 7.2) is at least $b^{8}$ since $H_{2}$ is a subgraph of
$\overline{G^{\prime}}$ dues to the Alter$(E(H_{2}))$ within
Reverse$(V(E_{\text{filter}}),E(H_{2}))$ in Step 9 of Connectivity$(G)$ and
Lemma 7.1, giving the first part of the lemma by Definition 7.2.

A vertex $v$ is low if at most $b^{8}$ cells in $\mathcal{H}(v)$ are occupied
(Step 3). If $\overline{\deg}_{G^{\prime}}(v)\geq b^{9}$, then since each edge
of $\overline{G^{\prime}}$ is sampled into $H_{2}$ w.p. $1/(\log n)^{7}$ (by
Step 3 of Connectivity$(G)$, Definition 7.2, and the fact that
$\overline{G^{\prime}}$ performs the same Alter as $H_{2}$ by Step 9 of
Connectivity$(G)$ and Lemma 7.1), by a Chernoff bound, we get
$\deg_{H_{2}}(v)\geq b^{9}/(\log n)^{8}\geq b^{8.5}$ w.p. $1-n^{-11}$ by
$b\geq(\log n)^{100}$. Then $v$ is low w.p. at most

$\binom{b^{8.5}}{b^{8}}\cdot\left(\frac{b^{8}}{b^{8.5}}\right)^{b^{9}}\leq
b^{8.5b^{8}}\cdot b^{-0.5b^{9}}\leq b^{-b^{8}}\leq n^{-11},$

where we used $b\geq(\log n)^{100}$. So, w.p. $1-n^{-10}$ all such vertices
are marked as high in one call to SparseBuild$(G^{\prime},H_{2},b)$ by a union
bound. During the execution of Connectivity$(G)$,
SparseBuild$(G^{\prime},H_{2},b)$ is called for at most $10\log\log n$ times
(Step 5 of Connectivity$(G)$). So, all such vertices are marked as high w.p.
$1-n^{-9}$ in any call to SparseBuild$(G^{\prime},H_{2},b)$ by a union bound,
and we shall condition on this happening. Since any vertex $v$ with
$\overline{\deg}_{G^{\prime}}(v)\geq b^{9}$ is marked as high, we have that
any low vertex $v$ must have $\overline{\deg}_{G^{\prime}}(v)\leq b^{9}$. This
gives the second part of the lemma. ∎

######  Lemma 7.5.

Let graph $H$ be computed in Step 1 of Increase$(G^{\prime},H_{1},H_{2},b)$.
W.p. $1-n^{-8}$, for any active root $v\in V(G^{\prime})$, either
$\mathcal{C}_{\overline{G^{\prime}}}(v)=\mathcal{C}_{H}(v)$ or $\sum_{w\in
V(\mathcal{C}_{H}(v))}\deg_{H}(w)\geq b^{6}$.

###### Proof.

The first part of the proof is an analog of the proof of Lemma 5.4. Since the
edge set $E_{H}$ of graph $H$ contains $E^{\prime}$, the set of edges adjacent
to low vertices (Step 4 and Step 5 of SparseBuild$(G^{\prime},H_{2},b)$), we
can run breath-first searches on $\mathcal{C}_{\overline{G^{\prime}}}(v)$ and
$\mathcal{C}_{H}(v)$ simultaneously to get that if there is no high vertex in
$\mathcal{C}_{H}(v)$, then
$\mathcal{C}_{H}(v)=\mathcal{C}_{\overline{G^{\prime}}}(v)$.

On the other hand, if there is a high vertex $w$ in $\mathcal{C}_{H}(v)$, then
by Lemma 7.4, w.p. $1-n^{-9}$, $\overline{\deg}_{G^{\prime}}(w)\geq b^{8}$. By
a Chernoff bound, w.p. $1-n^{-9}$, $\deg_{H_{2}}(w)\geq b^{6}$ because $H_{2}$
is a random subgraph of $\overline{G^{\prime}}$ with edge sampling probability
$1/(\log n)^{7}$ by Step 3 of Connectivity$(G)$, Definition 7.2, and the fact
that $\overline{G^{\prime}}$ performs the same Alter as $H_{2}$ by Step 9 of
Connectivity$(G)$ and Lemma 7.1. So, w.p. $1-n^{-8}$, $\deg_{H}(w)\geq b^{6}$
since $E(H_{2})\subseteq E_{H}$ (Step 5 of SparseBuild$(G^{\prime},H_{2},b)$),
giving the second part of the lemma. ∎

####  7.3.2 Increasing Vertex Degrees by Sparse Skeleton Graph

######  Lemma 7.6.

Let graph $H$ be computed in Step 1 of Increase$(G^{\prime},H_{1},H_{2},b)$.
W.p. $1-1/(\log n)^{6}$, for any component $\mathcal{C}$ in $H$ such that
$\sum_{w\in V(\mathcal{C})}\deg_{H}(w)<b^{6}$, at the end of
Increase$(G^{\prime},H_{1},H_{2},b)$, all vertices in $\mathcal{C}$ must be
roots or children of roots and all edges in $E(H_{1})$ adjacent to these
vertices must be loops.

###### Proof.

By Lemma 7.5, w.p. $1-n^{-8}$,
$V(\mathcal{C})=V(\mathcal{C}_{\overline{G^{\prime}}})$, where
$\mathcal{C}_{\overline{G^{\prime}}}$ is the component in
$\overline{G^{\prime}}$ induced on vertex set $V(\mathcal{C})$. Next, we prove
that the number of vertices in $\mathcal{C}$ is less than $b^{6}$. If
$\mathcal{C}$ contains only $1$ vertex then the claim holds. Otherwise, since
each $v\in V(\mathcal{C})$ has at least $1$ adjacent edge in $H$ (otherwise
$v$ is a singleton), we get $|\mathcal{C}|<b^{6}$ by $\sum_{w\in
V(\mathcal{C})}\deg_{H}(w)<b^{6}$. Therefore, for any shortest path $P$ in
$\mathcal{C}$, there are at most $b^{6}$ vertices on $P$.

Using the same proof as of Lemma 5.24, w.p. $1-1/(\log n)^{7}$, at the end of
Increase$(G^{\prime},H_{1},H_{2},b)$, we obtain that all vertices in
$\mathcal{C}$ must be roots or children of roots and they must be in the same
tree. The Alter$(E(H_{1}))$ in Step 3 of Increase$(G^{\prime},H_{1},H_{2},b)$
moves all edges adjacent to vertices in $\mathcal{C}$ to the root, which must
be loops. ∎

By the same discussion after Lemma 5.24, such small component (with total
degree less than $b^{6}$) in $H$ can be ignored in the rest of the entire
algorithm as the connectivity computation on them is already finished.

######  Lemma 7.7.

During the execution of Connectivity$(G)$, w.p. $1-1/(\log n)^{5}$, for any
integer $i\in[0,10\log\log n)$ and any active root $v\in V(G^{\prime})$ at the
end of Step 2 within Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$,
it must be $\overline{\deg}_{G^{\prime}}(v)\geq b=(\log n)^{100\cdot
1.1^{i}}$.

###### Proof.

By Lemma 7.6, w.p. $1-1/(\log n)^{6}$, any vertex in a component of $H$ with
total degree less than $b^{6}$ is ignored in the rest of the algorithm since
the computation of its component is finished. Therefore, we assume that any
vertex $v\in V$ is in a component with total degree at least $b^{6}$.

If any shortest path in $\mathcal{C}_{H}(v)$ has less than $b^{6}$ vertices on
it, then since Step 2 of Increase$(G^{\prime},H_{1},H_{2},b)$ runs Step 2 to
Step 9 in the Increase$(V,E,b)$ in §5.3, we can use the same proof in the
second paragraph in the proof of Lemma 5.25 to get that w.p. $1-1/(\log
n)^{6}$, all vertices in $\mathcal{C}_{H}(v)$ contracts to $v$. So, the degree
of any root $v\in V(G^{\prime})$ has $\overline{\deg}_{G^{\prime}}(v)\geq
b^{6}/2$ because the total degree of $\mathcal{C}_{H}(v)$ is at least $b^{6}$
and all edges in $\mathcal{C}_{H}(v)$ would be adjacent to $v$ if we executed
Alter$(E(G^{\prime}))$ (Definition 7.2).

If there exists a shortest path in $\mathcal{C}_{H}(v)$ with at least $b^{6}$
vertices on it, then using the same proof in the proof of Lemma 5.25 for this
case, we get that w.p. $1-1/(\log n)^{6}$, the degree of $v$ in $G^{\prime}$
would be at least $b$ if we executed Alter$(E(G^{\prime}))$. Using the same
argument in the previous paragraph, $\overline{\deg}_{G^{\prime}}(v)\geq b$
holds w.p. $1-1/(\log n)^{6}$ for this case.

By a union bound over all $10\log\log n$ phases,
$\overline{\deg}_{G^{\prime}}(v)\geq b$ holds w.p. $1-1/(\log n)^{5}$ for all
integers $i\in[0,10\log\log n)$ and all roots $v\in V(G^{\prime})$. ∎

######  Lemma 7.8.

If the edge set $E^{\prime}$ in Step 4 of SparseBuild$(G^{\prime},H_{2},b)$
can be computed in $n/(\log n)^{7}$ work, then
Increase$(G^{\prime},H_{1},H_{2},b)$ takes $(m+n)/(\log n)^{2}$ work w.p.
$1-1/(\log n)^{2}$.

###### Proof.

By a Chernoff bound, w.p. $1-n^{-9}$, we have $|E(H_{1})|\leq m/(\log n)^{6}$
and $|E(H_{2})|\leq m/(\log n)^{6}$ by Step 3 of Connectivity$(G)$, and we
shall condition on this happening.

In Step 1 of Increase$(G^{\prime},H_{1},H_{2},b)$, consider the work of
SparseBuild$(G^{\prime},H_{2},b)$. Detecting whether a vertex $v\in
V(G^{\prime})$ is an active root can be done by checking whether all of the
following $3$ conditions hold: (i) $v=v.p$, (ii) in the previous phase, at the
end of Step 6 in Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, any
edge in $E_{\text{filter}}$ does not connect $v$ to another root, (iii) in the
previous phase, at the end of Step 9 in
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, any edge in
$E^{\prime}$ does not connect $v$ to another root. Condition (i) can be
checked by all vertices in $V(G^{\prime})$ in $O(1)$ time, taking
$|V(G^{\prime})|\leq n/(\log n)^{10}$ work. Condition (ii) can be checked by
adding $O(|E_{\text{filter}}|)$ work into Step 6 in
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ then write a flag
into the private memory of $v$, which does not change the asymptotic work of
that step. Condition (iii) can be checked by adding $O(|E^{\prime}|)$ work
into Step 9 in Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ then
write a flag into the private memory of $v$, which does not change the
asymptotic work of that step. All in all, the total work (attributes to
SparseBuild$(G^{\prime},H_{2},b)$) of letting each vertex know whether itself
is an active root is $O(n/(\log n)^{10})$.

By Lemma 7.3, w.p. $1-n^{-7}$, the number of active roots is at most
$n/b^{10}$, so Step 1 of SparseBuild$(G^{\prime},H_{2},b)$ takes $O(n/b)\leq
n/(\log n)^{9}$ work (here we assume all active roots are in an index array of
length at most $2n/b^{10}$, which is guaranteed by approximate compaction at
the end of each phase, see Lemma 7.18 for details). Step 2 takes
$O(|E(H_{2})|)\leq O(m/(\log n)^{6})$ work. Step 3 takes $O(n/b^{10}\cdot
b^{9}\cdot O(\log b^{9}))\leq n/(\log n)^{9}$ work by a binary tree counting
argument. Computing edge set $E^{\prime}$ in Step 4 takes $n/(\log n)^{7}$
work by the precondition of the lemma. By Lemma 7.4, w.p. $1-n^{-9}$, for any
vertex $v\in V(G^{\prime})$ that is marked as low,
$\overline{\deg}_{G^{\prime}}(v)\leq b^{9}$, giving at most $b^{9}$ edges in
$E^{\prime}$ adjacent on $v$ by Definition 7.2. Since non-active roots can be
ignored by the discussion after Definition 7.2, and the number of active roots
is at most $n/b^{10}$, we have that $|E^{\prime}|\leq n/b$ w.p. $1-n^{-6}$.
So, the following Alter$(E^{\prime})$ takes $O(|E^{\prime}|)\leq O(n/b)$ work.
Summing up, Step 1 of Increase$(G^{\prime},H_{1},H_{2},b)$ takes $O(m+n)/(\log
n)^{6}$ work.

Consider Step 2 of Increase$(G^{\prime},H_{1},H_{2},b)$. Firstly, we show that
$|E(H)|\leq(m+n)/(\log n)^{5}$ w.p. $1-n^{-8}$. By the previous paragraph,
$|E^{\prime}|\leq n/b$ w.p. $1-n^{-6}$. Since $|E(H_{2})|\leq m/(\log n)^{6}$,
we have that $|E_{H}|=|E(H)|\leq(m+n)/(\log n)^{5}$ w.p. $1-n^{-5}$ by Step 5
of SparseBuild$(G^{\prime},H_{2},b)$. Secondly, the vertex set $V$ in Step 2
to Step 9 of Increase$(V,E,b)$ is replaced by the set of active roots, which
is already described in the second paragraph of this proof and by running
approximate compaction on all active roots at the end of each phase. By Lemma
7.3, the number of active roots is at most $n/b^{10}$. Since the requirements
on $H$ and $|V|$ in §5.3 are satisfied, (the proof of) Lemma 5.19 still holds.
In the Increase$(V,E,b)$ in §5.3, its Step 2 to Step 9 perform $(m+n)/(\log
n)^{2.5}$ work w.p. $1-2/(\log n)^{3}$ (see footnote 14). As a result, Step 2
of Increase$(G^{\prime},H_{1},H_{2},b)$ takes $(m+n)/(\log n)^{2.5}$ work w.p.
$1-2/(\log n)^{3}$.

Step 3 of Increase$(G^{\prime},H_{1},H_{2},b)$ takes $O(|E(H_{1})|)\leq
O(m/(\log n)^{6})$ work. Summing up and by a union bound, the lemma follows. ∎

The computation of the edge set $E^{\prime}$ in Step 4 of
SparseBuild$(G^{\prime},H_{2},b)$ will be given in §7.4.

###  7.4 Reducing the Work of Computing Edge Set $E^{\prime}$

In this section, we present a new technique that work-efficiently computes

  * •

The edge set $E^{\prime}$ in Step 4 of SparseBuild$(G^{\prime},H_{2},b)$.

  * •

The edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$.

####  7.4.1 Building the Auxiliary Array

The computation of edges set $E^{\prime}$ mentioned above relies on an
auxiliary array that is computed and stored in the public RAM at the end of
Stage $1$ where the current graph is $G^{\prime}$ (Step 2 of
Connectivity$(G)$). We need the following tool.

######  Lemma 7.9 (Section 1.3 in [HR92]).

The _padded sort_ is to sort an array of $m$ items such that after sorting,
the items are in sorted order in an array of length at most $2m$. If the item
values to be sorted are integers in $[m]$, then $m$ items can be padded sorted
in $O(\log\log m)$ time and $O(m)$ work w.p. $1-m^{-20}$.

In our application, we padded sort all $m$ edges of $G^{\prime}$ by their
first ends (see below). If $m\leq n^{0.3}$, then the non-singletons in
$G^{\prime}$ are at most $2n^{0.3}$, which can be detected in $O(n)$ work.
Since we only need to compute the connected components of the non-singletons,
one can call Theorem 2 for $\log n$ times in parallel to compute the connected
components of $G^{\prime}$ in $O(\log d+\log\log n)\leq
O(\log(1/\lambda)+\log\log n)$ time and $O(m+2n^{0.3})\cdot\log n\cdot O(\log
n)\leq O(n)$ work w.p. $1-n^{-9}$. Therefore, we assume $m\geq n^{0.3}$, which
means the padded sort succeeds w.p. at least $1-n^{-6}$. Meanwhile, the padded
sort takes $O(\log\log n)$ time by $m\leq n^{c}$.

BuildAuxiliary$(G^{\prime})$:

  1. 1.

Padded sort all edges of $G^{\prime}$ by their first ends and store the output
array $\mathcal{A}$.

  2. 2.

For each item $(v,w)\in\mathcal{A}$ in parallel: if the first end of the
predecessor of $(v,w)$ in $\mathcal{A}$ is not $v$ then write the index of
$(v,w)$ in $\mathcal{A}^{\prime}$ into $v.l$ in the private memory of (the
processor corresponding to) $v$.

  3. 3.

For each item $(v,w)\in\mathcal{A}$ in parallel: if the first end of the
successor of $(v,w)$ in $\mathcal{A}$ is not $v$ then write the index of
$(v,w)$ in $\mathcal{A}$ into $v.r$ in the private memory of $v$.

  4. 4.

For each vertex $v\in V(G^{\prime})$: if $v.r-v.l\geq(\log n)^{90}$ then
(approximate) compact the subarray from index $v.l$ to index $v.r$ (inclusive)
in $\mathcal{A}$.

Padded sorting (Step 1) create empty cells between items. In Step 4, if the
subarray from index $v.l$ to $v.r$ satisfies $v.r-v.l\geq(\log n)^{90}$, then
the non-empty cells are moved to the beginning of this subarray while the
original subarray is erased. The array $\mathcal{A}$ is called the _auxiliary
array_ that is stored in the public RAM and will be used to efficiently
compute the edge set $E^{\prime}$ during the algorithm. Each cell of
$\mathcal{A}$ that contains an edge $e$ also stores the processor id
corresponding to $e$ for the purpose of mapping each edge in $\mathcal{A}$
back to the corresponding edge processor, which can be done by copying the
edge set and storing the corresponding processor id in the item (edge) to be
sorted before padded sorting.

######  Lemma 7.10.

BuildAuxiliary$(G^{\prime})$ takes $O(\log\log n)$ time and $O(m)$ work w.p.
$1-n^{-5}$.

###### Proof.

By Lemma 7.9 and the discussion after it, Step 1 takes $O(m)$ work and
$O(\log\log n)$ time w.p. $1-n^{-6}$. Since $\mathcal{A}$ is indexed, we
assign a processor for each of its cell. Step 2 and Step 3 take $O(m)$ work
and $O(1)$ time by $|\mathcal{A}|\leq 2m$. Step 4 takes $O(\log^{*}n)$ time
and $O(v.r-v.l)$ work w.p. $1-1/2^{(\log n)^{90/25}}\geq 1-n^{-9}$ for each
$v\in V(G^{\prime})$ by Lemma 4.2. W.p. $1-n^{-8}$, the total work of Step 4
is at most $\sum_{v\in V(G^{\prime})}O(v.r-v.l)=O(|\mathcal{A}|)\leq O(m)$ by
telescoping. The lemma follows. ∎

We will use the following property of the auxiliary array $\mathcal{A}$.

######  Lemma 7.11.

Let $\mathcal{A}$ be constructed in BuildAuxiliary$(G^{\prime})$. W.p.
$1-n^{-4}$, for any vertex $v\in V(G^{\prime})$, all edges adjacent on $v$ in
$E(G^{\prime})$ are stored in the subarray of $\mathcal{A}$ that starts from
index $v.l$ and ends at index $v.l+v.s$, where $v.s\leq\max\\{(\log
n)^{90},2\deg_{G^{\prime}}(v)\\}$.

###### Proof.

By the proof of Lemma 7.10, w.p. $1-n^{-5}$, the padded sorting in Step 1 and
all approximate compactions in Step 4 succeed. For any vertex $v\in
V(G^{\prime})$, if $v.r-v.l<(\log n)^{90}$, then all adjacent edges are stored
in the subarray of $\mathcal{A}$ that starts from index $v.l$ and ends at
index $v.r\leq v.l+(\log n)^{90}$, so the lemma holds for this case. Else if
$v.r-v.l\geq(\log n)^{90}$, the all the $\deg_{G^{\prime}}(v)$ edges adjacent
to $v$ are compacted to the subarray of $\mathcal{A}$ that starts from index
$v.l$ and ends at index $v.r\leq v.l+v.s\leq v.l+2\deg_{G^{\prime}}(v)$ by
Definition 4.1, and the lemma holds for this case. ∎

####  7.4.2 Computing the Edge Set in SparseBuild

In this section we show that the edge set $E^{\prime}$ in Step 4 of
SparseBuild$(G^{\prime},H_{2},b)$ can be computed in $n/(\log n)^{7}$ work and
$O(\log b)$ time, giving the precondition of Lemma 7.8.

######  Lemma 7.12.

At the beginning of Step 4 of SparseBuild$(G^{\prime},H_{2},b)$, w.p.
$1-n^{-9}$, for any vertex $u\in V(G^{\prime})$, if $u.p$ is a low vertex,
then $\deg_{G^{\prime}}(u)\leq b^{9}$.

###### Proof.

By Lemma 7.4, w.p. $1-n^{-9}$, $\overline{\deg}_{G^{\prime}}(u.p)\leq b^{9}$,
and we shall condition on this happening. Assume for contradiction that
$\deg_{G^{\prime}}(u)>b^{9}$, then the degree of $u.p$ is more than $b^{9}$ if
we perform Alter$(E(G^{\prime}))$, giving
$\overline{\deg}_{G^{\prime}}(u.p)>b^{9}$, a contradiction. ∎

######  Lemma 7.13.

W.p. $1-n^{-3}$, the edge set $E^{\prime}$ in Step 4 of
SparseBuild$(G^{\prime},H_{2},b)$ can be computed in $O(\log b)$ time and
$n/(\log n)^{7}$ work.

###### Proof.

In Step 4 of SparseBuild$(G^{\prime},H_{2},b)$, each vertex $u\in
V(G^{\prime})$ checks whether $u.p$ is a low vertex using
$O(|V(G^{\prime})|)\leq O(n/(\log n)^{10})$ work in total. If $u.p$ is low,
then we do the following. The processor corresponding to $u$ awakens the
processor corresponding to the cell indexed at $u.l$ of the auxiliary array
$\mathcal{A}$ in round $0$, then in the next round (round $1$) the processor
corresponding to the cell at $u.l$ awakens the cells at $u.l$ and $u.l+1$,
then in round $2$, the processor at $u.l$ awakens $u.l$ and $u.l+1$, and the
processor at $u.l+1$ awakens $u.l+2$ and $u.l+3$, and so on. That is, in round
$j$, each of the $2^{j-1}$ awakened processor at $u.l+k$ awakens the
processors at $u.l+2k$ and $u.l+2k+1$. We continue this process until the
$(9\log b+1)$-th round or a cell containing an edge not starting at $u$ is
awakened. Since in each round, a processor only needs to awaken $2$
processors, the running time for this part is $O(\log b)$. After $9\log b+1$
rounds, all cells indexed from $u.l$ to $u.l+2^{9\log b+1}=u.l+2b^{9}$ such
that the cell contains an edge starting at $u$ are awakened by $u$ (if a cell
containing an edge not starting at $u$ is awakened by $u$, we mark this cell
as not awakened by $u$ to avoid the case that a cell is awakened by more than
$1$ vertices).

By Lemma 7.12, w.p. $1-n^{-9}$, $\deg_{G^{\prime}}(u)\leq b^{9}$ if $u.p$ is a
low vertex. By Lemma 7.11, w.p. $1-n^{-4}$, all edges adjacent on $u$ in
$E(G^{\prime})$ are stored in the subarray of $\mathcal{A}$ that starts from
index $u.l$ and ends at index $u.l+u.s$, where

$u.s\leq\max\\{(\log n)^{90},2\deg_{G^{\prime}}(v)\\}\leq 2b^{9}$

by the previous sentence and $b\geq(\log n)^{100}$. Therefore, if $u.p$ is a
low vertex, then w.p. $1-n^{-3}$, any cell that stores an edge in
$E(G^{\prime})$ adjacent to $u$ is awakened by $u$. The processor
corresponding to each cell then notifies the stored edge (processor) that it
is in $E^{\prime}$, giving the edge set $E^{\prime}$.

The total running time is $O(\log b)$. The total work is at most
$O(|V(G^{\prime})|+O(|E^{\prime}|))\leq n/(\log n)^{7}$ because at most
$2|E^{\prime}|$ cells are awakened in total and $|E^{\prime}|\leq n/b$ w.p.
$1-n^{-6}$ by the third paragraph in the proof of Lemma 7.8. The lemma
follows. ∎

####  7.4.3 Computing the Edge Set in Interweave

In this section we show that the edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ can be computed in
$n/(\log n)^{7}$ work and $O(\log b)$ time.

######  Lemma 7.14.

During the execution of Connectivity$(G)$, w.p. $1-n^{-7}$, for any phase
$i\in[0,10\log\log n)$ and for any vertex $v\in V(G^{\prime})$, if
$\deg_{G^{\prime}}(v)\geq(\log n)^{10^{6}\cdot 1.1^{i}}$, then $v.p\notin
V(G^{\prime})\backslash V(E_{\text{filter}})$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$.

###### Proof.

Since the statement in the lemma is about the algorithm at Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, we can ignore Step 2
to Step 4 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in this
proof, because if the algorithm executes to Step 8, then the labeled digraph
is reverted to its state in Step 1 (by Step 4).

In Step 4 of Connectivity$(G)$, the edge set of $G^{\prime}$ is copied as
$E_{\text{filter}}$. In each phase, the edges in $E_{\text{filter}}$ are
altered and deleted randomly in Step 6 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. For each edge $e\in
E_{\text{filter}}$ at a timestamp of the algorithm, let the _corresponding
edge_ $\overline{e}$ of $e$ be the edge in $E(G^{\prime})$ that is altered (in
Step 6 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$) over
phases to become $e$ at this timestamp, and let $e$ be the _corresponded edge_
of $\overline{e}$.

Let $v$ be a vertex in $V(G^{\prime})$ with $\deg_{G^{\prime}}(v)\geq(\log
n)^{10^{6}\cdot 1.1^{i}}$. At the end of Step 6 in phase $i$, consider the
edge set $\mathcal{E}_{v}$ of corresponded edges of all edges in
$E(G^{\prime})$ adjacent to $v$. For each edge
$\overline{e}\in\mathcal{E}_{v}$, every time the algorithm executes Step 6 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in a phase $j\leq i$,
the edge $\overline{e}$ is deleted w.p. $10^{-4}$. In all the phases before
and including phase $i$, the algorithm executes Step 6 for at most

$\sum_{j=0}^{i}10^{6}\cdot 1.1^{j}\log\log n\leq 10^{8}\log\log n\cdot
1.1^{i}$

times, so the probability that edge $\overline{e}$ ever gets deleted before
phase $i$ is at most

$1-(1-10^{-4})^{10^{8}\log\log n\cdot 1.1^{i}}.$

Since $|\mathcal{E}_{v}|=\deg_{G^{\prime}}(v)\geq(\log n)^{10^{6}\cdot
1.1^{i}}$, the probability that all edges in $\mathcal{E}_{v}$ are deleted
before phase $i$ is at most

$\left(1-(1-10^{-4})^{10^{8}\log\log n\cdot 1.1^{i}}\right)^{(\log
n)^{10^{6}\cdot 1.1^{i}}}\leq\left(1-(\log n)^{-10^{5}\cdot
1.1^{i}}\right)^{(\log n)^{10^{6}\cdot
1.1^{i}}}\leq\left(\frac{1}{e}\right)^{(\log n)^{9}}\leq n^{-9}.$

Therefore, w.p. $1-n^{-9}$, there is an edge in $\mathcal{E}_{v}$ that is not
deleted at the beginning of Step 8 in phase $i$. By the definition of
corresponded edges, there is an edge in $E_{\text{filter}}$ that is adjacent
to $v.p$ at this timestamp, which means $v.p\in V(E_{\text{filter}})$ and thus
$v.p\notin V(G^{\prime})\backslash V(E_{\text{filter}})$. The lemma follows by
a union bound over all the at most $10\log\log n$ phases and all the at most
$n$ vertices. ∎

######  Lemma 7.15.

W.p. $1-n^{-8}$, the edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in any phase
$i\in[0,10\log\log n)$ of Connectivity$(G)$ satisfies $|E^{\prime}|\leq
n/(\log n)^{9}$.

###### Proof.

Note that the definition of edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in phase $i$ is
exactly the edge set $E^{\prime}$ at the end of Step 2 of Extract$(E,k)$ if we
set $k=10^{6}\cdot 1.1^{i}\log\log n$, because $V(E_{\text{filter}})$ is
exactly the vertex set $V^{\prime}$ defined at the end of Step 2 of
Extract$(E,k)$.

Using the same technique used in the proof of Lemma 4.15, we get that the
expected contribution to $|E^{\prime}|$ from each vertex in
$V(E_{\text{filter}})$ is at most $2$, and we get that
$\operatorname*{\mathbb{E}}[|E^{\prime}|]\leq O(|V(E_{\text{filter}})|)$.
Using the technique in §8, we get that w.p. $1-n^{-9}$, $|E^{\prime}|\leq
O(|V(E_{\text{filter}})|)\leq O(|V(G^{\prime})|)\leq n/(\log n)^{9}$. The
lemma follows from a union bound over all phases. ∎

With the above two lemmas, we are ready to give the cost of compute the edge
set $E^{\prime}$.

######  Lemma 7.16.

W.p. $1-n^{-3}$, the edge set $E^{\prime}$ in Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in any phase
$i\in[0,10\log\log n)$ of Connectivity$(G)$ can be computed in $O(\log b)$
time and $n/(\log n)^{7}$ work.

###### Proof.

We shall use the auxiliary array $\mathcal{A}$ built in §7.4.1, similar to the
proof of Lemma 7.13. In Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, each vertex $v\in
V(G^{\prime})$ first checks whether $v.p\in V(G^{\prime})\backslash
V(E_{\text{filter}})$. Since each vertex knows whether itself its in
$V(E_{\text{filter}})$ in $O(1)$ time by adding $O(|E_{\text{filter}}|)$ work
to Step 6 (which does not affect the asymptotic work of Step 6), the above
computation can be done in $O(|V(G^{\prime})|)\leq n/(\log n)^{10}$ work and
$O(1)$ time. Next, each vertex $v$ such that $v.p\in V(G^{\prime})\backslash
V(E_{\text{filter}})$ awakens all its adjacent edges in $\mathcal{A}$
following the same manner in the proof of Lemma 7.13 for $10^{4}\log b$ rounds
or until a cell containing an edge not starting at $v$ is reached. By Lemma
7.14, w.p. $1-n^{-7}$, any such vertex $v$ has $\deg_{G^{\prime}}(v)\leq(\log
n)^{10^{6}\cdot 1.1^{i}}\leq b^{10^{4}}$ by $b=(\log n)^{100\cdot 1.1^{i}}$.
Therefore, by Lemma 7.11, w.p. $1-n^{-4}$, all adjacent edges of any such
vertex $v$ are awakened in $10^{4}\log b$ rounds, and each awakened edge
notifies the edge processor that it is in $E^{\prime}$.

The total running time is $O(\log b)$. The total work is at most $n/(\log
n)^{7}$ because at most $2|E^{\prime}|\leq 2n/(\log n)^{9}$ cells are awakened
w.p. $1-n^{-8}$ by Lemma 7.15. ∎

###  7.5 The Work of Connectivity

In this section, we give the total work of Connectivity$(G)$.

######  Lemma 7.17.

For any graph $G$, w.p. $1-1/\log n$, Connectivity$(G)$ takes
$O(m)+\overline{O}(n)$ work.

###### Proof.

Step 1 takes $O(n)$ work. By Lemma 4.25, w.p. $1-n^{-2}$, Step 2 takes
$O(m)+\overline{O}(n)$ work because the edge set $E^{\prime}$ in Step 4 of
Reduce$(V,E,k)$ satisfies
$\operatorname*{\mathbb{E}}[|E^{\prime}|]\leq\overline{O}(n)$ by the same
proof of Lemma 4.15. Step 3 and Step 4 take $O(m)$ work. Step 6 takes $O(n)$
work.

Consider Step 5. Consider the
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in each phase
$i\in[0,10\log\log n)$. By Lemma 7.8 and Lemma 7.13, the
Increase$(G^{\prime},H_{1},H_{2},b)$ in Step 2 takes $(m+n)/(\log n)^{2}$ work
w.p. $1-2/(\log n)^{2}$. By the same proof for Lemma 5.10, w.p. $1-1/(\log
n)^{3}$, Step 3 takes $(m+n)/(\log n)^{3}$ work, because $|E(H_{1})|$ is
bounded same as $|E(H)|$ required in Densify$(H,b)$. The following
Alter$(H_{1})$ takes $O(|E(H_{1})|)\leq m/(\log n)^{6}$ work w.p. $1-n^{-9}$.
Step 4 without calling Remain$(G^{\prime},H_{1})$ takes the same work as in
the previous step. To implement Step 5, we make a copy of $H_{1}$ at the
beginning of Step 1, which takes $O(|E(H_{1})|)\leq m/(\log n)^{6}$ work w.p.
$1-n^{-9}$. To revert the labeled digraph, we copy all parent pointers for
each vertex $v\in V(G^{\prime})$ in Step 1 which takes $O(|V(G^{\prime})|)\leq
n/(\log n)^{9}$ work, because the vertices in $V(G)\backslash V(G^{\prime})$
are non-roots after Step 2 of Connectivity$(G)$ which do not change their
parent until Step 6 of Connectivity$(G)$. Running approximate compaction on
all active roots (required by $\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$
when assigning blocks to active roots) at the end of each phase takes at most
$n/(\log n)^{7}$ work. As a result, the total work of all steps but Step 6 to
Step 10 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in all
phases except the call to Remain$(G^{\prime},H_{1})$ is at most $2(m+n)/(\log
n)^{2}\cdot 10\log\log n\leq(m+n)/\log n$ w.p. $1-1/(\log n)^{1.5}$.

Next, we show that the total work of Step 6 to Step 10 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ over all phases is at
most $O(m+n)$ w.p. $1-n^{-2}$. To total work of Step 6 over all phases is
$O(m)$ w.p. $1-n^{-8}$. Because the algorithm deletes each edge from
$E_{\text{filter}}$ with constant probability in each round of Step 6 over
phases so $|E_{\text{filter}}|$ decreases by a constant fraction in each round
w.p. $1-n^{-9}$, and the claim follows from a union bound over all the at most
$(\log n)^{4}$ rounds. To total work of Step 7 over all phases is $O(n)$ by
$|V(G^{\prime})|\leq n/(\log n)^{1000}$. By Lemma 7.15 and Lemma 7.16, the
edge set $E^{\prime}$ in Step 8 in any phase $i\in[0,10\log\log n)$ satisfies
$|E^{\prime}|\leq n/(\log n)^{9}$ and Step 8 takes $n/(\log n)^{7}$ work w.p.
$1-n^{-3}$, so the total work of Step 8 and Step 9 over all phases is at most
$O(1.1^{10\log\log n}\log\log n)\cdot n/(\log n)^{9}+n/(\log n)^{7}\leq O(n)$
w.p. $1-n^{-3}$. Step 10 in each phase takes
$O(|V(E_{\text{filter}})|+|E(H_{2})|)$ work, which is at most
$O(|V(G^{\prime})|+n/(\log n)^{6})\leq n/(\log n)$ w.p. $1-n^{-8}$, so the
total work of Step 10 over all phases is $O(n)$ w.p. $1-n^{-7}$.

Finally, we show that the call to Remain$(G^{\prime},H_{1})$ in Step 4 takes
$O(m+n)$ work w.p. $1-1/(\log n)^{8}$, which completes the proof because it is
called for $1$ time during the execution of Connectivity$(G)$. Step 1 and Step
2 of Remain$(G^{\prime},H_{1})$ take $O(|E(G^{\prime})|)\leq O(m)$ work. Step
3 take $O(m)$ work w.p. $1-n^{-9}$ by PRAM perfect hashing [GMV91]. We claim
that at the beginning of Step 4, $|E_{\text{remain}}|\leq n/(\log n)^{6}$ w.p.
$1-n^{-9}$. Since the algorithm runs Alter$(E(G^{\prime}))$ in Step 1, the
graph $H_{1}$ is an (unbiased) random subgraph of $G^{\prime}$ by sampling
each edge w.p. $1/(\log n)^{7}$ independently. The key observation is that,
although $H_{1}$ has been used (in Step 2 to Step 5 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$) before the current
phase, it is reverted to its initial state (in Step 5 of the previous phase),
so the execution of the algorithm before phase $i$ (excluding Step 2 to Step 5
in each previous phase, which is irrelevant to the analysis of the current
phase) is independent of the randomness in generating $H_{1}$.191919Without
this observation, it could be the case that the execution of the algorithm
before the current phase is dependent on the generation of $H_{1}$, such that
$H_{1}$ is not an unbiased random subgraph of $\overline{G^{\prime}}$ given
the fact that the algorithm does not terminate before the current phase.  By
the sampling lemma of Karger, Klein and Tarjan ([KKT95]), the number of edges
in $G^{\prime}$ connecting different connected components of its random
subgraph $H_{1}$ is at most $O(|V(G^{\prime})|/p)$ w.p. $1-n^{-9}$ where the
edge sampling probability $p=(1/(\log n)^{7})$.202020[KKT95] states a more
general version for the application in minimum spanning tree and the bound on
the number of inter-component edges is in expectation. A high-probability
result is a straightforward corollary (e.g., see [HZ96], Lemma 9.1).
Therefore, $|E_{\text{remain}}|\leq n/(\log n)^{6}$ w.p. $1-n^{-9}$ at the
beginning of Step 4. By Theorem 2, Step 4 takes at most $n/(\log n)^{6}\cdot
O(\log n)$ work w.p. $1-1/(\log n)^{9}$. ∎

###  7.6 The Running Time and Correctness of Connectivity

In this section, we give the running time of Connectivity$(G)$ and prove that
it correctly computes the connected components of the input graph $G$.

######  Lemma 7.18.

During the execution of Connectivity$(G)$, w.p. $1-1/(\log n)^{2}$, for any
integer $i\in[0,10\log\log n)$, phase $i$ in Step 5 takes $O(\log b)$ time
unless $E_{\text{filter}}=\emptyset$, where $b=(\log n)^{100\cdot 1.1^{i}}$.

###### Proof.

Consider the Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in phase
$i$. Consider the $\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$ in Step 2 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. In Step 1 of
$\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$, we calculate the running time
of $\textsc{SparseBuild}(G^{\prime},H_{2},b)$. We already described how to let
each vertex in $V(G^{\prime})$ knows whether itself is an active root in the
proof of Lemma 7.8, so at the end of each phase the algorithm runs approximate
compaction on all active roots to compact them in an index array of length
$O(n/b^{10})$ in $O(\log^{*}n)$ time w.p. $1-n^{-6}$ by Lemma 7.3. Step 1 of
$\textsc{SparseBuild}(G^{\prime},H_{2},b)$ takes $O(1)$ time since the active
roots are indexed. Step 2 takes $O(1)$ time. Step 3 takes $O(\log b)$ time by
the binary tree counting argument. Step 4 takes $O(\log b)$ time w.p.
$1-n^{-3}$ by Lemma 7.13. Therefore, Step 1 of
$\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$ takes $O(\log b)$ time w.p.
$1-2n^{-3}$. By the fourth paragraph in the proof of Lemma 7.8 and Lemma 5.19,
Step 2 of $\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$ takes $O(\log b)$ time
w.p. $1-2/(\log n)^{3}$. (This probability will be boosted to $1-n^{-c}$ in
§8.) Summing up, $\textsc{Increase}(G^{\prime},H_{1},H_{2},b)$ takes $O(\log
b)$ time w.p. $1-3/(\log n)^{3}$.

Consider Step 3 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$.
By Lemma 5.8, each $\textsc{Expand-Maxlink}(H_{1})$ takes $O(1)$ time w.p.
$1-1/(\log n)^{6}$. So all $20\log b$ rounds of Step 3 take $O(\log b)$ time
w.p. $1-1/(\log n)^{5}$. By Theorem 2, the following call takes $O(\log\log
n)\leq O(\log b)$ time w.p. $1-1/(\log n)^{8}$ by $b\geq(\log n)^{100}$. The
Alter$(E(H_{1}))$ takes $O(1)$ time. Summing up, Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ takes $O(\log b)$
time w.p. $1-1/(\log n)^{7}$.

In Step 4 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ the
algorithm only needs to check whether all edges in $E(H_{1})$ are loops
without calling Remain$(G^{\prime},H_{1})$ because the algorithm does not
return $\emptyset$, which can be done in $O(1)$ time. Step 5 can be done in
$O(1)$ time by the second paragraph in the proof of Lemma 7.17. Each round of
Step 6 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ can be done
in $O(1)$ time by Lemma 4.3. So Step 6 takes $O(10^{6}\cdot 1.1^{i}\log\log
n)=O(\log b)$ time by $b=(\log n)^{100\cdot 1.1^{i}}$. Step 7 takes
$O(i+2\log\log n)\leq O(\log\log n)\leq O(\log b)$ time. Step 8 takes $O(\log
b)$ time w.p. $1-n^{-3}$ by Lemma 7.16. Step 9 takes $O(\log b)$ time, same as
Step 6. Step 10 takes $O(1)$ time.

Summing up and by a union bound, the lemma follows. ∎

######  Lemma 7.19.

During the execution of Connectivity$(G)$, w.p. $1-1/(\log n)^{7}$, for any
integer $i\in[0,10\log\log n)$, if the
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in phase $i$ returns
$\emptyset$, then the Remain$(G^{\prime},H_{1})$ in Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ takes $O(\log
d+\log\log n)$ time where $d$ is the maximum diameter of $G$, and
Connectivity$(G)$ computes all the connected components of $G$.

###### Proof.

Let $i\in[0,10\log\log n)$ be the last phase of Connectivity$(G)$. By Step 1
of Connectivity$(G)$ and Lemma 4.21, Step 2 is a contraction algorithm. Note
that in each phase $j<i$, Step 6 to Step 9 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ is a contraction
algorithm on graph $G^{\prime}$ by the same proof for Lemma 4.21. Vertices in
$V(G)\backslash V(G^{\prime})$ are non-roots created at the end of Step 2 of
Connectivity$(G)$. Therefore, the execution of Connectivity$(G)$ before phase
$i$ is a contraction algorithm if we execute Shortcut$(V(G))$ (which will be
done in Step 6 of Connectivity$(G)$).

Now consider phase $i$. A proof similar to the proof of Lemma 5.22 shows that
Step 2 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ is a
contraction algorithm on $G^{\prime}$ if we execute Alter$(E(G^{\prime}))$, so
Step 2 is a contraction algorithm on $H_{1}$. By the same proof of Lemma 5.9,
w.p. $1-1/(\log n)^{8}$, Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ is a contraction
algorithm on $H_{1}$. In Step 4 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, since all edges in
$E(H_{1})$ are loops, all connected components of $H_{1}$ are computed because
Step 2 and Step 3 are contraction algorithms on $H_{1}$. Now consider
Remain$(G^{\prime},H_{1})$ in Step 4.212121The algorithm needs to run
Remain$(G^{\prime},H_{1})$ to maintain correctness because if the assumption
$\lambda\geq b^{-0.1}$ is wrong in this phase, then the edge sampling on
$G^{\prime}$ (to obtain $H_{1}$) disconnects some components of $G^{\prime}$,
but Step 3 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$
contracts all components of $H_{1}$ either because the contraction algorithm
on $H_{1}$ takes less running time than its upper bound or the disconnection
does not create any component with spectral gap less than $\lambda$. In both
cases, the computation of connected components of $G^{\prime}$ is not
finished, which will be done in Remain$(G^{\prime},H_{1})$ by adding all the
remaining edges unsampled into $H_{1}$. §6 is correct without
Remain$(G^{\prime},H_{1})$ because $\lambda\geq b^{-0.1}$ holds. Step 1 of
Remain$(G^{\prime},H_{1})$ takes $O(1)$ time. Step 2 takes $O(1)$ time to let
each edge of $E(G^{\prime})$ check whether itself is in $H_{1}$. Step 3 take
$O(\log^{*}n)$ time w.p. $1-n^{-9}$ by PRAM perfect hashing [GMV91]. Note that
the diameter of graph $(V(E_{\text{remain}}),E_{\text{remain}})$ is at most
$d$ because computing all connected components of $H_{1}$ and executing
Alter$(E(G^{\prime}))$ is a contraction algorithm on $G^{\prime}$ and any
contraction does not increase the diameter; moreover, removing loops and
parallel edges from $E_{\text{remain}}$ does not influence the diameter of the
graph. Therefore, Step 4 takes $O(\log d+\log\log n)$ time w.p. $1-1/(\log
n)^{9}$ by Theorem 2, and it computes all connected components of
$G^{\prime}$.

By the first paragraph, the algorithm computes all connected components of $G$
after Step 6 of Connectivity$(G)$. The lemma follows from a union bound. ∎

######  Lemma 7.20.

For any graph $G$ with component-wise spectral gap $\lambda$, w.p. $1-1/(\log
n)^{4}$, Connectivity$(G)$ computes all the connected components of $G$ before
or in phase $i$, where $i\in[0,10\log\log n)$ is the minimum integer that
satisfies $(\log n)^{-10\cdot 1.1^{i}}\leq\lambda$.

###### Proof.

First of all, such an integer $i$ must exist because $(\log n)^{-10\cdot
1.1^{9c\log\log n}}\leq n^{-9c}$, and $\lambda\geq\phi^{2}/2\geq m^{-2}/2\geq
n^{-3c}$ by Cheeger’s inequality and $m\leq n^{c}$ where constant $c\geq 2$.

By Lemma 7.19, w.p. $1-1/(\log n)^{8}$, if Connectivity$(G)$ terminates in a
phase $j\in[0,10\log\log n)$, then it correctly computes all connected
components of $G$. Suppose Connectivity$(G)$ does not terminate before phase
$i$. Consider phase $i$ and let $b=(\log n)^{100\cdot 1.1^{i}}$. By Lemma 7.7,
w.p. $1-1/(\log n)^{5}$, it must be $\overline{\deg}_{G^{\prime}}(v)\geq b$
for any active root $v\in V(G^{\prime})$ at the end of Step 2 within
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. By Definition 7.2
and Step 3 of Connectivity$(G)$, at the end of Step 2 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, the graph $H_{1}$ is
an (unbiased) random subgraph of $\overline{G^{\prime}}$ by sampling each edge
w.p. $1/(\log n)^{7}$ independently (see the observation in last paragraph in
the proof of Lemma 7.17 and footnote 19). Note that the component-wise
spectral gap of $\overline{G^{\prime}}$ is at least $\lambda$ since the
algorithm only performs contractions on $G$ (same as in §6). Now since
$\deg(\overline{G^{\prime}})\geq b$ and the sampling probability $p=1/(\log
n)^{7}$, we have that $p\cdot\deg(\overline{G^{\prime}})\geq C\ln n$ and thus
Corollary C.3 is applicable. We have that w.p. $1-n^{-9}$, the component-wise
spectral gap $\lambda^{\prime}$ of $H_{1}$ satisfies

$\lambda^{\prime}\geq\lambda-C^{\prime}\cdot\sqrt{\frac{\ln n}{1/(\log
n)^{7}\cdot b}}\geq b^{-0.1}-b^{-0.4}\geq b^{-0.2}$

by $\lambda\geq(\log n)^{-10\cdot 1.1^{i}}=b^{-0.1}$, where $C^{\prime}$ is
the constant in Corollary C.3. So the maximum diameter $d^{\prime}$ over all
components of $H_{1}$ is at most $O(\log n/\lambda^{\prime})\leq b^{0.3}$.
Since any shortest path of $H$ has at most $b^{0.3}+1\leq b^{7}$ vertices, we
can apply the same proof of Lemma 5.17 to get that $20\log b$ rounds of
$H_{1}=\textsc{Expand-Maxlink}(H_{1})$ (Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$) contracts $H_{1}$
such that its diameter becomes at most $1$ w.p. $1-1/(\log n)^{8}$, and the
following call to Theorem 2 computes all connected components of $H_{1}$ in
$O(\log\log n)$ time w.p. $1-1/(\log n)^{9}$ (the same, more detailed proof
appears in [LTZ20]). As a result, the following Alter$(H_{1})$ makes all edges
in $E(H_{1})$ loops and Step 4 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ returns $\emptyset$.
So phase $i$ is the last phase and Connectivity$(G)$ correctly computes all
connected components of $G$ by the second paragraph of this proof. The lemma
follows from a union bound. ∎

######  Lemma 7.21.

For any graph $G$ with component-wise spectral gap $\lambda$, w.p. $1-1/\log
n$, Connectivity$(G)$ computes all the connected components of $G$ in
$O(\log(1/\lambda)+\log\log n)$ time.

###### Proof.

By Lemma 4.25, w.p. $1-n^{-2}$, Step 2 of Connectivity$(G)$ takes $O(\log\log
n)$ time. By Lemma 7.10, the BuildAuxiliary$(G^{\prime})$ at the end of Step 2
takes $O(\log\log n)$ time w.p. $1-n^{-5}$ (required for reducing the work,
see §7.4.1). Step 3, Step 4, and Step 6 take $O(1)$ time. W.p. $1-2/(\log
n)^{2}$, assuming Lemma 7.18, Lemma 7.19, and Lemma 7.20 hold.

Let phase $i$ be the last phase of Connectivity$(G)$. If $i=0$, then in
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ of phase $0$, before
calling Remain$(G^{\prime},H_{1})$ in its Step 4, the algorithm takes
$O(\log((\log n)^{100}))=O(\log\log n)$ time by the proof of Lemma 7.18. Now
suppose $i\geq 1$. By Lemma 7.20, it must be

$\lambda\leq(\log n)^{-10\cdot 1.1^{i+1}}.$ (6)

By Lemma 7.18, the total running time in Step 5 of Connectivity$(G)$ before
calling Remain$(G^{\prime},H_{1})$ in phase $i$ is at most

$\sum_{j<i}O\left(\log\left(\left(\log n\right)^{100\cdot
1.1^{j}}\right)\right)\leq\sum_{j<i}O\left(1.1^{j}\log\log n\right)\leq
O\left(1.1^{i}\log\log n\right)\leq O\left(\log\left(1/\lambda\right)\right),$

where the last inequality is by Equation (6). By Lemma 7.19, the
Remain$(G^{\prime},H_{1})$ in phase $i$ takes $O(\log d+\log\log n)\leq
O(\log(1/\lambda)+\log\log n)$ time by $d\leq O(\log n/\lambda)$. Summing up
and by a union bound, the lemma follows. ∎

The success probability $1-1/\log n$ will be boosted to $1-n^{-c}$ for
arbitrary constant $c>0$ in §8.

##  8 Boosting the Work and Success Probability

In this section we improve the total work of our algorithm to $O(m+n)$ and the
success probability to high probability in $n$.

###  8.1 Bounding the Size of Edge Set with High Probability

The main step towards getting a high probability bound is to show that in the
execution of Extract$(E,k)$, the size of each $E_{i}$ is bounded by $2\cdot
0.999^{i-1}\cdot n$ with high probability for $i\in[1,k]$. As we discussed in
the proof of Lemma 4.15 in order for some edge $(v,u)$ to contribute to
$E_{i+1}$ through a vertex $v$, all of the edges originally in $E_{i,v}$ must
be deleted by the end of the Filter$(E^{\prime},k)$. We show that the excepted
number of edges that contribute to $E_{i+1}$ is concentrated around its mean.
The main challenge to provide a concentration bound is that the events that
two different edges $e,e^{\prime}\in E_{i}$ contribute to $E_{i+1}$ are not
necessarily independent from each other. For example, suppose that $e=(v,u)$
and $e^{\prime}=(v,u^{\prime})$. In this case $e$ and $e^{\prime}$ share a
common endpoint and if we condition on the event that $e$ contributes to
$E_{i+1}$, then it implies that all of the edges in $E_{i,v}$ or all edges in
$E_{i,u}$ are deleted within Filter. This intuitively increases the
probability that $e^{\prime}$ contributes to the $E_{i+1}$ since if all edges
in $E_{i,v}$ are deleted, then $e^{\prime}$ also has a good chance contributes
to the matching. The reason that we cannot say that $e^{\prime}$ contributes
to $E_{i+1}$ with the probability $1$, is that $e^{\prime}$ might have moved
to some other vertex and that vertex might have some edges that are not
deleted by the end of Filter. This however, still shows a possible positive
correlation between the contribution of vertices, and we can’t simply use
Chernoff-like concentration bounds as there are only valid for random
variables with negative association.

In order to prove the concentration bound, we take two steps. First we show
that for all rounds $i$ and vertices $v\in V^{\prime}_{i}$ if $|E_{i,v}|\geq
1000\log n$, then with the high probability no edges contribute to $E_{i+1}$
through these vertices. Therefore, we can assume that for every vertex $v$
such that some edge contributes to $E_{i+1}$ through $v$ we have
$|E_{i,v}|<1000\log n$, thus the total contribution of $v$ is relatively
small. We then use this observation, and apply the concentration bound for
self-bounding functions to show that $E_{i}$ is bounded by $2\cdot
0.999^{i-1}\cdot n$ with high probability.

Consider any edge $e\in E_{i}$, the probability that this edge gets deleted by
the end of Filter$(E^{\prime},k)$ is $(1-(1-10^{-4})^{k+1})$. Since we run the
algorithm for $k=1000\log\log\log n$, then we have the following bound for the
probability that $e$ gets deleted by the end of the Filter$(E^{\prime},k)$.

$\displaystyle(1-(1-10^{-4})^{k+1})=(1-(1-10^{-4})^{1000\log\log\log n+1})\leq
1-\frac{1}{\log\log n}.$

Now suppose that for a vertex $v\in V^{\prime}_{i}$ we have $|E_{i,v}|\geq
1000\log n$, then the probability that all of the edges in $|E_{i,v}|$ gets
deleted is at most

$\displaystyle(1-\frac{1}{\log\log n})^{1000\log n}\leq n^{-10}.$

Therefore, we can say that if for a vertex $v$, we have $|E_{i,v}|\geq
1000\log n$, then no edges will contribute to $E_{i+1}$ through $v$ with the
probability of $(1-n^{-10})$. By taking the union bound over all possible $n$
different vertices $v$ and $k$ rounds of Extract$(E,k)$, we can say that with
the probability of at least $(1-n^{-9}k)\leq(1-n^{-8})$, for all rounds
$i\in[0,k-1]$ if a vertex $v\in V^{\prime}_{i}$ has more than $1000\log n$
edges in $E_{i,v}$, then none of these edges contribute to $E_{i+1}$ through
$v$.

For a round $i$ of Extract$(E,k)$, let $V^{\prime\prime}_{i}$ be the set of
vertices in $V_{i}$ such that for each $v\in V^{\prime\prime}_{i}$ we have
$|E_{i,v}|<1000\log n$. As we discussed, all of the contribution to $E_{i+1}$
are through vertices in $V^{\prime\prime}_{i}$ with high probability in $n$.
This means that with high probability in $n$, the total contribution of all
vertices to $E_{i+1}$ is at most $1000\log n$. We then use this property, and
apply the concentration bounded for self-bounding functions. First we define
the self-bounding functions.

######  Definition 8.1.

Let $X_{1},X_{2},\cdots,X_{n}$ be $n$ independent random variables taking
values in some measure space $\mathcal{X}$. Also, let
$f:\mathcal{X}^{n}\rightarrow\mathbb{R}$, then $f$ is $(a)$-self-bounding if
there exists functions
$f_{1},f_{2},\cdots,f_{n}:\mathcal{X}^{n-1}\rightarrow\mathbb{R}$ such that

$\displaystyle 0\leq f(x)-f_{j}(x^{(j)})\leq 1\,.$

And,

$\displaystyle\sum_{i=1}^{n}\big{(}f(x)-f_{j}(x^{(j)})\big{)}\leq a\cdot
f(x)\,.$

For all inputs $x=(x_{1},x_{2},\cdots,x_{n})\in\mathcal{X}^{n}$ where
$x^{(j)}=(x_{1},\cdots,x_{j-1},x_{j+1},\cdots,x_{n})$ is the $x$ when
$j^{\text{th}}$ element is dropped.

The following concentration bound is known for self-bounding functions

######  Lemma 8.2 ([BLM09]).

Let $Z=f(X_{1},X_{2},\cdots,X_{n})$, then if $f(.)$ is $(a)$-self-bounding
function we have

$\displaystyle\Pr[Z\geq\operatorname*{\mathbb{E}}[Z]+t]\leq\exp\bigg{(}\frac{-t^{2}}{2a\operatorname*{\mathbb{E}}[Z]+a\cdot
t}\bigg{)}\,.$

We now use the concentration bound above, to provide a concentration bound for
$|E_{i+1}|$. Let us fix an ordering on the edges in $E_{i}$ and assume that
$|E_{i}|=\\{e_{1},e_{2},\cdots,e_{\ell}\\}$ where $\ell=|E_{i}|$. Also, let
$X_{e_{1}},X_{e_{2}},\cdots,X_{e_{\ell}}$ be $\ell$ random variables where
$X_{e_{j}}$ indicates whether $e_{j}$ is deleted by the end of the
Filter$(E^{\prime},k)$. Specifically, $X_{e_{j}}=1$ if $e_{j}$ is deleted by
Filter, and it is $0$ otherwise. It is then clear that these random variables
are independent as Filter deletes each edge independent of others. Now we
define function $f_{v}:\\{0,1\\}^{\ell}\rightarrow\mathbb{R}$ as follows for
every $v\in V^{\prime\prime}_{i}$.

$f_{v}(x)=\begin{cases}|E_{i,v}|,&\text{If for all edges $e\in E_{i,v}$ we
have $x_{e}=1$}\\\ &\text{, i.e., all edges in $E_{i,v}$ are deleted based on
the input $x$}\\\ 0,&\text{Otherwise}\end{cases}$

and we define function $f$ as follows $f(x)=\frac{\sum_{v\in
V^{\prime\prime}_{i}}f_{v}(x)}{2000\log n}$. We then claim that $f$ is
$(1000\log n)$-self-bounding.

######  Claim 8.3.

Let $f$ be the function defined as above, then $f$ is $(1000\log n)$-self-
bounding.

###### Proof.

For each $e_{j}\in E_{i}$, we define function $f_{e_{j}}(x^{(e_{j})})$ as
below.

$\displaystyle
f_{e_{j}}(x^{(e_{j})})=f(x_{e_{1}},\cdots,x_{e_{i-1}},0,x_{e_{i+1}},\cdots,x_{e_{\ell}})\,.$

In other words, $f_{e_{j}}(x^{(e_{j})})$ is the same as function $f$ when we
change that $e_{j}$ is not deleted. For each $e_{j}$, we use $x^{\prime}_{j}$
to denote the input sequence
$(x_{e_{1}},\cdots,x_{e_{i-1}},0,x_{e_{i+1}},\cdots,x_{e_{\ell}})$. Thus, it
is equivalent to define $f_{e_{j}}(x^{(e_{j})})=f(x^{\prime}_{j})$. Also, for
an input sequence $x$, we use $\eta(x)$ to denote the set of vertices in
$V^{\prime\prime}_{i}$ such that for each $v\in\eta(x)$ all edges in $E_{i,v}$
are deleted according to $x$. Based on this definition, we can re-write
function $f$ as follows.

$\displaystyle f(x)=\frac{\sum_{v\in\eta(x)}|E_{i,v}|}{2000\log n}$

Now we are ready to show these function $f$ satisfies the properties of self-
bounding functions. Considering the first property we have to show that for
every edge $e_{j}$ we have

$\displaystyle 0\leq f(x)-f_{e_{j}}(x^{(e_{j})})\leq 1$

Let $e_{j}=(v^{\prime},u^{\prime})$. It is then clear that
$\eta({x^{\prime}_{j}})\subseteq\eta(x)$ since in $x^{\prime}$ we are changing
the input such that $e_{j}$ is not deleted, and it is only changed for one
edge. Then by the definition of functions $f(.)$ and $f_{e_{j}}(.)$ we have

$\displaystyle f(x)-f_{e_{j}}(x^{(e_{j})})$
$\displaystyle=f(x)-f(x^{\prime}_{j})$
$\displaystyle=\frac{\sum_{v\in\eta(x),v\notin\eta({x^{\prime}_{j}})}|E_{i,v}|}{2000\log
n}$ (7)
$\displaystyle\leq\frac{|E_{i,v^{\prime}}|+|E_{i,u^{\prime}}|}{2000\log n}$
$\displaystyle(\text{$\eta({x^{\prime}_{j}})$ is different from $\eta(x)$ for
at most vertices adjacent to $e_{j}$})$ $\displaystyle\leq 1\,.$
$\displaystyle(\text{Since $|E_{i,v}|\leq 1000\log n$ for every vertex $v\in
V^{\prime\prime}_{i}$ })$

Thus, function $f$ satisfies the first property of self-bounding functions.

For the second property we have

$\displaystyle\sum_{e_{j}\in E_{i}}f(x)-f_{e_{j}}(x^{(e_{j})})$
$\displaystyle=\sum_{e_{j}\in
E_{i}}\bigg{(}\frac{\sum_{v\in\eta(x),v\notin\eta({x^{\prime}_{j}})}|E_{i,v}|}{2000\log
n}\bigg{)}$ $\displaystyle\leq\sum_{v\in\eta(x)}\bigg{(}\frac{1000\log
n\cdot|E_{i,v}|}{2000\log n}\bigg{)}$
$\displaystyle(\text{$\eta({x^{\prime}_{j}})$ is different from $\eta(x)$ for
at most vertices adjacent to $e_{j}$}$ $\displaystyle\text{and each $v\in
V^{\prime\prime}_{i}$ is adjacent to at most $1000\log n$ edges})$
$\displaystyle=\sum_{v\in\eta(x)}\bigg{(}\frac{|E_{i,v}|}{2}\bigg{)}$
$\displaystyle=1000\log n\cdot f(x)\,.$

Thus, function $f$ is $(1000\log n)$-self-bounded and it proof the claim. ∎

We now show the concentration bound for $E_{i+1}$. Recall that
$X_{e_{1}},X_{e_{2}},\cdots,X_{e_{\ell}}$ are the random variables where
$X_{e_{i}}$ indicates whether $e_{i}$ is deleted by the end of the Filter.
Also, let $\vec{X}=(X_{e_{1}},X_{e_{2}},\cdots,X_{e_{\ell}})$. First we claim
that with the probability of $(1-n^{-8})$ we have $|E_{i+1}|\leq\sum_{v\in
V^{\prime\prime}_{i}}f_{v}(\vec{X})$. The reason is that in order an edge
$(v,u)$ contribute to $E_{i+1}$, for at least one of its endpoints, let’s say
$v$, all the edges in $E_{i,v}$ must be deleted. In this case $f_{v}(\vec{X})$
is $E_{i,v}$ which is an upper bound on the number of edges that contribute to
$E_{i+1}$ through $v$. Also with the probability of at least $(1-n^{-8})$ all
of the contribution to $E_{i+1}$ are through vertices in
$V^{\prime\prime}_{i}$. This implies that $|E_{i+1}|\leq\sum_{v\in
V^{\prime\prime}_{i}}f_{v}(\vec{X})$, and $\frac{|E_{i+1}|}{2000\log n}\leq
f(\vec{X})$.

Also, as we discussed in the proof of Lemma 4.15, the expected number of edges
contributed through each vertex $v\in V^{\prime}_{i}$ is upper bounded by $1$.
Using the similar argument we can say that
$\operatorname*{\mathbb{E}}[f_{v}(\vec{X})]\leq 1$ for each $v\in
V^{\prime\prime}_{i}$. Thus,
$\operatorname*{\mathbb{E}}[f(\vec{X})]\leq\frac{|V^{\prime\prime}_{i}|}{2000\log
n}$. Let $Z=f(\vec{X})$. Since $f$ is $(1000\log n)$-self-bounded function,
using the concentration bound for self-bounding functions we can say

$\displaystyle\Pr[Z\geq\operatorname*{\mathbb{E}}[Z]+n^{0.6}]$
$\displaystyle\leq\exp\bigg{(}\frac{-n^{1.2}}{2000\log
n\operatorname*{\mathbb{E}}[Z]+1000\log n\cdot n^{0.6}}\bigg{)}$
$\displaystyle\leq\exp\bigg{(}\frac{-n^{1.2}}{|V^{\prime\prime}_{i}|+1000\log
n\cdot n^{0.6}}\bigg{)}$ $\displaystyle(\text{Since
$\operatorname*{\mathbb{E}}[Z]\leq\frac{|V^{\prime\prime}_{i}|}{2000\log
n}$})$ $\displaystyle\leq\exp\bigg{(}\frac{-n^{1.2}}{n+1000\log n\cdot
n^{0.6}}\bigg{)}\leq n^{-10}$ $\displaystyle(\text{Since
$|V^{\prime\prime}_{i}|\leq n$}).$

Recall that with the probability of at least $(1-n^{-8})$ we had
$\frac{|E_{i+1}|}{2000\log n}\leq f(\vec{X})$. By combining this with the
concentration bound above, we can say with the probability of at least
$(1-n^{-7})$ we have

$\displaystyle\frac{|E_{i+1}|}{2000\log
n}\leq\operatorname*{\mathbb{E}}[f(\vec{X})]+n^{0.6}$

Thus,

$\displaystyle|E_{i+1}|$ $\displaystyle\leq 2000\log n\cdot
E[f(\vec{X})]+2000\log n\cdot n^{0.6}$ $\displaystyle=\sum_{v\in
V^{\prime\prime}_{i}}E[f_{v}(\vec{X})]+2000\log n\cdot n^{0.6}$
$\displaystyle\leq|V^{\prime\prime}_{i}|+2000\log n\cdot n^{0.6}\,.$

By Lemma 4.12, with the probability of at least $1-kn^{-9}\geq 1-n^{-8}$, we
have $|V^{\prime\prime}_{i}|\leq 0.999^{i}\cdot n$. Thus with the probability
of at least $1-n^{-6}$ we have

$\displaystyle|E_{i+1}|\leq|V^{\prime\prime}_{i}|+2000\log n\cdot n^{0.6}\leq
2\cdot 0.999^{i}\cdot n\,,$

which proves the following lemma.

######  Lemma 8.4.

For each round $i\in[1,k]$ of Extract, with the probability of at least
$1-n^{-6}$ we have $|E_{i}|\leq 2\cdot 0.999^{i-1}\cdot n$.

We can use the same technique to provide the high probability bound for the
size of $E^{\prime}$ in the
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$.

######  Corollary 8.5.

Let $E^{\prime}$ be the set of edges by end of Step 8 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. Then,
$|E^{\prime}|\leq 10^{9}\cdot n$ with the probability of at least $1-n^{-6}$.

###### Proof.

The set $E^{\prime}$ is computed in the same way that $E_{i+1}$ is computed in
round $i$ of Extract. The only difference is that in the proof above, we are
assuming that each edge gets deleted with the probability of $(1-10^{-4})$ for
$1000\log\log\log n$ rounds. However,
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ this happens for
every edge for $10^{6}\cdot 1.1^{i}\log\log n$ rounds. Also, it is guaranteed
that $10^{6}\cdot 1.1^{i}\log\log n$ is bounded by $10^{6}\cdot(\log n)^{3}$.
We show that we can still claim that in order for a vertex to have a
contribution to $E^{\prime}$, it should have at most $10^{8}\cdot(\log n)^{4}$
edges. Consider a vertex with at least $10^{8}\cdot(\log n)^{4}$ edges. Then,
the probability that all of these edges get deleted is

$\displaystyle(1-(1-10^{-4})^{10^{6}\cdot 1.1^{i}\log\log
n})^{10^{8}\cdot(\log n)^{4}}\leq(1-(1-10^{-4})^{10^{6}\cdot(\log
n)^{3}})^{10^{8}\cdot(\log n)^{4}}\leq n^{-10}\,.$

Thus, with high probability in $n$, vertices with more than $10^{8}\cdot(\log
n)^{4}$ edges do not contribute to $E^{\prime}$. Then we define the function
$f=\frac{\sum_{v\in V^{\prime\prime}}f_{v}(x)}{2\cdot 10^{8}\cdot(\log
n)^{4}}$ where $V^{\prime\prime}$ is the set of vertices with at most
$10^{8}\cdot(\log n)^{4}$ edges. Then, it is straightforward to verify that
$f$ is $(10^{8}\cdot(\log n)^{4})$-self bounding and get the concentration
bound stated in this corollary. ∎

We further leverage this technique to get the concentration bound for the set
of edges $E^{\prime}$ in Step 4 of Reduce. The proof immediately follows from
what we have discussed so far as it calls Filter with $k=10^{6}\log\log n$.

######  Corollary 8.6.

Let $E^{\prime}$ be the set of edges by end of Step 4 of Reduce. Then,
$|E^{\prime}|\leq 10^{7}\cdot n$ with the probability of at least $1-n^{-6}$.

###  8.2 Boosting to Linear Work with High Probability

We show that Connectivity$(G)$ can be implemented to take $O(m+n)$ work with
high probability.

######  Lemma 8.7.

For any graph $G$, w.p. $1-1/n$, Connectivity$(G)$ takes $O(m+n)$ work.

###### Proof.

Consider the proof of Lemma 7.17. Step 2 of Connectivity$(G)$ takes
$O(m)+\overline{O}(n)$ work because the edge set $E^{\prime}$ in Step 4 of
Reduce$(V,E,k)$ has
$\operatorname*{\mathbb{E}}[|E^{\prime}|]\leq\overline{O}(n)$. Using the
technique in §8.1, we can show that $|E^{\prime}|\leq O(n)$ w.p. $1-n^{-6}$,
giving $O(m+n)$ total work for Step 2 of Connectivity$(G)$ w.p. $1-n^{-6}$.

It remains to improve the total work of Step 5 of Connectivity$(G)$ to
$O(m+n)$ with high probability. Consider the
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ in each phase
$i\in[0,10\log\log n)$. In the proof of Lemma 7.17, we already showed that the
total work of Step 6 to Step 10 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ over all phases is at
most $O(m+n)$ w.p. $1-n^{-2}$.

Observe that Step 2 and Step 3 take $2(m+n)/(\log n)^{2}$ work w.p. $1-1/\log
n$. The idea is to run $\log n$ instances of Step 2 and Step 3 in parallel
independently, and halt the execution of an instance when the work of that
execution reaches $2(m+n/(\log n)^{2})$, so the total work would be
$2(m+n)/(\log n)^{2}\cdot\log n$ w.p. $1-n^{-9}$. To implement $\log n$
instances of parallel execution, note that $|E(H_{1})|,|E(H_{2})|\leq m/(\log
n)^{6}$ w.p. $1-n^{-8}$. At the end of Step 3 of Connectivity$(G)$, we
approximate compact the arrays of edges of $H_{1}$ and $H_{2}$ into arrays of
length at most $2m/(\log n)^{6}$ in $O(\log^{*}n)$ time and $O(m)$ work w.p.
$1-n^{-9}$. Since the edge of $H_{1},H_{2}$ are indexed, at the beginning of
each phase we can use $4m/(\log n)^{5}$ processors to make $\log n$ copies of
$H_{1},H_{2}$. Observe from the proof of Lemma 7.8, Lemma 7.13, and Lemma
5.10, that each atomic step of Step 2 and Step 3 in
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ uses
$O(|V(G^{\prime})|+|E(H_{1})|+|E(H_{2})|)\leq(m+n)/(\log n)^{5}$ processors
w.p. $1-1/(\log n)^{2}$, so we can use $(m+n)/(\log n)^{4}$ processors for the
$\log n$ independent parallel executions. The same observation implies that
Step 2 and Step 3 perform more than $2(m+n/(\log n)^{2})$ work only if the
algorithm wants to use more than $(m+n)/(\log n)^{5}$ processors in an atomic
step (e.g., when assigning block of processors to a vertex with level more
than $100\log\log n$), which can be detected and we halt the execution of that
instance. Finally, for all instances of Step 2 and Step 3 that finishes its
execution without halting, pick an arbitrary one to continue the execution of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ and discard the
others. As a result, Step 2 and Step 3 over all the $10\log\log n$ phases
takes $O(m+n)$ work w.p. $1-n^{-8}$.

To bound the total work of Step 4, we only need to show that Step 4 of
Remain$(G^{\prime},H_{1})$ takes $O(n)$ work w.p. $1-n^{-8}$ by the last
paragraph in the proof of Lemma 7.17. Since $|E_{\text{remain}}|\leq n/(\log
n)^{6}$ w.p. $1-n^{-9}$, we run $\log n$ instances of the algorithm in Theorem
2 in parallel and halt the execution of the instance if it reaches $n/(\log
n)^{5}$ using the technique described in the previous paragraph. As a result,
Step 4 of Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ takes
$O(n)$ work w.p. $1-n^{-8}$. The lemma follows from a union bound. ∎

Next, we show that our algorithm computes the connected components in desired
time with high probability using the implementation in the proof of Lemma 8.7.

######  Lemma 8.8.

For any graph $G$ with component-wise spectral gap $\lambda$, w.p. $1-1/n$,
Connectivity$(G)$ computes all the connected components of $G$ in
$O(\log(1/\lambda)+\log\log n)$ time.

###### Proof.

In the proofs of Lemma 7.21 and Lemma 8.7, we already showed that Step 1, Step
2, Step 3, Step 4, and Step 6 can be implemented to take $O(\log\log n)$ time
w.p. $1-2/n^{-2}$. It remains to prove for Step 5 of Connectivity$(G)$.

In the proof of Lemma 7.18, we showed that Step 2 and Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ take $O(\log b)$ time
w.p. $1-1/(\log n)^{2}$. In the proof of Lemma 8.7, we run $\log n$ parallel
instances of Step 2 and Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. So we can halt the
execution of an instance if it reaches $c\log n$ running time where $c>0$ is
an absolute constant such that Step 2 and Step 3 take at most $c\log b$ time.
Therefore, the statement in Lemma 7.18 holds w.p. $1-n^{-2}$.

In the proof of Lemma 7.19, we used the fact that w.p. $1-1/(\log n)^{8}$,
Step 3 of the algorithm
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ is a contraction
algorithm on $H_{1}$. One can detect whether this step is a contraction
algorithm on $H_{1}$ by checking whether all vertices in $V(H_{1})$ are either
roots or children of roots. In the proof of Lemma 8.7, we run $\log n$
parallel instances of Step 2 and Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$. So we can discard an
instance at the end of the execution if it is not a contraction algorithm on
$H_{1}$. Therefore, Step 3 is a contraction algorithm on $H_{1}$ w.p.
$1-n^{-9}$. In Remain$(G^{\prime},H_{1})$ in Step 4, its first $3$ steps take
$O(\log^{*}n)$ time w.p. $1-n^{-9}$. In the proof of Lemma 8.7, we run $\log
n$ instances of the algorithm in Theorem 2 in parallel. So we halt the
execution of the instance if it reaches $c(\log d+\log\log n)$ time where $c$
is an absolute constant, which happens w.p. at most $1/(\log n)^{9}$. As a
result, the statement in Lemma 7.19 holds w.p. $1-n^{-7}$.

In the proof of Lemma 7.20, we proved that in the last phase $i$, w.p.
$1-1/(\log n)^{4}$, all edges of $H_{1}$ are loops at the end of Step 3 of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$, which can be
detected using $|E(H_{1})|\leq m/(\log n)^{6}$ processors in $O(1)$ time w.p.
$1-n^{-8}$. In the proof of Lemma 8.7, we run $\log n$ parallel instances of
Step 2 and Step 3, so w.p. $1-n^{-9}$, at least one of the instance at the end
of its execution satisfies that all edges of $H_{1}$ are loops and we choose
this one to continue the execution of
Interweave$(G^{\prime},H_{1},H_{2},E_{\text{filter}},i)$ and discard the
others. Therefore, the statement in Lemma 7.20 holds w.p. $1-n^{-7}$.

Since Lemma 7.18, Lemma 7.19, and Lemma 7.20 hold w.p. $1-1/n$, the rest of
the proof is the same as the proof of Lemma 7.21. ∎

By Lemma 8.7 and Lemma 8.8, Theorem 1 follows immediately.

##  Appendix A Conditional Lower Bound

In this section, we show that our time bound is optimal when the input graph
has component-wise spectral gap at most $1/\operatorname{poly}(\log(n))$
conditioning on the widely believed 2-Cycle Conjecture (see below). The
approach is similar to that of [BDE+19], who gives an $\Omega(\log d)$
conditional lower bound, where $d\geq\operatorname{poly}(\log(n))$ is the
diameter.

######  Conjecture A.1 (2-Cycle Conjecture [RVW18, ASW19, ASS+18, BDE+19]).

Any MPC algorithm that uses $n^{1-\Omega(1)}$ space per processor requries
$\Omega(\log n)$ MPC rounds to distinguish between one cycle of size $n$ from
two cycles of size $n/2$ w.h.p.

For simplicity, we state the theorem in the MPC model so that our proof can be
based on the MPC model. The conditional lower bound easily holds in any PRAM
model with $O(m+n)$ total memory by a simple simulation [ASW19, ASS+18]: if
there exists a PRAM algorithm that distinguishes between one cycle from two
cycles in $o(\log n)$ time, then an MPC with $n^{1-\Omega(1)}$ space per
processor can simulate this PRAM algorithm with $O(1)$ overhead, which
violates the conjecture.

######  Theorem 4.

If the 2-Cycle Conjecture is true, then there exists a constant $c>20$ such
that any MPC algorithm with $n^{1-\Omega(1)}$ space per processor that w.h.p.
computes connected components of any given $n$-vertex graph with component-
wise spectral gap $\lambda^{\prime}$ requires
$\Omega(\log(1/\lambda^{\prime}))$ rounds, where
$\lambda^{\prime}\leq\log^{-c}n$ is a fixed parameter.

For the contradiction, we assume that there exists an MPC algorithm ALG with
$n^{1-\Omega(1)}$ space per processor that w.h.p. computes connected
components of any given $n$-vertex graph with component-wise spectral gap
$\lambda^{\prime}$ in $o(\log(1/\lambda^{\prime}))$ rounds, where
$\lambda^{\prime}$ is given in Theorem 4.

Given a graph $G$ which consists a cycle of size $n$ or two cycles of size
$n/2$. The algorithm proceeds in rounds. In each round, delete each edge of
$G$ w.p. $\lambda^{\prime 1/4}$ independently to get graph $G^{\prime}$.
Compute the connected components of $G^{\prime}$ by ALG. Contract each
connected components of $G^{\prime}$ to a single vertex in $G$ and add the
edges deleted in this round to $G$, completing this round. Repeat for $R$
rounds until the number of edges in $G$ is $n^{o(1)}$ such that $G$ can be
stored in one processor and solved where $R$ is a parameter to be tuned. We
need the following claim.

######  Lemma A.2.

The graph $G$ at the beginning of each round and subgraph $G^{\prime}$ during
each round is a collection of paths and cycles.

###### Proof.

The statement is trivially true at the beginning of the algorithm. By an
induction, assuming the graph $G$ at the beginning of each round is a
collection of paths and cycles. During this round, $G^{\prime}$ is a subgraph
of $G$ after edge deletions, which is still a collection of paths and cycles
(singleton vertex is considered as a path or a cycle of size $1$, where _size_
is defined as the number of vertices). After contracting connected components
of $G^{\prime}$, the resulting $G$ is also a collection of paths and cycles,
completing the induction. ∎

######  Lemma A.3.

Each round takes $o(\log(1/\lambda^{\prime}))$ rounds w.h.p.

###### Proof.

The edge deletion at the beginning of the round and the contraction at the end
of the round can be implemented in $O(1)$ MPC rounds (e.g., see [ASS+18]). It
remains to show that the graph $G^{\prime}$ ($G$ after edge deletions) has
spectral gap at least $\lambda^{\prime}$ w.h.p. at the beginning of each
round.222222If graph $G^{\prime}$ has component-wise spectral gap greater than
$\lambda^{\prime}$, the algorithm creates a _dummy_ component of spectral gap
$\lambda^{\prime}$ and adds it into $G^{\prime}$ such that $G^{\prime}$ has
component-wise spectral gap exactly $\lambda^{\prime}$ and thus ALG is
applicable on $G^{\prime}$. The dummy component has no edge with the original
$G^{\prime}$ so does not influence the computation of other components.
Moreover, the dummy component has at most $m$ edges (e.g. a path of fixed
length) and can be created and deleted at the end of this round in $O(1)$ MPC
rounds.

By Lemma A.2, $G^{\prime}$ is a collection of paths and cycles. In the
following, we show that w.h.p. the size of each path and cycle is at most
$\lambda^{\prime-1/3}$, then a union bound gives the result since there are at