###### Proof.

###### Proof.

.:

###### Near-Optimal Distributed Computation of Small Vertex Cuts

###### Abstract

We present near-optimal algorithms for detecting small vertex cuts in the
${\mathsf{CONGEST}}$ model of distributed computing. Despite extensive
research in this area, our understanding of the _vertex_ connectivity of a
graph is still incomplete, especially in the distributed setting. To this
date, all distributed algorithms for detecting cut vertices suffer from an
inherent dependency in the maximum degree of the graph, $\Delta$. Hence, in
particular, there is no truly sub-linear time algorithm for this problem, not
even for detecting a _single_ cut vertex. We take a new algorithmic approach
for vertex connectivity which allows us to bypass the existing $\Delta$
barrier.

As a warm-up to our approach, we show a simple
$\widetilde{O}(D)$-round111Throughout the paper, we use the notation
$\widetilde{O}$ to hide poly-logarithmic in $n$ terms. randomized algorithm
for computing all cut vertices in a $D$-diameter $n$-vertex graph. This
improves upon the $O(D+\Delta/\log n)$-round algorithm of [Pritchard and
Thurimella, ICALP 2008].

Our key technical contribution is an $\widetilde{O}(D)$-round randomized
algorithm for computing all cut _pairs_ in the graph, improving upon the
state-of-the-art $O(\Delta\cdot D)^{4}$-round algorithm by [Parter, DISC ’19].
Note that even for the considerably simpler setting of _edge_ cuts, currently
$\widetilde{O}(D)$-round algorithms are known _only_ for detecting pairs of
cut edges.

Our approach is based on employing the well-known linear graph sketching
technique [Ahn, Guha and McGregor, SODA 2012] along with the heavy-light tree
decomposition of [Sleator and Tarjan, STOC 1981]. Combining this with a
careful characterization of the survivable subgraphs, allows us to determine
the connectivity of $G\setminus\\{x,y\\}$ for every pair $x,y\in V$, using
$\widetilde{O}(D)$-rounds. We believe that the tools provided in this paper
are useful for omitting the $\Delta$-dependency even for larger cut values.

###### Contents

  1. 1 Introduction and Our Contribution
    1. 1.1 Our Approach, in a Nutshell
    2. 1.2 Preliminaries
  2. 2 Single Cut Vertices
  3. 3 Dependent Cut Pairs
    1. 3.1 Implementation Details for Section 3
  4. 4 Independent Cut Pairs
    1. 4.1 Computing $x$-Connectivity Trees
    2. 4.2 Component Classification Based on Sensitivity
    3. 4.3 $xy$-Connectivity Algorithms Under a Promise
      1. 4.3.1 Implementation Details for Section 4.3
    4. 4.4 Omitting the Promise
      1. 4.4.1 Light Pairs
      2. 4.4.2 Heavy Pairs
  5. 5 Conclusion

##  1 Introduction and Our Contribution

The vertex connectivity of the graph is a central concept in graph theory and
extensive attention has been paid to developing algorithms to compute it in
various computational models. Recent years have witnessed an enormous progress
in our understanding of vertex cuts, from a pure graph theoretic perspective
[PY21] to many algorithmic applications [NSY19, LNP+21, PY21, HLW21]. Despite
this exciting movement, our algorithmic toolkit for handling vertex cuts is
still somewhat limited. A large volume of the work, in the centralized
setting, has focused on fast algorithms for detecting minimum vertex cuts of
size at most $k$, for some small number $k$. Until recently, near-linear time
algorithms where known only for $k\leq 2$ [Tar72, HT73]. A sequence of recent
breakthrough results [CKL+22, LNP+21, SY22] provide almost-linear time
sequential algorithms for computing the vertex connectivity (even for large
connectivity values).

As we discuss soon, the situation is considerably worse in distributed
settings, where the problem is still fairly open already for $k=1$.
Throughout, we consider the ${\mathsf{CONGEST}}$ model [Pel00]. In this model,
each node holds a processor with a unique and arbitrary ID of $O(\log n)$
bits, and initially only knows the IDs of its neighbors in the graph. The
execution proceeds in synchronous rounds, where in each round, each node can
send a message of size $O(\log n)$ to each of its neighbors. The primary
complexity measure is the number of communication rounds. For $n$-vertex
$D$-diameter graphs, Pritchard and Thurimella [PT11] presented a randomized
algorithm for detecting a (single) cut vertex (a.k.a articulation point)
within $O(D+\Delta/\log n)$ ${\mathsf{CONGEST}}$ rounds, where $\Delta$ is the
maximum degree of the graph. The authors of [PT11] conclude their paper by
noting:

> [PT11] _It would be interesting to know if our distributed cut vertex
> algorithm could be synthesized with the cut vertex algorithm of[Thu97] to
> yield further improvement. Alternatively, a lower bound showing that no
> $O(D)$-time algorithm is possible for finding cut vertices would be very
> interesting._

No progress on the complexity of this problem has been done since then. For
small cut values $k$, Parter [Par19] employed the well-known fault-tolerant
sampling technique [WY13, KP21] for detecting $k$ vertex cuts in $(\Delta\cdot
D)^{\Theta(k)}$ deterministic rounds. Turning to approximation algorithms, for
$k=\Omega(\log n)$, Censor-Hillel, Ghaffari and Kuhn [CHGK14] provided a
$O(\log n)$ approximation for computing the _value_ of the vertex connectivity
of the graph within $\widetilde{O}(D+\sqrt{n})$ rounds The authors of [CHGK14]
also presented a lower bound of $\widetilde{\Omega}(D+\sqrt{n/k})$
$V$-${\mathsf{CONGEST}}$ rounds. In the $V$-${\mathsf{CONGEST}}$ model, each
_node_ (rather than an edge) is restricted to send only $O(\log n)$ bits, in
total, in every round. As shown in this paper, this lower bound does not hold
in the standard ${\mathsf{CONGEST}}$ model.

We follow the terminology from [PT11]: a _cut vertex_ is a vertex $x$ such
that $G\setminus\\{x\\}$ is not connected. A _cut pair_ is a pair of vertices
$x,y$ such that $G\setminus\\{x,y\\}$ is not connected. For brevity, we refer
to cut vertices and cut pairs as _small cuts_. Our main results in this paper
are near-optimal algorithms for detecting these small cuts, in the sense that
for every small cut, there is at least one vertex in the graph that learns it.
Our first contribution is in presenting a (perhaps surprisingly) simple
randomized algorithm222As usual, all presented randomized algorithms in this
paper have success guarantee of $1-1/n^{c}$, for any given constant $c>1$.
that can detect all cut vertices in the graph in $\widetilde{O}(D)$ rounds.
The edge-congestion333The edge congestion of a given algorithm is the worst-
case bound on the total number of messages exchanged through a given edge $e$
in the graph. of the algorithm is $\widetilde{O}(1)$ bits444We exploit this
bounded congestion for detecting cut pairs..

######  Theorem 1.1.

There is a randomized algorithm that w.h.p. identifies all single cut-vertices
in $G$ within $\widetilde{O}(D)$ rounds. The edge congestion is
$\widetilde{O}(1)$. In the output, each vertex $x\in V$ learns if it is a cut
vertex.

This settles the question raised in [PT11]. Our algorithm is based on the
well-known _graph-sketching_ technique of Ahn, Guha and McGregor [AGM12]. This
technique has admitted numerous applications in the context of connectivity
computation under various computational settings, e.g., [KKM13, KW14, GKKT15,
KKT15, MK18, GP16, DP17, DP21]. Yet, to the best of our knowledge, it has not
been employed before in the context of ${\mathsf{CONGEST}}$ algorithms for
minimum vertex-cut computation.

We then turn to consider the problem of detecting cut pairs. It has been noted
widely in the literature that there is a sharp qualitative difference between
a single failure and two failures. This one-to-two jump has been accomplished
by now for a wide variety of fault-tolerant settings, e.g., reachability
oracles [Cho16], distance oracles [DP09], distance preservers [Par15, GK17,
Par20] and vertex-cuts [HT73, BT89, BT96, GILP15]. While it is relatively easy
to extend our algorithm of Theorem 1.1 to detect cut pairs in
$\widetilde{O}(D^{2})$ rounds, providing a near-optimal complexity of
$\widetilde{O}(D)$ rounds turns out to be quite involved. Our key technical
contribution is:

######  Theorem 1.2.

There is a randomized algorithm that w.h.p. identifies all cut pairs in $G$
within $\widetilde{O}(D)$ rounds. For each cut pair $x,y$, either $x$ or $y$
learns that fact.

We observe that even for the simpler problem of edge-connectivity (see Remark
on the Edge Connectivity below), an $\widetilde{O}(D)$-round algorithm is
currently only known for edge cuts of size at most two [PT11, Dag20]. Hence,
we are now able to match the complexity of these two problems for small cut
values. Our algorithm is based on distinguishing between two structural cases
depending on the locations of the cut pair $x,y$ in a BFS tree of $G$. The
first case which we call _dependent_ handles the setting where the $x$ and $y$
have ancestry/descendant relations. The second _independent_ case assumes that
$x$ and $y$ are not dependent, i.e., $\operatorname{LCA}(x,y)\notin\\{x,y\\}$,
where $\operatorname{LCA}(x,y)$ is the lowest (or least) common ancestor of
$x$ and $y$ in the BFS tree. Each of these cases calls for a different
approach. For a more in-depth technical overview, see Section 1.1.

We believe that the tools provided in this paper could hopefully pave the way
towards detecting larger vertex cuts with no dependency in the maximum degree
$\Delta$ (as it is the case for the state-of-the-art algorithm in [Par19]).

_Remark on the Edge Connectivity._ It is widely known that in undirected
graphs, vertex connectivity and vertex cuts are significantly more complex
than edge connectivity and edge cuts, for which now the following result are
known: an $\widetilde{O}(m)$-time centralized exact algorithm [Kar99, GNT20,
GMW20] and an $\widetilde{O}(D+\sqrt{n})$ exact distributed algorithms
[DEMN21]. For constant values of edge connectivity a ${\rm poly}(D)$-round
algorithm is given in [Par19].

###  1.1 Our Approach, in a Nutshell

We provide the key ideas of our algorithms. Our end goal is to simulate a
connectivity algorithm in the graph $G\setminus\\{x,y\\}$ for _every_ pair of
vertices $x,y\in V$. Note that this is not trivial already for a single $x,y$
pair as the diameter of the subgraph555Here we mean the _strong_ diameter of
$G\setminus\\{x,y\\}$, i.e. the diameter of the graph induced by $G$ on
$V\setminus\\{x,y\\}$. Its _weak_ diameter, defined as the maximal distance
_in $G$_ between any $u,v\in V\setminus\\{x,y\\}$, remains at most $D$, which
we crucially exploit. $G\setminus\\{x,y\\}$ might be as large as
$\Omega(\Delta D)$, hence using on-shelf connectivity algorithms leads to a
round complexity of $O(\min\\{D+\sqrt{n},\Delta D\\})$. We bypass this
$\Delta$ dependency by using the edges incident to the vertices $x,y$ as
_shortcuts_. Then, to minimize the congestion imposed by running possibly
$n^{2}$ connectivity algorithms in parallel, we employ a preprocessing phase
in which we collect _graph-sketch_ information (explained next) at each vertex
$x$. This information allows each vertex $x$ to pinpoint a bounded number of
cut-mate suspects. In addition, it allows $x$, in certain cases, to locally
simulate connectivity queries without using further communication.

Throughout, let $T$ be a BFS tree rooted at some source $s$, and denote the
$T$-paths by $\pi(\cdot,\cdot)$. We start by employing the well-known _heavy-
light tree decomposition_ technique by Sleator and Tarjan [ST83]. This
classifies the edges of $T$ into light and heavy edges. The useful properties
are that each vertex $v$ has $O(\log n)$ light edges on its tree path
$\pi(s,v)$, and is the parent of _one_ heavy edge, connecting $v$ to its
unique heavy child. It is easy to compute this decomposition on $T$ in
$\widetilde{O}(D)$ rounds. For a vertex $x$, let $T_{x}$ be the subtree of $T$
rooted at $x$.

##### Basic Tools: Graph Sketches and the Borůvka Algorithm.

A _graph sketch_ of a vertex $v$ is a randomized string of $\widetilde{O}(1)$
bits that compresses $v$’s edges [AGM12]. The linearity of these sketches
allows one to infer, given the sketches of subset of vertices $S$, an outgoing
cut edge from $S$ to $V\setminus S$ (if exists) with constant probability. A
common approach for deducing the graph connectivity merely from the sketches
of the vertices is based on the well-known Borůvka algorithm [NMN01]. This
algorithm works in $O(\log n)$ phases, where in each phase, from each growable
component an outgoing edge is selected. All these outgoing edges are added to
the forest, while ignoring cycles. Each such phase reduces the number of
growable components by constant factor, thus within $O(\log n)$ phases a
maximal spanning forest666A maximal spanning forest is defined as the union of
spanning trees for all connected components. is computed. Since this algorithm
only requires the computation of outgoing edges it can be simulated using
$O(\log n)$ independent sketches for each of the vertices. In our algorithms,
we aggregate graph sketches over the BFS tree $T$ which allows each vertex $x$
to locally simulate Borůvka in the graph $G\setminus\\{x\\}$. This is
illustrated in our algorithm for detecting a single cut vertex, described
next.

##### Warm Up: Detecting Single Cut Vertices.

Our algorithm starts by letting each vertex $v$ locally compute its individual
$\mathsf{sketch}_{G}(v)$. Then, by aggregating the sketches (using their
linearity) from the leaf vertices to the root $s$ over the BFS tree $T$, each
vertex $v$ learns its subtree-sketch $\mathsf{sketch}_{G}(V(T_{v}))$. Once
this is completed, it is easy to let each vertex $x\in V$ learn the $G$-sketch
information of all the connected components in $T\setminus\\{x\\}$. We then
show that $x$ can locally modify these $G$-sketches into
$(G\setminus\\{x\\})$-sketches. At this point, the vertex $x$ can locally
apply the Borůvka algorithm in $G\setminus\\{x\\}$ and deduce if
$G\setminus\\{x\\}$ is connected.

We now turn to consider the considerably more challenging task of detecting
cut pairs. We classify these pairs into dependent and independent.

##### Detecting Dependent Cut Pairs.

Our approach for the dependent case is based on designing algorithms $\\{{\cal
A}_{y}\\}_{y\in V}$, where ${\cal A}_{y}$ detects all $xy$ cut pairs of the
form777This is a critical point where only $x$ learns if $y\in\pi(s,x)$ is its
cut-mate (by running Alg. ${\cal A}_{y}$), but $y$ might not learn its
descendant cut-mates, such as $x$. $x\in V(T_{y})$. We show that each such an
algorithm ${\cal A}_{y}$ can be designed in a way that sends a total of
$\widetilde{O}(1)$ messages only along edges incident to $V(T_{y})$, and runs
in $\widetilde{O}(D)$ rounds. The standard random delay technique allows us
then to schedule the execution of all $n$ algorithms $\\{{\cal A}_{y}\\}_{y\in
V}$ within $\widetilde{O}(D)$ rounds. At a high level, each algorithm ${\cal
A}_{y}$ is based on employing the single cut vertex detection algorithm in the
graph $G\setminus\\{y\\}$. Our challenge is then twofold: first, the diameter
of the graph $G\setminus\\{y\\}$ might be as large as $\Omega(\Delta D)$, and
second, communication is restricted to use only edges incident to $V(T_{y})$.
We overcome these challenges by using $y$ as a coordinator, providing global
computation services and communication shortcuts that essentially enables
efficient simulation (in both dilation and congestion) of the algorithm for
detecting single cut vertices in $G\setminus\\{y\\}$.

##### Detecting Independent Cut Pairs.

The most technically involved case is where $x,y$ are independent, namely, _do
not_ have ancestry relations in $T$. A-priori, the number of such potential
cut-mates $y$ for a given vertex $x$ might be even linear in $n$. To filter
out irrelevant options, the algorithm starts by computing at each vertex $x$ a
tree $\widehat{T}_{x}$ that encodes the connectivity between $s$ and the
vertices in $V_{x}=V(T_{x})\setminus\\{x\\}$ in the graph $G\setminus\\{x\\}$.
Let $\mathcal{C}_{x}$ denote the collection of maximal connected components in
the graph $G[V_{x}]$. The tree $\widehat{T}_{x}$ is the union of paths of the
form $\pi(s,u_{C})\circ(u_{C},v_{C})$ for every component
$C\in\mathcal{C}_{x}$, where $v_{C}$ is some representative vertex in $C$, and
$u_{C}$ is outside the subtree $T_{x}$. It is then easy to observe that in
case $\hat{T}_{x}$ is non-empty, all independent cut-mates $y$ must appear on
some path $\pi(s,u_{C})$ for $C\in\mathcal{C}_{x}$. For a given suspect $y$,
we call the $\mathcal{C}_{x}$-components $C$ for which $y\in\pi(s,u_{C})$,
$y$-_sensitive_. Our argument has the following structure.

Multiple $xy$-Connectivity Algorithms, Under a Promise. For a fixed $xy$ pair,
we design an algorithm $\mathcal{A}^{P}_{x,y}$ that determines the
connectivity in $G\setminus\\{x,y\\}$ _given_ an $x$-$y$ path $\Pi_{x,y}$ (on
which $x,y$ can exchange messages). The algorithm $\mathcal{A}^{P}_{x,y}$ has
the special property that it sends messages either along $\Pi_{x,y}$, or along
edges incident to a restricted subset of vertices in $T_{x},T_{y}$, defined as
follows. Let $\mathsf{LDS}(x,y)\subset V(T_{x})$ be the set of all vertices
which are descendants of the _light_ children of $x$, and belong to a
$y$-sensitive component in $\mathcal{C}_{x}$. The set $\mathsf{LDS}(y,x)$ is
defined in an analogous manner. $\mathcal{A}^{P}_{x,y}$ is then guaranteed to
send $\widetilde{O}(1)$ messages only along the edges of $\Pi_{x,y}$ and the
edges incident to $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. This restriction
is crucial in order to run multiple $\mathcal{A}^{P}_{x,y}$ algorithms, for
distinct $xy$ pairs, in parallel. Using the properties of the heavy-light
decomposition and our sensitivity definition, one can show that each vertex
$w\in V$ belongs to the $\mathsf{LDS}(x,y)$ sets of at most $\widetilde{O}(D)$
pairs $xy$. The main challenge is in bounding the overlap between the
$\Pi_{x,y}$ paths across different $xy$ pairs. We show that given a subset
$Q\in V\times V$, the collection of $\\{\mathcal{A}^{P}_{x,y}\mid(x,y)\in
Q\\}$ algorithms can be scheduled in parallel in $\widetilde{O}(D)$ rounds
using the random delay approach [LMR94, Gha15], given that following promise
holds for $Q$:

> [Promise:] _There is a path collection
> $\mathcal{P}_{Q}=\\{\Pi_{x,y}\mid(x,y)\in Q\\}$ such that each path has
> length $O(D)$, and each edge appears on $\widetilde{O}(D)$ paths in
> $\mathcal{P}_{Q}$. _

On a high level, each algorithm $\mathcal{A}^{P}_{x,y}$ works by letting $x$
and $y$ jointly simulate the Borůvka algorithm in $G\setminus\\{x,y\\}$. The
main challenge is that the communication is restricted to the edges incident
to $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$, despite the fact that one should
also take into account the remaining vertices in $T_{x},T_{y}$, e.g.,
descendants of the _heavy_ children of $x,y$. In each Borůvka phase, we
maintain the invariant that $x,y$ jointly hold the sketches of connected
subsets (called _parts_) in $G\setminus\\{x,y\\}$, where we split the
responsibility between $x,y$ in a careful manner. We mainly distinguish
between parts that contain a heavy child of $x,y$ and the remaining _light_
parts that are contained in $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. The
merges of the light parts are implemented by using communication between
vertices in $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. The merges concerning
the heavy parts are implemented by using the direct communication over the
$\Pi_{x,y}$ path. Each such Borůvka phase is implemented in $\widetilde{O}(D)$
rounds. At the end of the simulation, $x,y$ both learn whether
$G\setminus\\{x,y\\}$ is connected.

Omitting the Promise by Classifying to Light and Heavy Pairs. While the
promise clearly holds for $\widetilde{O}(D)$ pairs, it does not hold for all
$\Omega(n^{2})$ pairs, in general. Our approach is based on classifying the
independent $xy$ pairs into two classes: _light_ and _heavy_. This
classification is based on the trees $\widehat{T}_{x},\widehat{T}_{y}$, as
well as on the heavy-light decomposition of $T$. Informally, for a light pair
$xy$, one can define a $\Pi_{x,y}$ path that intersects a light subtree of
either $x$ or $y$. These paths can be shown to have a bounded overlap, hence
satisfying the promise. Handling the heavy pairs is more involved. Here we
take a mixed approach. We define a special subset of the heavy pairs for which
the promise can be satisfied (called _mutual pairs_). This subset is chosen
carefully to guarantee the following, perhaps surprising, property: the
remaining (non-mutual) heavy pairs $x,y$ can be decided locally, at either $x$
or $y$. Our key observation is that for a $xy$ heavy pair, the graph
$G\setminus\\{x,y\\}$ is connected iff one of the heavy children of $x,y$ is
connected to $s$ in $G\setminus\\{x,y\\}$. Hence, it is mainly essential for
$x,y$ to collect a sketch information on the components of these heavy
children in $\mathcal{C}_{x},\mathcal{C}_{y}$.

###  1.2 Preliminaries

Throughout the paper, fix a connected $n$-vertex graph $G=(V,E)$, and a BFS
tree $T$ for $G$ rooted at an arbitrary source $s\in V$. We denote the unique
tree path from $u$ to $v$ by $\pi(u,v,T)$. When the tree $T$ is clear from
context, we may omit it and write $\pi(u,v)$. We use the $\circ$ operator for
path concatenation. An (undirected) edge between vertices $u$,$v$ is denoted
by $(u,v)$.

##### Heavy-Light Tree Decomposition.

We now present our heavy-light terminology, the notion of _compressed paths_ ,
and their distributed computation.

For a non-leaf vertex $v\in V(T)$, its _heavy child_ , denoted $v_{h}$, is the
(unique) child $v^{\prime}$ of $v$ maximizing888Ties are broken arbitrarily
and consistently. the number of vertices in its subtree $T_{v^{\prime}}$. Any
other child of $v$ is a _light child_. A vertex is _heavy_ if it is a heavy
child, and _light_ otherwise (so the root $s$ is light). A tree edge is
_heavy_ if it connects a vertex to its heavy child, and _light_ otherwise. If
$(u,u^{\prime})$ is a heavy (resp., light) edge in the path $\pi(s,v)$, then
$u$ is a _heavy ancestor_ (resp., _light ancestor_) of $v$, and $v$ is a
_heavy descendant_ (resp, _light descendant_) of $u$. (Note that in our
terminology, a ‘heavy ancestor’ need not be a heavy vertex itself, and
similarly for all combinations of heavy/light and ancestor/descendant). We
denote by $\mathsf{LA}(v)$ (resp., $\mathsf{LD}(v)$) the set of $v$’s light
ancestors (resp., descendants). It is easy to show that $\pi(s,v)$ contains
$O(\log n)$ _light_ vertices and edges, hence also $|\mathsf{LA}(v)|=O(\log
n)$

######  Definition 1.1 (Compressed paths).

Let $v\in V(T)$. Let $L=[s=v_{0},v_{1},\dots,v_{k}]$ be the ordered list of
the light vertices on the root-to-$v$ path $\pi(s,v,T)$. The _compressed path_
of $v$ with respect to $T$, denoted $\pi^{*}(s,v,T)$ consists of the list $L$,
along with a table mapping each $v_{i}$ to the number of heavy vertices
appearing between $v_{i}$ and $v_{i+1}$ in $\pi(s,v,T)$ (where we define
$v_{k+1}=v$). Note that the compressed path $\pi^{*}(s,v,T)$ has bit-length
$O(\log^{2}n)$.

Observe that compressed paths can be used as _ancestry labels_ in $T$: given
$\pi^{*}(s,u,T)$ and $\pi^{*}(s,v,T)$, one can check whether $\pi(s,u,T)$ is a
prefix of $\pi(s,v,T)$, and hence determine whether $u$ is an ancestor of $v$
in $T$.

######  Lemma 1.3.

For every tree $T$, there is an $\widetilde{O}(D(T))$-rounds
$\widetilde{O}(1)$-congestion algorithm letting each vertex $v$ of $T$ learn
its heavy/light classification and its compressed path $\pi^{*}(s,v,T)$.

###### Proof.

First, each vertex $v$ learns its subtree size $|V(T_{v})|$ by bottom-up
aggregation on $T$. By passing these sizes to the parents, within another
round each vertex can classify its children as either heavy or light. Within
one more round, each vertex is informed of its classification by its parent.
Computing the compressed paths can now be executed in a top-down fashion, as a
vertex can deduce its own compressed path from the compressed path of its
parent and its own heavy/light classification. ∎

##### Graph Sketches.

We give a formal but brief definition of graph sketches. We follow [DP21], and
refer the reader to Section 3.2.1 therein for a detailed presentation of the
subject. Throughout, let $\oplus$ denote the bitwise-XOR operator. The first
required ingredients are randomized _unique edge identifiers_ :

######  Lemma 1.4 ([DP21, Lemma 3.8], [GP16, Lemma 2.4]).

Using a random seed $\mathcal{S}_{\mathsf{id}}$ of $O(\log^{2}n)$ random bits,
one can compute a collection of $M=\binom{n}{2}$ $O(\log n)$-bit identifiers
for the pairs in $\binom{V}{2}$, denoted
$\mathcal{I}=\\{\mathsf{uid}(e_{1}),\ldots,\mathsf{uid}(e_{M})\\}$, with the
following property: For any nonempty subset $E^{\prime}\subseteq E$ with
$|E^{\prime}|\neq 1$, $\Pr[\oplus_{e\in
E^{\prime}}\mathsf{uid}(e)\in\mathcal{I}]\leq 1/n^{10}$. Furthermore, for any
$e=(u,v)$, the identifier $\mathsf{uid}(e)$ can be computed from
$\mathsf{id}(u)$, $\mathsf{id}(v)$ and the random seed
$\mathcal{S}_{\mathsf{id}}$.

Next, we define the notion of _extended edge identifiers_ , formed by
augmenting $\mathsf{uid}(e)$ with the IDs and $T$-ancestry labels of the
endpoints based on compressed paths, namely
$\mathsf{anc}_{T}(v)=\pi^{*}(s,v,T)$. Formally, an edge $e=(u,v)$ we have

$\displaystyle\mathsf{eid}_{T}(e)=[\mathsf{uid}(e),\mathsf{id}(u),\mathsf{id}(v),\mathsf{anc}_{T}(u),\mathsf{anc}_{T}(v)]~{}.$
(1)

We are ready to define the sketches. We now follow [DP16, DP17, DP21] and use
pairwise independent hash functions for this purpose. Choose $L=c\log n$
pairwise independent hash functions $h_{1},\ldots,h_{L}:\\{0,1\\}^{\Theta(\log
n)}\to\\{0,\ldots,2^{\log M}-1\\}$, and for each $i\in[1,L]$ and $j\in[0,\log
M]$ define the edge set $E_{i,j}=\\{e\in E\mid h_{i}(e)\in[0,2^{\log
M-j})\\}$. Each $h_{i}$ can be defined by a random seed of logarithmic length
[Vad12]. Thus, a random seed $\mathcal{S}_{h}$ of length $O(L\log n)$ can be
used to determine the collection of all $L$ hash functions. For each vertex
$v$ and indices $i,j$, let $E_{i,j}(v)$ be the edges incident to $v$ in
$E_{i,j}$. The $i^{th}$ _basic sketch unit_ of a vertex $v$ is then given by:

$\displaystyle\mathsf{sketch}_{G,i}(v)=\big{[}\bigoplus_{e\in
E_{i,0}(v)}\mathsf{eid}_{T}(e),\ldots,\bigoplus_{e\in E_{i,\log
M}(v)}\mathsf{eid}_{T}(e)\big{]}.$

We extend this definition to vertex subsets by XORing, i.e., for $S\subseteq
V$, $\mathsf{sketch}_{G,i}(S)=\oplus_{v\in S}\mathsf{sketch}_{G,i}(v).$ The
_sketch_ of a vertex $v$ is formed by concatenating its basic sketch units:

$\displaystyle\mathsf{sketch}_{G}(v)=[\mathsf{sketch}_{G,1}(v),\mathsf{sketch}_{G,2}(v),\ldots\mathsf{sketch}_{G,L}(v)]~{}.$

Again, we extend this definition to $S\subseteq V$ by
$\mathsf{sketch}_{G}(S)=\bigoplus_{v\in S}\mathsf{sketch}_{G}(v)$.

######  Observation 1.5.

$\mathsf{sketch}_{G}(V)=0$, where $0$ denote the all-$0$s string of
appropriate length.

###### Proof.

For each $i,j$, the $j^{th}$ entry of $\mathsf{sketch}_{G,i}(V)$ contains
$\bigoplus_{v\in V}\bigoplus_{e\in E_{i,j}(v)}\mathsf{eid}(e)~{}.$ Each term
in this XOR appears precisely twice: $\mathsf{eid}(e)$ of $e=(u,w)\in E_{i,j}$
appears once for $u$ and once for $w$. Hence, this entry equals $0$, and the
result follows. ∎

The main use of graph sketches is in finding outgoing edges:

######  Lemma 1.6 ([DP21, Lemma 3.11]).

For any subset $S$, given a basic sketch unit $\mathsf{sketch}_{G,i}(S)$ and
the seed $\mathcal{S}_{\mathsf{id}}$ one can compute, with constant
probability999Over the choice of the random seeds $\mathcal{S}_{\mathsf{id}}$
and $\mathcal{S}_{h}$. $\mathsf{eid}_{T}(e)$ for an outgoing edge $e$ from $S$
in $G$, if such exists.

The following lemma lets us “cancel” edges from the sketches:

######  Lemma 1.7.

Let $S\subseteq V$, and let $E^{\prime}\subseteq E$ be a set of outgoing edges
from $S$. Then, given $\mathsf{sketch}_{G}(S)$, the random seeds
$\mathcal{S}_{h},\mathcal{S}_{\mathsf{id}}$, and the extended identifiers
$\mathsf{eid}_{T}(e)$ of all $e\in E^{\prime}$, one can compute a
_cancellation-sketch_ $\mathsf{csketch}(E^{\prime})$ for $E^{\prime}$ such
that $\mathsf{sketch}_{G\setminus
E^{\prime}}(S)=\mathsf{sketch}_{G}(S)\oplus\mathsf{csketch}(E^{\prime})$.

###### Proof.

Let $Out(S)$ be the set of outgoing edges from $S$ in $G$, and
$Out_{i,j}(S)=Out(S)\cap E_{i,j}$. Observe that for each
$i\in\\{1,\dots,L\\}$:

$\displaystyle\mathsf{sketch}_{G,i}(S)$ $\displaystyle=[\bigoplus_{v\in
S}\bigoplus_{e\in E_{i,0}(v)}\mathsf{eid}_{T}(e),\ldots,\bigoplus_{v\in
S}\bigoplus_{e\in E_{i,\log M}(v)}\mathsf{eid}_{T}(e)]$
$\displaystyle=[\bigoplus_{e\in
Out_{i,0}(S)}\mathsf{eid}_{T}(e),\ldots,\bigoplus_{e\in Out_{i,\log
M}(S)}\mathsf{eid}_{T}(e)]$

where the last equality is true as each edge $e$ with both endpoints inside
$S$ appears either $0$ or $2$ times in each XOR. Now let $Out^{\prime}(S)$ and
$Out^{\prime}_{i,j}(S)$ be defined exactly as $Out(S)$ and $Out_{i,j}(S)$, but
with respect to $G\setminus E^{\prime}$ instead of $G$. Then as $Out(S)$ is
the disjoint union of $Out^{\prime}(S)$ and $E^{\prime}$, we obtain

$\displaystyle\mathsf{sketch}_{G,i}(S)\oplus\mathsf{sketch}_{G\setminus
E^{\prime},i}(S)=[\bigoplus_{e\in E^{\prime}\cap
E_{i,0}}\mathsf{eid}_{T}(e),\ldots,\bigoplus_{e\in E^{\prime}\cap E_{i,\log
M}}\mathsf{eid}_{T}(e)].$

The right-hand side of the above equation can be computed from the given
extended IDs of $E^{\prime}$ and the random seeds
$\mathcal{S}_{h},\mathcal{S}_{\mathsf{id}}$, and we denote it by
$\mathsf{csketch}_{i}(E^{\prime})$. Note that by the above equation, we have
that $\mathsf{sketch}_{G\setminus
E^{\prime},i}(S)=\mathsf{sketch}_{G,i}(S)\oplus\mathsf{csketch}_{i}(E^{\prime})$.
Therefore, we can define the cancellation-sketch as the concatenation
$\mathsf{csketch}(E^{\prime})=[\mathsf{csketch}_{1}(E^{\prime}),\ldots,\mathsf{csketch}_{L}(E^{\prime})]$,
and the lemma follows. ∎

##### Distributed Scheduling.

The congestion of an algorithm ${\cal A}$ is defined by the worst-case upper
bound on the number of messages exchanged through a given graph edge when
simulating ${\cal A}$. Throughout, we make extensive use of the following
random delay approach of [LMR94], adapted to the ${\mathsf{CONGEST}}$ model.

######  Theorem 1.8 ([Gha15, Theorem 1.3]).

Let $G$ be a graph and let ${\cal A}_{1},\ldots,{\cal A}_{m}$ be $m$
distributed algorithms, each algorithm takes at most d rounds, and where for
each edge of $G$, at most c messages need to go through it, in total _over
all_ these algorithms. Then, there is a randomized distributed algorithm that
w.h.p. runs all the algorithms in $\widetilde{O}(\mbox{\tt c}+\mbox{\tt d})$
rounds.

##  2 Single Cut Vertices

In this section we describe the distributed algorithm for detecting single
vertex cuts of Theorem 1.1. This serves both as a warm-up to our approach in
the subsequent sections devoted to cut pairs detection, as well as for a
detailed presentation of basic tools used in these next sections. We assume
each vertex $v$ is equipped with its heavy/light classification in $T$ (recall
that $T$ is a BFS tree of $G$ rooted at $s$), and with its ancestry label
which is its compressed path, $\mathsf{anc}_{T}(v)=\pi^{*}(s,v,T)$. This can
be achieved in $\widetilde{O}(D)$ rounds by Lemma 1.3.

##### Step 1: Computing Subtree Sketches.

The source $s$ samples the random seeds
$\mathcal{S}_{\mathsf{id}},\mathcal{S}_{h}$ of $\widetilde{O}(1)$ bits, and
broadcasts them to all vertices. Using Lemma 1.4, each vertex $v$ can then
locally compute the $\mathsf{uid}(e)$ for each edge $e$ incident to $v$. By
letting all neighbors in $G$ exchange their $\mathsf{anc}_{T}$-labels, each
$\mathsf{uid}(e)$ can be concatenated with the required information to create
$\mathsf{eid}(e)$. This provides each vertex $v$ with all the information
needed to lcoally compute $\mathsf{sketch}_{G}(v)$. By XOR-aggregation of the
individual sketches from the leaves of $T$ upwards, each vertex $v$ obtains
its subtree sketch, given by $\mathsf{sketch}_{G}(V(T_{v}))=\oplus_{u\in
T_{v}}\mathsf{sketch}_{G}(v)$. Next, each vertex passes its subtree sketch to
its parent, so that each vertex now holds the subtree sketch for each of its
children. Finally, the source $s$ also broadcasts its subtree sketch, which is
$\mathsf{sketch}_{G}(V)$, to all the other vertices. The
$\widetilde{O}(D)$-rounds and $\widetilde{O}(1)$-congestion bounds follow as
we have performed a constant number of broadcasts and aggregations of
$\widetilde{O}(1)$-bit strings over $T$, which has diameter $O(D)$ as a BFS
tree of $G$ [Pel00].

##### Step 2: Local Borůvka Simulation.

This step is locally applied at every vertex $x$, and requires no additional
communication rounds. We show that given the information of Step 1, $x$ can
locally simulate the Borůvka’s algorithm [NMN01] in the graph
$G\setminus\\{x\\}$, and thus determine if $G\setminus\\{x\\}$ is connected.
Let $x_{1},\ldots,x_{k}$ be the children of $x$ in $T$. We assume that $x\neq
s$; the case $x=s$ is easier and requires only slight modifications. The
connected components in $T\setminus\\{x\\}$ are denoted by
$\mathcal{P}_{x}=\\{V(T_{x_{j}})\mid j=1,\dots,k\\}\cup\\{V\setminus
V(T_{x})\\}.$ By Step 1, $x$ holds the $G$-sketch of each component in
$\mathcal{P}_{x}$: It has explicitly received
$\mathsf{sketch}_{G}(V(T_{x_{j}}))$ from each child $x_{j}$. The sketch of the
remaining component can be locally inferred as $\mathsf{sketch}_{G}(V\setminus
V(T_{x}))=\mathsf{sketch}_{G}(V)\oplus\mathsf{sketch}_{G}(V(T_{x}))$. For a
neighbor $u$ of $v$, $x$ can use $\mathsf{anc}_{T}(u)$ (found in
$\mathsf{eid}_{T}((x,u))$) to determine component containing $u$ in
$\mathcal{P}_{x}$. Therefore, using Lemma 1.7, $x$ can cancel its incident
edges to obtain $\mathsf{sketch}_{G\setminus\\{x\\}}(P)$ for every
$P\in\mathcal{P}_{x}$.

We are now ready to describe the Borůvka execution, which is very similar to
the (centralized) decoding algorithm of [DP21]. The algorithm consists of
$O(\log n)$ phases. Each phase $i$ is given as input a partitioning
$\mathcal{P}_{x,i}=\\{P_{i,1},\ldots,P_{i,k_{i}}\\}$ of $V\setminus\\{x\\}$
into connected _parts_ , along with their sketch information
$\mathsf{sketch}_{G\setminus\\{x\\}}(P_{i,j})$. The initial partitioning given
to the first phase is $\mathcal{P}_{x,0}=\mathcal{P}_{x}$. The output of the
phase is a coarser partitioning $\mathcal{P}_{x,i+1}$ along with the
$(G\setminus\\{x\\})$-sketch information of the new parts. A part
$P_{i,j}\in\mathcal{P}_{x,i}$ is said to be _growable_ if it has at least one
outgoing edge to a vertex in $V\setminus(P_{i,j}\cup\\{x\\})$. To obtain
outgoings edges from the growable parts in $\mathcal{P}_{x,i}$, the algorithm
uses the $i^{th}$ basic-unit sketch
$\mathsf{sketch}_{G\setminus\\{x\\},i}(P_{i,j})$ of each
$P_{i,j}\in\mathcal{P}_{x,i}$. By Lemma 1.6, from every growable part
$P_{i,j}\in\mathcal{P}_{x,i}$, we get $\mathsf{eid}_{T}(e)$ for one outgoing
edge $e=(u,v)$ with constant probability. To find the part $P_{i,j^{\prime}}$
containing the other endpoint of $e$ (to be merged with $P_{i,j}$), we use the
$T$-ancestry labels found in $\mathsf{eid}_{T}(e)$. Say this endpoint is $v$.
We determine the component of $v$ in $T\setminus\\{x\\}$, i.e. the part
$P_{0,q}$ containing $v$ in $\mathcal{P}_{x,0}$, by querying the ancestry
relation between $v$ and the children of $x$ using their
$\mathsf{anc}_{T}$-labels. Then $v$ belongs to the unique component
$P_{i,j^{\prime}}\in\mathcal{P}_{x,i}$ containing $P_{0,q}$. The sketch
information for the next phase $i+1$ is given by XORing over the sketches of
the parts in $\mathcal{P}_{x,i}$ that got merged into a single component in
$\mathcal{P}_{x,i+1}$.

Note that it is important to use fresh randomness (i.e. independent sketch
information) in each of the Borůvka phases [AGM12, KKM13, DP16]. Since each
growable component gets merged with constant probability, the expected number
of growable components is reduced by a constant factor in each phase. Thus
after $O(\log n)$ phases, the expected number of growable components is at
most $1/n^{5}$, and by Markov’s inequality we conclude that w.h.p. there are
no growable components. Namely, at this point, the partition is just the
connected components of $G\setminus\\{x\\}$ (as a part is not growable iff it
has no outgoing edges in $G\setminus\\{x\\}$, i.e. it is a connected component
of this graph). We therefore determine that $G\setminus\\{x\\}$ is
disconnected (i.e. that $x$ is a cut vertex) iff this partition has more than
one part.

This concludes the proof of Theorem 1.1. Finally, we note that by tracking the
merges throughout the Borůvka simulation, $x$ can also find a subset
$\widetilde{E}$ of the outgoing edges received throughout the simulation such
$(T\setminus\\{x\\})\cup\widetilde{E}$ is a maximal spanning forest of
$G\setminus\\{x\\}$. This becomes useful in next sections.

##  3 Dependent Cut Pairs

In this section we present an $\widetilde{O}(D)$-round algorithm for detecting
_dependent_ cut pairs in $G$, i.e. pairs $xy$ where $x$ is a descendant of $y$
in the BFS tree $T$ rooted at $s$. Recall that our approach is based on
scheduling the execution of algorithms $\\{{\cal A}_{y}\\}_{y\in V}$, where
${\cal A}_{y}$ detects all cut pairs $xy$ such that $x\in T_{y}$ (see overview
in Section 1.1). By employing the single cut vertices detection algorithm of
Section 2 as a common preprocessing phase prior to the execution of the
$\\{{\cal A}_{y}\\}_{y\in V}$ algorithms, we may assume that there are no
single cut vertices in $G$. Furthermore, by carefully examining the properties
of this algorithm, we may assume that every $v\in V$ holds the following
preprocessing information:

  * •

The random seeds $\mathcal{S}_{\mathsf{id}},\mathcal{S}_{h}$.

  * •

$\mathsf{eid}_{T}(e)$ for every edge $e$ incident to $v$.

  * •

$|V(T_{v})|$ and $|V(T_{v^{\prime}})|$ for every $T$-child $v^{\prime}$ of
$v$.

  * •

$\mathsf{sketch}_{G}(v)$, $\mathsf{sketch}_{G}(V)$,
$\mathsf{sketch}_{G}(V(T_{v}))$ and $\mathsf{sketch}_{G}(V(T_{v^{\prime}}))$
for every $T$-child $v^{\prime}$ of $v$.

  * •

An edge set $\widetilde{E}(v)\subseteq E\setminus E(T)$ such that
$\widetilde{T}(v)=(T\setminus\\{v\\})\cup\widetilde{E}(v)$ is a spanning tree
of $G\setminus\\{v\\}$. For each $e\in\widetilde{E}(v)$, its extended
identifier $\mathsf{eid}_{T}(e)$ is known.

######  Lemma 3.1.

Assuming all vertices know their preprocessing information, there is an
$\widetilde{O}(D)$-rounds, $\widetilde{O}(1)$-congestion algorithm ${\cal
A}_{y}$ that detects all cut pairs $xy$ where $x\in V(T_{y})$. The algorithm
${\cal A}_{y}$ sends messages only on edges incident to $V(T_{y})$.

We next describe the algorithm ${\cal A}_{y}$. Throughout, let
$\widetilde{E}=\widetilde{E}(y)$, $\widetilde{T}=\widetilde{T}(y)$,
$\widetilde{G}=G\setminus\\{y\\}$, and denote the $T$-children of $y$ by
$y_{1},\dots,y_{k}$.

##### Step 0: Local Computation of Component Tree for $\widetilde{T}$ in $y$.

This preliminary step is executed by local computation in $y$. It constructs
the _component tree_ $\widetilde{CT}$, which is obtained from $\widetilde{T}$
by contracting each connected component of
$\widetilde{T}\setminus\widetilde{E}$ into a single node. Note that
$\widetilde{T}\setminus\widetilde{E}=T\setminus\\{y\\}$, namely the nodes in
$\widetilde{CT}$ correspond to connected components of $T\setminus\\{y\\}$.
More concretely, for every $i=1,\dots,k$ the component $C_{i}=V(T_{y_{i}})$ is
a node of $\widetilde{CT}$, and (unless $y=s$) there is another node for the
component $C_{0}=V\setminus V(T_{y})$. Each edge $(C_{i},C_{j})$ in
$\widetilde{CT}$ corresponds to the unique $\widetilde{E}$-edge incident to
both $C_{i}$ and $C_{j}$. Observe that the extended edge identifiers which are
known to $y$ by the preprocessing contain the $T$-ancestry labels of all the
endpoints of the edges in $\widetilde{E}$, as well as those of the $y_{i}$’s.
Using these ancestry labels, $y$ can determine the components incident to each
edge $e\in\widetilde{E}$, and therefore construct $\widetilde{CT}$ locally.

For clarity of presentation we assume $y\neq s$; the special case $y=s$ is
easier, and requires only slight modifications. We set $s$ as the root of
$\widetilde{T}$, and accordingly $C_{0}$ is the root of $\widetilde{CT}$. For
each $i=1,\dots,k$, denote by $e_{i}=(r_{i},p_{i})$ the unique edge in
$\widetilde{E}$ connecting $C_{i}$ to its parent in $\widetilde{CT}$, where
$r_{i}$ is the endpoint of $e_{i}$ inside $C_{i}$, and $p_{i}$ is the endpoint
lying in the parent component. See Figure 1 for an illustration.

Figure 1:  Left: Illustration of the trees $T$ and $\widetilde{T}$. The dashed
edges are $T$-edges incident to $y$, and the solid edges are
$\widetilde{E}$-edges. The components $C_{0},C_{1},\dots,C_{5}$ are each
internally connected via original $T$-edges. The tree $\widetilde{T}$ is
obtained by removing $y$ and its incident edges from $T$, and adding the
$\widetilde{E}$ edges. Right: The component tree $\widetilde{CT}$.

##### Step 1: Construction of $\widetilde{T}$.

The goal of this step is for each vertex in $V(T_{y})\setminus\\{y\\}$ to
learn its parent in $\widetilde{T}$. First, $y$ sends its children their
corresponding edges from $\widetilde{E}$, so each $y_{i}$ learns
$\mathsf{eid}_{T}(e_{i}=(r_{i},p_{i}))$. The $y_{i}$’s propagate (in parallel)
these edges down their $T$-subtrees, so that all vertices of component $C_{i}$
learn $\mathsf{eid}_{T}(e_{i})$. Then, a BFS procedure with source vertex
$r_{i}$ is executed inside each tree $T_{y_{i}}$ (in parallel). This completes
the step, since the $\widetilde{T}$-parent of each vertex in $C_{i}$ is its
BFS-parent from this last procedure, except for $r_{i}$ whose
$\widetilde{T}$-parent is $p_{i}$.

##### Step 2: Computing $\widetilde{T}$-Ancestry labels.

In later steps, we locally simulate Borůvka’s algorithm similarly to Section
2, but with the initial components being parts of $\widetilde{T}$. In order to
identify which components get merged by the outgoing edges, we need ancestry
labels with respect to $\widetilde{T}$ rather than $T$. As we are restricted
to send messages only on $V(T_{y})$-incident edges, we would like the $T$\-
and $\widetilde{T}$-labels to coincide for vertices in $C_{0}$ (as some of
them cannot be informed of new labels). Note that the compressed paths of
$v\in C_{0}$ w.r.t. $T$ and $\widetilde{T}$ are generally different, even
though $\pi(s,v,T)=\pi(s,v,\widetilde{T})$, as the these trees have different
heavy-light notions. Hence, instead of relying solely on compressed paths in
$\widetilde{T}$, we take a hybrid approach and define new labels based on
breaking each $\widetilde{T}$-path to a $T$-part and a strictly
$\widetilde{T}$-part, and compressing them accordingly. We still have the
challenge of computing (at least part of) the heavy-light decomposition of
$\widetilde{T}$. As the diameter of $\widetilde{T}$ might be $\Omega(\Delta
D)$, we cannot use simple bottom-up or top-down computations on
$\widetilde{T}$. The key to overcoming this is utilizing $y$ as a coordinator,
enabling the parts $C_{i}$ to work in parallel. The full details appear in the
proof of the next claim, which is deferred to Section 3.1 on implementation
details.

######  Claim 3.2.

In $\widetilde{O}(D)$-rounds of computation with $\widetilde{O}(1)$
congestion, in which messages are sent only on $V(T_{y})$-incident edges, one
can compute $\widetilde{T}$-ancestry labels
$\mathsf{anc}_{\widetilde{T}}(\cdot)$ of $\widetilde{O}(1)$ bits, such that
_every_ vertex $v$ of $\widetilde{T}$ learns
$\mathsf{anc}_{\widetilde{T}}(v)$.

##### Step 3: Computing Sketches w.r.t. $\widetilde{G}$ and $\widetilde{T}$.

We define new extended edge identifiers for edges of
$\widetilde{G}=G\setminus\\{y\\}$, based on its spanning tree $\widetilde{T}$.
For an edge $e=(u,v)$ of $G\setminus\\{y\\}$, let

$\displaystyle\mathsf{eid}_{\widetilde{T}}(e)=[\mathsf{uid}(e),\mathsf{id}(u),\mathsf{id}(v),\mathsf{anc}_{\widetilde{T}}(u),\mathsf{anc}_{\widetilde{T}}(v)].$

Next, for every vertex $v\in V\setminus\\{y\\}$ we define
$\mathsf{sketch}_{\widetilde{G}}(v)$ exactly as $\mathsf{sketch}_{G}(v)$, only
ignoring edges incident to $y$ in the sampling, and using the
$\mathsf{eid}_{\widetilde{T}}$ identifiers for the edges. Computing these new
sketches requires $\widetilde{O}(1)$ rounds of communication, in which every
$v\in C_{1}\cup\cdots\cup C_{k}$ sends $\mathsf{anc}_{\widetilde{T}}(v)$ to
all its $\widetilde{G}$-neighbors. As the $T$\- and $\widetilde{T}$-ancestry
labels coincide on the vertices of $C_{0}$, every vertex $v\in
V\setminus\\{y\\}$ can now determine $\mathsf{eid}_{\widetilde{T}}(e)$ for
every $\widetilde{G}$-edge $e$ incident to $v$, and use the random seed
$\mathcal{S}_{h}$ to compute $\mathsf{sketch}_{\widetilde{G}}(v)$.

Our next goal is letting each vertex $x\in C_{1}\cup\cdots\cup C_{k}$ learn
the $\widetilde{G}$-sketch of its $\widetilde{T}$-subtree (not $T$-subtree),
namely
$\mathsf{sketch}_{\widetilde{G}}(V(\widetilde{T}_{x}))=\bigoplus_{v\in\widetilde{T}_{x}}\mathsf{sketch}_{\widetilde{G}}(v)$.
This is done by using $y$ as a coordinator, similarly to the
$\widetilde{T}$-subtree sum computation in the proof of 3.2. We start by XOR-
aggregation of the $\widetilde{G}$-sketches upwards on each $T_{y_{i}}$ (in
parallel), which takes $\widetilde{O}(D)$ rounds, and results in each $y_{i}$
learning $\mathsf{sketch}_{\widetilde{G}}(C_{i})$. Within $\widetilde{O}(1)$
rounds, these component $\widetilde{G}$-sketches are passed to $y$ from its
children. $y$ can now locally compute the $\widetilde{T}$-subtree
$\widetilde{G}$-sketch of each $r_{i}$ as follows:
$\mathsf{sketch}_{\widetilde{G}}(V(\widetilde{T}_{r_{i}}))=\oplus_{j\in
J(i)}\mathsf{sketch}_{\widetilde{G}}(C_{j})$, where $J(i)$ is the set of all
indices $j$ such that $C_{j}$ is the subtree of $C_{i}$ in the component tree
$\widetilde{CT}$. Then, $y$ sends each of its children $y_{i}$ the
$\widetilde{T}$-subtree sketch of $r_{i}$, and which is propagated down on
each $T_{y_{i}}$ (in parallel) so that each $r_{i}$ learns
$\mathsf{sketch}_{\widetilde{G}}(V(\widetilde{T}_{r_{i}}))$. The $r_{i}$’s
then send this information to their $\widetilde{T}$-parent, which are the
$p_{i}$’s. For each vertex $v$ of $\widetilde{T}$, let

$\beta_{v}=\begin{cases}\text{if
$v=p_{j}$:}&\mathsf{sketch}_{\widetilde{G}}(v)+\mathsf{sketch}_{\widetilde{G}}(V(\widetilde{T}_{r_{j}}))\\\
\text{otherwise:}&\mathsf{sketch}_{\widetilde{G}}(v)\end{cases}$

Then by this point, every $v\in C_{1}\cup\cdots\cup C_{k}$ know its
$\beta_{v}$ value. For $i=1,\dots,k$, let $\widetilde{T}^{(i)}$ be the tree
induced on $C_{i}$ by $\widetilde{T}$, where the parents in
$\widetilde{T}^{(i)}$ are the same as in $\widetilde{T}$. Equivalently,
$\widetilde{T}^{(i)}$ is the tree obtained by rerooting $T_{y_{i}}$ at the
vertex $r_{i}$. Each of its leaves is either an original $\widetilde{T}$-leaf
or a $p_{j}$ vertex for some $j$. The crux is that for each $x\in C_{i}$ it
holds that
$\mathsf{sketch}_{\widetilde{G}}(V(\widetilde{T}_{x}))=\oplus_{v\in\widetilde{T}^{(i)}_{x}}\beta_{v}$.
That is, the $\widetilde{T}$-subtree $\widetilde{G}$-sketch of $x$ is equal to
the sum-of-$\beta$’s in its $\widetilde{T}^{(i)}$-subtree. Hence, we complete
the computation in this step by executing bottom-up XOR-aggregation of the
$\beta_{v}$ values in each of the trees $\widetilde{T}^{(i)}$ in parallel.

Finally, as $\mathsf{sketch}_{\widetilde{G}}(V\setminus\\{y\\})$ is just the
all-$0$’s string (by 1.5), it is also known to each $x\in C_{1}\cup\cdots\cup
C_{k}$.

##### Step 4: Local Borůvka Simulation In $G\setminus\\{x,y\\}$.

This entire step is executed by local computation in which each $x\in
C_{1}\cup\cdots\cup C_{k}$ determines whether it is a cut vertex in
$G\setminus\\{y\\}$, or equivalently if $xy$ is a cut pair in $G$. This is
done by locally simulating Borůvka’s algorithms using the sketches of the
components of $\widetilde{T}\setminus\\{x\\}$ (which are known to $x$ by Step
3) in an identical manner to the last step of the (single) cut vertices
detection algorithm of Section 2, replacing $G$ and $T$ there with
$G\setminus\\{y\\}$ and $\widetilde{T}$. We note that the new ancestry labels,
extended identifiers and sketches, _computed w.r.t. $\widetilde{T}$_, are
important for this simulation to follow through exactly as in Section 2. This
completes the proof of Lemma 3.1.

We conclude this section by describing the scheduling of the algorithms
$\\{A_{y}\\}_{y\in V}$:

######  Lemma 3.3.

The collection of algorithms $\\{{\cal A}_{y}\\}_{y\in V}$ can be executed
simultaneously within $\widetilde{O}(D)$ rounds, w.h.p.

###### Proof.

The key observation is that every edge $e$ participates in $O(D)$ algorithms.
Specifically, since each algorithm ${\cal A}_{y}$ exchanges messages only on
edges incident to $V(T_{y})$, we get that the algorithms using $e=(u,v)$ are
exactly $\\{{\cal A}_{y}\mid y\in\pi(s,u,T)\cup\pi(s,v,T)\\}$. Therefore, the
total number of messages sent through $e=(u,v)$ in the collection of $n$
algorithms $\\{A_{y}\\}_{y\in V}$ is at most
$\widetilde{O}(1)\cdot(|\pi(s,u,T)|+|\pi(s,v,T)|)=\widetilde{O}(D)$. The
result follows by employing Theorem 1.8 with congestion and dilation bounds of
$\widetilde{O}(D)$. ∎

###  3.1 Implementation Details for Section 3

###### Proof of Claim 3.2.

We define the labels $\mathsf{anc}_{\widetilde{T}}$ as follows. If $v\in
C_{0}$, we simply take its $T$-ancestry label, i.e.
$\mathsf{anc}_{\widetilde{T}}(v)=\mathsf{anc}_{T}(v)=\pi^{*}(s,v,T)$. We now
define $\mathsf{anc}_{\widetilde{T}}(v)$ for $v\in C_{i}$, $i\neq 0$. The
$s$-$v$ $\widetilde{T}$-path decomposes as
$\pi(s,v,\widetilde{T})=\pi(s,p_{j},T)\circ(p_{j},r_{j})\circ\pi(r_{j},v,\widetilde{T}_{r_{j}})$
for the unique $p_{j}\in C_{0}$ which is an ancestor of $v$ in
$\widetilde{T}$. Then $\mathsf{anc}_{\widetilde{T}}(v)$ is obtained by heavy-
light compression of these paths as
$\mathsf{anc}_{\widetilde{T}}(v)=\pi^{*}(s,p_{j},T)\circ(p_{j},r_{j})\circ\pi^{*}(r_{j},v,\widetilde{T}_{r_{j}})$.
(The heavy-light notions in the first segment are those of $T$, while in the
last segment they are those of $\widetilde{T}$.)

Given the $\mathsf{anc}_{\widetilde{T}}$-labels of any $u,v\in
V(\widetilde{T})$, one can easily determine if $\pi(s,u,\widetilde{T})$ is a
prefix of $\pi(s,v,\widetilde{T})$, and thus if $u$ is an
$\widetilde{T}$-ancestor of $v$. As compressed paths require $O(\log^{2}n)$
bits, each $\mathsf{anc}_{\widetilde{T}}$-label consists of
$O(\log^{2}n)=\widetilde{O}(1)$ bits.

We now compute the $\mathsf{anc}_{\widetilde{T}}$-labels. The vertices of
$C_{0}$ already hold them, as they are equal to their
$\mathsf{anc}_{T}$-labels. It remains to compute them for the vertices of
$C_{1}\cup\cdots\cup C_{k}$. This is done in three steps, as follows.

Step A: Heavy-Light Decomposition of $\widetilde{T}$. Our first task is
letting each $v\in C_{1}\cup\cdots\cup C_{k}$ learn its heavy/light
classification in $\widetilde{T}$. This essentially involves computing subtree
sizes in $\widetilde{T}$. At first glance, one might consider computing these
by simple aggregation on $\widetilde{T}$. This approach fails, the height of
$\widetilde{T}$ might be $\Omega(\Delta\cdot D)$. To overcome this, we use $y$
as a coordinator to jump-start the aggregation. Recall that all component
sizes $|C_{i}|$ are known to $y$ by the preprocessing. Therefore, $y$ can
locally compute the $\widetilde{T}$-subtree sizes of all the $r_{i}$’s:
$|V(\widetilde{T}_{r_{i}})|$ is the sum-of-sizes of components lying in the
subtree of $C_{i}$ in the component tree $\widetilde{CT}$. Then, $y$ sends
$|V(\widetilde{T}_{r_{i}})|$ to each child $y_{i}$, and this is propagated
down $T_{y_{i}}$ (in parallel), so that each $r_{i}$ learns its
$\widetilde{T}$-subtree size. Each $r_{i}$ passes this information also to its
$\widetilde{T}$-parent $p_{i}$. For any vertex $v\in V\setminus\\{y\\}$,
define

$\alpha_{v}=\begin{cases}\text{if $v=p_{i}$:}&|V(\widetilde{T}_{r_{i}})|+1,\\\
\text{otherwise:}&1.\end{cases}$

Then by this point, every vertex $v\in C_{1}\cup\cdots\cup C_{k}$ knows its
corresponding value $\alpha_{v}$. For $i=1,\dots,k$, let $\widetilde{T}^{(i)}$
be the tree induced on $C_{i}$ by $\widetilde{T}$, where the parents in
$\widetilde{T}^{(i)}$ are the same as in $\widetilde{T}$. Equivalently,
$\widetilde{T}^{(i)}$ is the tree obtained by rerooting $T_{y_{i}}$ at the
vertex $r_{i}$. Each of its leaves is either an original $\widetilde{T}$-leaf
or a $p_{j}$ vertex for some $j$. The crux is that for each $v\in C_{i}$ it
holds that
$|V(\widetilde{T}_{v})|=\sum_{u\in\widetilde{T}^{(i)}_{v}}\alpha_{u}$. That
is, the $\widetilde{T}$-subtree size of $v$ is equal to the sum-of-$\alpha$’s
in its $\widetilde{T}^{(i)}$-subtree. By executing bottom-up sum-aggregation
of the $\alpha_{v}$’s in each of the trees $\widetilde{T}^{(i)}$ in parallel,
each $v\in C_{1}\cup\cdots\cup C_{k}$ learns its $\widetilde{T}$-subtree size.
Each such vertex $v$ then passes its $\widetilde{T}$-subtree size to its
parent, enabling the parents to classify their children into light or heavy in
$\widetilde{T}$, and inform them of their classification.

Step B: Computing Compressed $\widetilde{T}$-Paths Inside the $C_{i}$’s. In
this step, each $v\in C_{i}$, $i\neq 0$, learns the compressed path
$\pi^{*}(r_{i},v,\widetilde{T}_{r_{i}})$. The main observation is that if a
vertex is given the compressed path of its parent, it can easily deduce its
own compressed path (as it know its own heavy/light classification).
Therefore, the required compressed paths can be computed in a top-down fashion
on each $\widetilde{T}^{(i)}$ (in parallel).

Step C: Obtaining The $\mathsf{anc}_{\widetilde{T}}$-labels. For $j=1,\dots,k$
define

$\pi_{j}=\begin{cases}\text{if $p_{j}\in C_{i}$ with $i\neq
0$:}&\pi^{*}(r_{i},p_{j},\widetilde{T}_{r_{i}}),\\\ \text{if $p_{j}\in
C_{0}$:}&\pi^{*}(s,p_{j},T)=\mathsf{anc}_{T}(p_{j}).\end{cases}$

Observe that by Step B, the $p_{j}$’s know their corresponding $\pi_{j}$’s. To
send this information to $y$, each $p_{j}$ sends $\pi_{j}$ to $r_{j}$, and the
messages are then forwarded upwards on each $T_{y_{j}}$ (in parallel), along
with the heavy/light classification of the $r_{j}$’s. Using the information of
$\\{\pi_{j}\\}_{j}$, the component tree $\widetilde{CT}$ and the heavy/light
classifications of the $r_{j}$’s, $y$ can locally compute
$\mathsf{anc}_{\widetilde{T}}(r_{i})$ for each $r_{i}$, and send this label to
the corresponding child $y_{i}$. Then, $\mathsf{anc}_{\widetilde{T}}(r_{i})$
is broadcasted on each $T_{y_{i}}$. Finally, $\mathsf{anc}_{\widetilde{T}}(v)$
can be locally deduced in $v$ from the information in
$\mathsf{anc}_{\widetilde{T}}(r_{i})$ and $\pi^{*}(v,\widetilde{T}_{r_{i}})$,
where the latter is known to $v$ by Step B. ∎

##  4 Independent Cut Pairs

We now turn to consider the case where the cut pair $xy$ is independent, i.e.,
$x,y$ have no ancestor/descendant relations. Throughout this section, for
every vertex $x\in V$, let $V_{x}=V(T_{x})\setminus\\{x\\}$. Recall that we
assume that there is no single cut vertex in the graph. Our algorithm is based
on the introduced notion of $x$-_connectivity trees_ , $\widehat{T}_{x}$,
computed locally at each vertex $x$. Let
$\mathcal{C}_{x}=\\{C_{1},\ldots,C_{k}\\}$ denote the maximal connected
components in the induced graph $G[V_{x}]$. For each $C\in\mathcal{C}_{x}$,
the tree $\widehat{T}_{x}$ contains a path
$\pi_{x}(s,C)=\pi(s,u_{C})\circ(u_{C},v_{C})$, where $(u_{C},v_{C})$ is a
$G$-edge such that $v_{C}\in C$, and $x\notin\pi(s,u_{C})$. Therefore,
$\widehat{T}_{x}$ encodes the connectivity of $s$ to $V_{x}$ in the graph
$G\setminus\\{x\\}$. For every $v\in V_{x}$, let $C_{x,v}$ denote the
component containing $v$ in $\mathcal{C}_{x}$. When $v=x_{h}$, we denote
$H_{x}=C_{x,x_{h}}$ and call it the _heavy component_ of $x$. See illustration
in Figure 2. We next describe the computation of these $\widehat{T}_{x}$
trees, and later on show how they guide the identification of independent cut
pairs.

Throughout, we assume that the vertices hold all the preprocessing information
as in Section 3, and that the ID of each vertex $v$ contains also its
compressed-path $\mathsf{anc}_{T}(v)=\pi^{*}(s,v)$.

Figure 2: Left: Illustration of $\mathcal{C}_{x}$, the connected components in
$G[V_{x}]$. Each component is a union of subtrees rooted at children of $x$.
The heavy component $H_{x}$ is the one containing $x_{h}$. For each component
$C\in\mathcal{C}_{x}$ the corresponding edge $(u_{C},v_{C})$ appears as a
thick solid curve. The tree paths to the $u_{C}$ vertices, all lying outside
$T_{x}$, are shown by solid lines. Right: The corresponding tree
$\mathcal{T}_{x}$, consisting of the paths
$\pi_{x}(s,C)=\pi(s,u_{C})\circ(u_{C},v_{C})$ for each $C\in\mathcal{C}_{x}$.

###  4.1 Computing $x$-Connectivity Trees

The computation of connectivity trees has two main steps, both based on
bottom-up aggregation of certain graph sketches over the BFS tree $T$. The
purpose of the first step is letting every $x\in V$ determine the connected
components $\mathcal{C}_{x}$ in $G[V_{x}]$. Each such component $C$ is
identified by its component-ID, which is defined as the largest vertex ID
among all the IDs of $T$-children of $x$ inside $C$. Additionally, each $u\in
V$ learns the component-ID of its component $C_{x,u}\in\mathcal{C}_{x}$, for
all of its ancestors $x\in\pi(s,u)$. The second step aggregates a special form
of graph sketches, providing $x$ with the path information required to locally
compute its connectivity tree $\widehat{T}_{x}$.

##### Step 1: Computing Connectivity in $G[V_{x}]$.

For ease of notation, denote by $d_{x}=0pt_{T}(x)$ the depth of vertex $x$ in
$T$. We say that an edge $e=(u,v)$ has depth $d$ if
$0pt_{T}(\operatorname{LCA}(u,v))=d$. This step is based on aggregating along
$T$ the information of $D$ types of graph sketches, one for every depth $1\leq
d\leq D$. The $d^{th}$ sketch type $\mathsf{sketch}^{d}_{G}(\cdot)$ will be
restricted to sampling only edges of depth _at least_ $d$. This is helpful by
the following observation: in order to locally simulate the connectivity
Borůvka algorithm in $G[V_{x}]$ at every $x$, it is required for $x$ to learn
$\mathsf{sketch}_{G[V_{x}]}(V(T_{x^{\prime}}))$ for each $T$-child
$x^{\prime}$ of $x$. Since the edges of $G[V_{x}]$ can be identified as
$G$-edges in $V_{x}\times(V\setminus\\{x\\})$ of depth at least $d_{x}$, $x$
can easily transform $\mathsf{sketch}^{d_{x}}_{G}(V(T_{x^{\prime}}))$ to the
required sketch by eliminating the $x$-incident edges from it. The following
lemma summarizes the output of this step, and the detailed implementation
appears in its proof.

######  Lemma 4.1.

There is a randomized $\widetilde{O}(D)$-round algorithm that computes
connectivity in $G[V_{x}]$ for every $x\in V$ simultaneously. At the end of
its execution, w.h.p. all of the following hold:

  1. 1.

Every $x\in V$ knows the component-ID of $C_{x,x^{\prime}}$ for each of its
children $x^{\prime}$.

  2. 2.

Every $u\in V$ knows the component-ID of $C_{x,u}$ for each of its ancestors
$x\in\pi(s,u)$.

  3. 3.

Every $v\in V$ knows the information of item 2 for each of its neighbors. That
is, the component-ID of $C_{x,u}$ for every $u$ adjacent to $v$ and
$x\in\pi(s,u)$.

###### Proof.

This is implemented as follows. First, within $O(D)$ rounds, we let each
vertex learn its tree path $\pi(s,u)$, and exchange this information with all
its neighbors. Using this information, $u$ can locally compute for every
$1\leq d\leq D$ the set of its incident edges with depth at least $d$, that is
$E_{d}(u)=\\{(u,v)\in E\mid 0pt_{T}(\operatorname{LCA}(u,v))\geq d\\}$. Then,
the source $s$ locally samples a random seed and broadcasts it to all the
vertices. Using this seed, each $u$ computes the $D$ sketches
$\mathsf{sketch}^{1}_{G}(u),\ldots,\mathsf{sketch}^{D}_{G}(u)$, where the
edges in the $d$’th sketch $\mathsf{sketch}^{d}_{G}(u)$ are based on using the
seed to implement the sampling of the edges only from $E_{d}(u)$. Next, the
algorithm aggregates these $D$ sketch types over subtrees. This can be done in
a pipeline manner from the leaf vertices up to the root, in increasing order
of the depth $d$ of the sketches. At the end of this computation, each vertex
$x$ of depth $d_{x}$ holds the the sketch
$\mathsf{sketch}^{d_{x}}_{G}(V(T_{x^{\prime}}))$ for each of its $T$-child
$x^{\prime}$. The final sketch $\mathsf{sketch}_{G[V_{x}]}(V(T_{x^{\prime}}))$
is obtained locally at $x$ by canceling-out its own edges to
$V(T_{x^{\prime}})$ from $\mathsf{sketch}^{d_{x}}(V(T_{x^{\prime}}))$, using
Lemma 1.7. At this point, each vertex $x$ has all the required sketch
information to locally simulate the Borůvka algorithm in $G[V_{x}]$. As a
result of this computation, w.h.p. $x$ holds the component-ID of
$C_{x,x^{\prime}}\in\mathcal{C}_{x}$ for each $T$-child $x^{\prime}$ of $x$,
establishing item 1. This information is then propagated down the tree $T$ in
a pipeline manner, where each vertex $u$ eventually learns the component-ID of
$C_{x,u}$ for each of its ancestors $x\in\pi(s,u)$, establishing item 2. By
exchanging the information of item 2 between neighbors, we obtain also item 3.
It is easy to see that this entire computation takes $\widetilde{O}(D)$
rounds. ∎

##### Step 2: Computing $x$-Connectivity Trees $\widehat{T}_{x}$ via Path-
Sketches.

Our next goal is to provide each vertex $x$ with the path information
$\pi_{x}(s,C)$, for every component $C\in\mathcal{C}_{x}$. Recall that
$\pi_{x}(s,C)=\pi(s,u_{C})\circ(u_{C},v_{C})$, where $v_{C}\in C$ and
$x\notin\pi(s,u_{C})$. Such a path must exists as we assume $x$ is not a cut
vertex. Towards this goal, we define _path-sketches_
$\mathsf{sketch}_{G}^{P}(\cdot)$. These are defined exactly as the regular
sketches, only using new edge identifiers $\mathsf{eid}_{T}^{P}(e=(u,v))$
obtained by augmenting $\mathsf{eid}_{T}(e)$ of Eq. 1 with the tree paths of
the endpoints $u,v$. Formally,

$\displaystyle\mathsf{eid}^{P}_{T}(e=(u,v))=[\mathsf{uid}(e),\mathsf{id}(u),\mathsf{id}(v),\mathsf{anc}_{T}(u),\mathsf{anc}_{T}(v),\pi(s,u),\pi(s,v)]~{}.$
(2)

Note that in contrast to $\mathsf{eid}_{T}(e)$ of Equation 1 which contains
$\widetilde{O}(1)$ bits, $\mathsf{eid}_{T}^{P}(e)$ of Equation 2 has
$\widetilde{O}(D)$ bits. Therefore, a path-sketch also has $\widetilde{O}(D)$
bits. However, we can still aggregate the path-sketches on $T$ so that
eventually every $x$ learns $\mathsf{sketch}^{P}_{G}(V(T_{x^{\prime}}))$ for
all its children $x^{\prime}$. Using the information of the previous step, $x$
can now locally compute the path-sketches of each component
$C\in\mathcal{C}_{x}$, and then obtain $\pi_{x}(s,C)$ by extracting
$\mathsf{eid}_{T}^{P}(e)$ of an outgoing edge from $C$. The proof of the
following lemma explains this process in further detail.

######  Lemma 4.2.

There is a randomized $\widetilde{O}(D)$-round algorithm letting each vertex
$x\in V$ learn its connectivity tree $\widehat{T}_{x}$, w.h.p.

###### Proof.

In order to compute the $\mathsf{eid}_{T}^{P}$-identifiers, it is enough to
let each vertex $u$ learn its tree path $\pi(s,u)$ and exchange this
information with all its neighbors, which can be done within $O(D)$ rounds.
The source then broadcast an $\widetilde{O}(1)$-bit random seed in
$\widetilde{O}(D)$ rounds, allowing each vertex $u$ to compute its path-sketch
$\mathsf{sketch}_{G}^{P}(u)$. The subtree path-sketches
$\mathsf{sketch}^{P}_{G}(V(T_{u}))$ for every vertex $u$ are then computed by
XOR-aggregation of $\widetilde{O}(D)$-length vectors on $T$, which can be done
in $\widetilde{O}(D)$ rounds via a standard pipeline. At the end of this
computation, each vertex $x$ holds the path-sketch
$\mathsf{sketch}^{P}_{G}(V(T_{x^{\prime}}))$ for each of its $T$-children
$x^{\prime}$. Using Lemma 1.7, $x$ can locally cancel-out its own edges to
obtain $\mathsf{sketch}^{P}_{G\setminus\\{x\\}}(V(T_{x^{\prime}}))$. Using the
information of Lemma 4.1, $x$ can add-up the subtree sketches of its children
to obtain $\mathsf{sketch}^{P}_{G\setminus\\{x\\}}(C)$ for all
$C\in\mathcal{C}_{x}$. Specifically, letting $N(x,C)$ denote the set of
$T$-children of $x$ inside the component $C$, we have
$\mathsf{sketch}^{P}_{G\setminus\\{x\\}}(C)=\oplus_{x^{\prime}\in
N(x,C)}\mathsf{sketch}^{P}_{G\setminus\\{x\\}}(V(T_{x^{\prime}}))$. Using
$O(\log n)$ basic sketch units of each such component sketch enables $x$ to
learn, w.h.p., the $\mathsf{eid}_{T}^{P}$-identifier of one outgoing edge per
component. As $C$ is a maximal connected component in $G[V_{x}]$, its outgoing
edge must connect it to $V\setminus V(T_{x})$. Specifically, for
$C\in\mathcal{C}_{x}$, $x$ learns $\mathsf{eid}_{T}^{P}((u_{C},v_{C}))$ where
$v_{C}\in C$ and $u_{C}\in V\setminus V(T_{x})$. As the tree-path
$\pi(s,u_{C})$ is stored in $\mathsf{eid}_{T}^{P}((u_{C},v_{C}))$, the path
$\pi_{x}(s,C)$ is easily deduced. The final tree is given by
$\widehat{T}_{x}=\bigcup_{C\in\mathcal{C}_{x}}\pi_{x}(s,C)$. ∎

Finally, we would like each vertex $u$ to learn some representation of the
path of its component $C_{x,u}$ in the tree $\widehat{T}_{x}$, for all its
ancestors $x\in\pi(s,u)$. To this end, we define compressed representation of
these paths: for $x\in V$ and $C\in\mathcal{C}_{x}$ the compressed path of
$\pi_{x}(s,C)$ is $\pi_{x}^{*}(s,C)=\pi^{*}(s,u_{C})\circ(u_{C},v_{C})$,
consisting only of $\widetilde{O}(1)$ bits. This enables us to achieve the
following.

######  Lemma 4.3.

Given that every vertex $x\in V$ holds its connectivity tree
$\widehat{T}_{x}$, there is an $\widetilde{O}(D)$-round algorithm such that in
the end of its execution, the following hold:

  1. 1.

Each $u\in V$ learns the compressed path $\pi_{x}^{*}(s,C_{x,u})$ for every
$x\in\pi(s,v)$, as well as the entire path $\pi_{x}(s,C_{x,u})$ in case
$x\in\mathsf{LA}(u)$.

  2. 2.

Each $v\in V$ learns all the information of item 1 for each neighboring vertex
$u$.

###### Proof.

We let every vertex $x$ send the full path $\pi_{x}(s,C_{x,x^{\prime}})$ and
its compressed version $\pi_{x}^{*}(s,C_{x,x^{\prime}})$ to each light child
$x^{\prime}$ of $x$, and only the compressed path $\pi^{*}_{x}(s,H_{x})$ to
its heavy child $x_{h}$. This information is propagated towards the leaf
vertices of $T_{x}$. Since each vertex is required to receive
$\widetilde{O}(D)$ bits of information from each of its _light_ ancestors, as
well as $\widetilde{O}(1)$ bits from each of its heavy ancestors, overall it
is required to receive $\widetilde{O}(D)$ bits. This can be done in
$\widetilde{O}(D)$ rounds, by standard pipeline techniques. This establishes
item 1. For item 2, we simply exchange the $\widetilde{O}(D)$-bit information
of item 1 between neighboring nodes, within additional $\widetilde{O}(D)$
rounds. ∎

###  4.2 Component Classification Based on Sensitivity

We use the structure of the $x$-connectivity tree $\widehat{T}_{x}$ to
classify its potential independent cut-mates. The first immediate observation
is that in case $\hat{T}_{x}$ is non-empty, any independent cut-mate $y$ of
$x$ (if exists) must be in $\widehat{T}_{x}$. We further examine the
_sensitivity_ of each component in $\mathcal{C}_{x}$ to different such
potential cut-mates $y$, as described in the following definition.

######  Definition 4.1 (Sensitivity Notions of $\mathcal{C}_{x}$ Components).

Fix an independent pair $x,y$. A component $C\in\mathcal{C}_{x}$ is called
_$y$ -sensitive_ if $y\in\pi_{x}(s,C)$.

We further classify the $y$-sensitive components into two types:

  * •

$C\in\mathcal{C}_{x}$ is _pseudo- $y$-senstive_ if $\pi_{x}(s,C)$ contains a
$T$-edge $(y,y^{\prime})$ such that $x\notin\pi_{y}(s,C_{y,y^{\prime}})$. That
is, the component $C_{y,y^{\prime}}$ of $y^{\prime}$ in $\mathcal{C}_{y}$ is
not $x$-sensitive.

  * •

$C\in\mathcal{C}_{x}$ is _fully- $y$-senstive_ if it is $y$-sensitive but not
pseudo-$y$-sensitive. Equivalently, if either $y=u_{C}$, or $\pi_{x}(s,C)$
contains a $T$-edge $(y,y^{\prime})$ such that
$x\in\pi_{y}(s,C_{y,y^{\prime}})$.

We denote by $\mathcal{S}(x,y)$, $\mathcal{PS}(x,y)$ and $\mathcal{FS}(x,y)$
the collections of components in $\mathcal{C}_{x}$ that are $y$-sensitive,
pseudo-$y$-sensitive and fully-$y$-sensitive, respectively101010Notice that
these notations are not symmetric in $x,y$, e.g. $\mathcal{S}(x,y)$ is
different than $\mathcal{S}(y,x)$..

######  Lemma 4.4.

Let $x,y$ be an independent pair, and let $C\in\mathcal{C}_{x}$. If $C$ is not
fully-$y$-sensitive (i.e. $C\in\mathcal{C}_{x}\setminus\mathcal{FS}(x,y)$),
then $C$ is connected to $s$ by a path in $G\setminus\\{x,y\\}$ avoiding all
components in $\mathcal{FS}(x,y)\cup\mathcal{FS}(y,x)$.

###### Proof.

Consider first the case where $C$ is not $y$-sensitive: then $\pi_{x}(s,C)$ is
the required path. The other case is when $C$ is pseudo-$y$-sensitive. Then,
let $(y,y^{\prime})\in\pi_{x}(s,C)$ be a $T$-edge such that
$C_{y,y^{\prime}}\in\mathcal{C}_{y}$ is not $x$-sensitive. By the previous
case, $C_{y,y^{\prime}}$ is connected to $s$ by a path in
$G\setminus\\{x,y\\}$ avoiding all components in
$\mathcal{FS}(x,y)\cup\mathcal{FS}(y,x)$. Denote this path by $Q$. Now,
Observe that the last edge $(u_{C},v_{C})$ of $\pi_{x}(s,C)$ is such that
$v_{C}\in C$ and $u_{C}\in C_{y,y^{\prime}}$ (as $x$ and $y$ are independent).
W.l.o.g., we may assume that the endpoint of $Q$ in $C_{y,y^{\prime}}$ is
$u_{C}$ (as any two vertices of $C_{y,y^{\prime}}$ are connected by a path
inside $C_{y,y^{\prime}}$). Thus, $Q\circ(u_{C},v_{C})$ is the required path
for $C$. ∎

The following lemma shows that each vertex $x$ can, in many cases, distinguish
between full sensitivity and pseudo sensitivity of a component
$C\in\mathcal{C}_{x}$ to the potential cut-mates in $\pi_{x}(s,C)$.

######  Lemma 4.5.

There is a randomized $\widetilde{O}(D)$-round algorithm such that by the end
of the execution, w.h.p. each $x\in V$ holds the following information:

  1. 1.

$\pi^{*}_{y}(s,C_{y,y^{\prime}})$ for every $T$-edge
$(y,y^{\prime})\in\pi_{x}(s,C)$ and every
$C\in\mathcal{C}_{x}\setminus\\{H_{x}\\}$.

  2. 2.

$\pi^{*}_{y}(s,C_{y,y^{\prime}})$ for every _light $T$-edge_
$(y,y^{\prime})\in\pi_{x}(s,H_{x})$

Note that given $\pi^{*}_{y}(s,C_{y,y^{\prime}})$, $x$ can check whether
$x\in\pi_{y}(s,C_{y,y^{\prime}})$. Consequently, the following holds: if
$C\in\mathcal{S}(x,y)$ such that either $C\neq H_{x}$ or
$(y,y_{h})\notin\pi_{x}(s,C)$, then $x$ knows if $C\in\mathcal{FS}(x,y)$ or
$C\in\mathcal{PS}(x,y)$.

###### Proof.

We start in a preprocessing step, in which we let each vertex $u$ learn the
compressed-path $\pi^{*}_{y}(s,C_{y,y^{\prime}})$ for every edge
$(y,y^{\prime})\in\pi(s,u)$, and further exchange this information with all
its neighbors. This can be done by downcasting the information on $T$ within
$\widetilde{O}(D)$ rounds. At this point, for every $x\in V$ and
$C\in\mathcal{C}_{x}$, the vertex $v_{C}\in C$ (which is the last vertex of
$\pi_{x}(s,C)$) holds the compressed path $\pi^{*}_{y}(s,C_{y,y^{\prime}})$
for every $T$-edge $(y,y^{\prime})\in\pi_{x}(s,C)$. Our goal is to pass (most)
of this preprocessing information up to $x$. To this end, we design for each
$x\in V$ two specialized algorithms, $\mathcal{L}_{x}$ and $\mathcal{H}_{x}$,
letting $x$ learn the information specified in item 1 and item 2 of the lemma,
respectively. They have the following properties:

  * •

$\mathcal{L}_{x}$ has dilation and congestion $\widetilde{O}(D)$, sending
messages only on edges incident to $\mathsf{LD}(x)$.

  * •

$\mathcal{H}_{x}$ has dilation $\widetilde{O}(D)$, congestion
$\widetilde{O}(1)$, sending messages only on edges incident to $V(T_{x})$.

These enable us to execute all algorithms
$\\{\mathcal{L}_{x},\mathcal{H}_{x}\\}_{x\in V}$ in parallel within
$\widetilde{O}(D)$ rounds using Theorem 1.8. Indeed, the dilation bound is
obvious. As for congestion, consider some edge $e$. There are at most $O(\log
n)$ vertices $x$ such that either of its endpoint belongs to $\mathsf{LD}(x)$,
hence $e$ needs to pass at most $O(\log
n)\cdot\widetilde{O}(D)=\widetilde{O}(D)$ messages of $\mathcal{L}_{x}$
algorithms. Also, there are at most $O(D)$ vertices $x$ such that either of
its endpoints belongs to $V(T_{x})$, hence $e$ needs to pass at most
$O(D)\cdot\widetilde{O}(1)=\widetilde{O}(D)$ messages of $\mathcal{H}_{x}$
algorithms.

It remains to describe the algorithms $\mathcal{L}_{x}$ and $\mathcal{H}_{x}$.
For $\mathcal{L}_{x}$, we let each vertex $v_{C}$ of a non-heavy component
$C\in\mathcal{C}_{x}\setminus\\{H_{x}\\}$ propagate the entire
$\widetilde{O}(D)$-bit preprocessing information upwards to $x$ on
$\pi(x,v_{C})$. As the collection of paths
$\\{\pi(s,v_{C})\\}_{C\in\mathcal{C}_{x}\setminus\\{H_{x}\\}}$ is edge-
disjoint, this can be done in parallel on all these paths, yielding the
required dilation and congestion for $\mathcal{L}_{x}$. Finally, in
$\mathcal{H}_{x}$, we let $v_{H_{x}}$ propagate the $\widetilde{O}(1)$-bits of
relevant information for item 2 in the lemma up to $x$ along
$\pi(x,v_{H_{x}})$, which clearly achieves the required dilation and
congestion for $\mathcal{H}_{x}$. ∎

From now on, we assume that all the (randomized) algorithms specified in
lemmas 4.1, 4.2, 4.3 and 4.5 were executed, and gave correct outputs (which
happens w.h.p.).

###  4.3 $xy$-Connectivity Algorithms Under a Promise

We next discuss the procedure for determining the $xy$-connectivity (i.e. the
connectivity of $G\setminus\\{x,y\\}$) for collections of independent pairs
$xy$ which satisfy a given _promise_. For an overview, see Section 1.1. The
following definition plays a key role in this procedure.

######  Definition 4.2.

Let $x,y$ be an independent pair. We define $\mathsf{LDS}(x,y)$ as the set of
light $x$-descendants in $y$-sensitive components. That is,
$\mathsf{LDS}(x,y)=\\{v\in\mathsf{LD}(x)\mid y\in\pi_{x}(s,C_{x,v})\\}.$

######  Observation 4.6.

Every vertex $v$ belongs to a total of $O(D\log n)$ sets $\mathsf{LDS}(x,y)$
for $x,y\in V$.

###### Proof.

$v$ belongs to $\mathsf{LD}(x)$ only for its $O(\log n)$ light ancestors $x$,
and $|\pi_{x}(s,C_{x,v})|=O(D)$. ∎

The following theorem states the properties of a single $xy$-connectivity
algorithm.

######  Theorem 4.7 ($xy$-Connectivity Given an $x$-$y$ Path).

Fix an independent pair $x,y$, and assume that there is an $x$-$y$ path
$\Pi_{x,y}\subseteq G$ of length $O(D)$ (known in a distributed manner). Then,
there is a randomized $xy$-connectivity algorithm $\mathcal{A}^{P}_{x,y}$ of
$\widetilde{O}(D)$ rounds and $\widetilde{O}(1)$ congestion, sending messages
only along (i) the edges of $\Pi_{x,y}$ and (ii) edges incident to
$\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. At the end of the execution, w.h.p.
both $x$ and $y$ know whether $G\setminus\\{x,y\\}$ is connected or not.

The major part of this section is devoted to proving Theorem 4.7. Before doing
so, we show that for a set of independent pairs $Q\subseteq V\times V$, all
algorithms $A_{x,y}^{P}$ for $xy\in Q$ can be scheduled simultaneously when
provided a path collection $\mathcal{P}_{Q}=\\{\Pi_{x,y}\mid xy\in Q\\}$
satisfying the following:

> [Promise:] _$\mathcal{P}_{Q}$ -paths have length $O(D)$, and each $G$-edge
> appears on $\widetilde{O}(D)$ $\mathcal{P}_{Q}$-paths._

######  Corollary 4.8.

[All Pairs $xy$-Connectivity Under a Promise] Let $Q\subseteq V\times V$ be a
collection of independent pairs, and $\mathcal{P}_{Q}=\\{\Pi_{x,y}\mid xy\in
Q\\}$ be a collection of $x$-$y$ paths (each known is a distributed manner)
satisfying the promise. Then, all algorithms $\mathcal{A}^{P}_{x,y}$ for
$xy\in Q$ (where $\mathcal{A}^{P}_{x,y}$ uses the path
$\Pi_{x,y}\in\mathcal{P}_{Q}$) can be executed simultaneously within
$\widetilde{O}(D)$ rounds, w.h.p.

###### Proof.

We show that the total congestion of these algorithms is $\widetilde{O}(D)$,
which immediately yields the result by Theorem 1.8. Consider an edge $e$. By
4.6, there are at most $\widetilde{O}(D)$ pairs $xy\in Q$ such that $e$ is
incident to sets $\mathsf{LDS}(x,y)\cup LDS(y,x)$. Also, by the promise, $e$
is present in $\Pi_{x,y}$ only for $\widetilde{O}(D)$ pairs $xy\in Q$. Thus,
$e$ is used by at most $\widetilde{O}(D)$ algorithms, each of sending
$\widetilde{O}(1)$ messages through it, so the congestion is
$\widetilde{O}(D)$. ∎

##### Description of the Connectivity Algorithm $\mathcal{A}^{P}_{x,y}$.

The algorithm is based on simulating the Borůvka algorithm using the sketch
information of connected subsets in $G\setminus\\{x,y\\}$, held jointly by $x$
and $y$. Throughout, we refer to the given $x$-$y$ path $\Pi_{x,y}$ as _the
$xy$-channel_

The input for phase $i\geq 1$ of Borůvka is the following. There is a
partitioning $\mathcal{P}_{i-1}=\\{P_{i-1,1},\ldots,P_{i-1,k_{i-1}}\\}$ of the
vertices in $V\setminus\\{x,y\\}$ into connected subsets, called _parts_ (to
avoid confusion with the ‘components’ in $\mathcal{C}_{x}$ and
$\mathcal{C}_{y}$). We mark a special vertex in each
$P_{i,j}\in\mathcal{P}_{i}$, called the _leader_ of the part. The leaders are
either some chosen $T$-children of $x$ or $y$ in these parts, or (in some
cases) the source $s$. The part-ID is the ID of its leader. The part
containing $s$ is called the _$s$ -part_. The part containing $x_{h}$ (resp.,
$y_{h}$) is called $x$-_heavy_ (resp., $y$-_heavy_)111111A part can be both
$x$-heavy and $y$-heavy.. The parts that are free of $s,x_{h},y_{h}$ are
called _light_. In the initial partitioning $\mathcal{P}_{0}$, we make sure
that all light parts are contained in $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$
(as will be described later). As the parts only get merged throughout the
Borůvka execution, this remains true also for light parts in
$\mathcal{P}_{i-1}$. A part $P$ is said to be _growable_ if there is an
outgoing $G$-edge connecting $P$ to $V\setminus(P\cup\\{x,y\\})$. The Borůvka
algorithm has $K=O(\log n)$ forest growing phases in $G\setminus\\{x,y\\}$,
where each phase reduces the number of growable parts by a constant factor, in
expectation. We maintain the following invariants for the beginning of each
phase $1\leq i\leq K$, for both $z\in\\{x,y\\}$:

  1. (I1)

$z$ knows $\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ and the part-ID of the
_$s$ -part_ $P\in\mathcal{P}_{i-1}$.

  2. (I2)

$z$ knows $\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ for every _light part_
$P\in\mathcal{P}_{i-1}$ whose leader is in $T_{z}$.

  3. (I3)

$z$ knows $\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ as well as the part-IDs
of all _heavy parts_ $P\in\mathcal{P}_{i-1}$.

  4. (I4)

$z$ knows, for each $T$-child $z^{\prime}$ of $z$, the part-ID of the part
containing $z^{\prime}$ in $\mathcal{P}_{i-1}$.

##### Initialization.

We describe the initialization executed prior to the first Borůvka phase. The
initial parts are defined as the fully-$y$-sensitive components in
$\mathcal{C}_{x}$, the fully $x$-sensitive components of $\mathcal{C}_{y}$,
and another part containing all the rest of the vertices in
$G\setminus\\{x,y\\}$ (and particularly the source $s$). That is, the initial
partitioning is
$\mathcal{P}_{0}=\mathcal{FS}(x,y)\cup\mathcal{FS}(y,x)\cup\\{U(x,y)\\}$,
where the $s$-part $U(x,y)$ is

$U(x,y)=V\setminus\left[\\{x,y\\}\cup\left(\bigcup_{C\in\mathcal{FS}(y,x)\cup\mathcal{FS}(y,x)}C\right)\right].$

Parts from $\mathcal{FS}(x,y)$ or $\mathcal{FS}(y,x)$ are clearly connected,
and $U(x,y)$ is connected by Lemma 4.4. Note that light parts can come only
from $\mathcal{FS}(x,y)\cap\mathsf{LD}(x)\subseteq\mathsf{LDS}(x,y)$ or from
$\mathcal{FS}(y,x)\cap\mathsf{LD}(y)\subseteq\mathsf{LDS}(y,x)$. The leader of
each part $P\in\mathcal{FS}(x,y)$ is chosen as the vertex of largest ID among
all $T$-children of $x$ in $P$, and similarly for parts in
$\mathcal{FS}(y,x)$. The source $s$ is the leader of $U(x,y)$.

The following claim builds on Lemma 4.5 and using the $xy$-channel. All
missing proofs in this section are deferred to Section 4.3.1 on implementation
details.

######  Claim 4.9.

By passing $\widetilde{O}(1)$ messages on the $xy$-channel, $x$ (resp., $y$)
can classify all components in $\mathcal{C}_{x}$ (resp., $\mathcal{C}_{y})$ as
non-, pseudo- or fully-$y$-sensitive (resp., $x$-sensitive).

The sensitivity classification of the last claim easily enables us to “almost”
fulfill invariants (I1-4) w.r.t. $\mathcal{P}_{0}$, only with $G$-sketches
instead of $(G\setminus\\{x,y\\})$-sketches. Formally, we define the
_modified_ conditions (I*1-4) exactly the same as (I1-4), only replacing
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(\cdot)$ with
$\mathsf{sketch}_{G}(\cdot)$ everywhere, and we have:

######  Claim 4.10.

Conditions (I*1-4) can be satisfied for both $z\in\\{x,y\\}$, by passing only
$\widetilde{O}(1)$ messages on the $xy$-channel.

Finally, the following technical claim enables us to end the initialization
step of $\mathcal{A}_{x,y}^{P}$ by transforming the $G$-sketches to
$(G\setminus\\{x,y\\})$-sketches, thus obtaining (I1-4) w.r.t.
$\mathcal{P}_{0}$.

######  Claim 4.11.

Assume that the modified invariants (I*1-4) hold w.r.t. $\mathcal{P}_{0}$.
Then, within $\widetilde{O}(D)$ rounds with congestion $\widetilde{O}(1)$,
where messages are sent only on the $xy$-channel and on edges incident to
$\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$, invariants (I1-4) can be fulfilled
w.r.t. $\mathcal{P}_{0}$.

##### Simulation of the $i^{th}$ Borůvka Phase.

We now describe the execution of phase $i\geq 1$, assuming that at the
beginning of this phase conditions (I1-4) hold w.r.t $\mathcal{P}_{i-1}$. The
output of the phase will be the partitioning $\mathcal{P}_{i}$, for which we
will show conditions (I1-4) hold as well. Our goal is to let $x,y$ simulate a
Borůvka phase in which parts of $\mathcal{P}_{i-1}$ are merged along their
outgoing edges. The main objective of this phase is to reduce the number of
_growable_ parts by a constant factor, in expectation. For efficiency of
computation, we restrict the merges to have star shapes using random coins
(see e.g., [GH16]). Such star merges are obtained by letting each part of
$\mathcal{P}_{i-1}$ toss a random coin, and allowing only merges centered on
head-parts, each accepting incoming suggested merge-edges from tail-parts. The
leader of this head-part becomes the leader of the merged part.

We now discuss the distributed implementation of the merges by the algorithm
$\mathcal{A}_{x,y}^{P}$. Throughout, we use the following auxiliary claim
which allows the vertices in every light part to exchange $\widetilde{O}(1)$
bits, in parallel.

######  Claim 4.12.

Assume that every vertex $v$ belonging to a light part in $\mathcal{P}_{i-1}$
holds a $\widetilde{O}(1)$-bit value $val(v)$. Within $\widetilde{O}(D)$
rounds with $\widetilde{O}(1)$ congestion, where communication is restricted
to edges incident to $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$, the vertices of
each light part $P$ can learn any aggregate function of the values in their
part $\\{val(v)\mid v\in P\\}$.

We divide the responsibility over the parts of $\mathcal{P}_{i-1}$ between $x$
and $y$ by letting each $z\in\\{x,y\\}$ be responsible for the parts whose
leader is inside $T_{z}$. W.l.o.g., we make $x$ also responsible for the
$s$-part in $\mathcal{P}_{i-1}$ in case its leader is $s$. We start by letting
each $z\in\\{x,y\\}$ toss (locally) a fresh random coin for each of the parts
under its responsibility. Denote by $\mathcal{P}_{i-1,z}^{H}$ and
$\mathcal{P}_{i-1,z}^{T}$ the head and tail parts, respectively, for which $z$
is responsible. Next, $z$ locally computes an outgoing edge $(u_{P},v_{P})$
for each of its tail-parts $P\in\mathcal{P}_{i-1,z}^{T}$. Whenever $P$ is
growable, such an edge is detected using
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ with constant probability. The
parts of $\mathcal{P}_{i}$ are formed by merging every head-part $P^{*}$ with
all the tail-parts in $P$ whose outgoing edges point at $P^{*}$. The leader of
the merged part is defined as the leader of the head-part $P^{*}$. The
following claim enables learning the part-IDs and coin-tosses of the parts to
which the outgoing edges point.

######  Claim 4.13.

Within $\widetilde{O}(D)$ rounds with $\widetilde{O}(1)$ congestion, where
communication is restricted to edges incident to
$\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$ and the $xy$-channel, each
$z\in\\{x,y\\}$ can determine for all its tail-parts
$P\in\mathcal{P}_{i-1,z}^{T}$ with an outgoing edge $e_{P}=(u_{P},v_{P})$, the
following information: (i) the part-ID of the second endpoint $v_{P}\notin P$
and, (ii) the coin-toss of the part of $v_{P}$.

The main issue in implementing the merges creating $\mathcal{P}_{i}$ is
letting each $z\in\\{x,y\\}$ to learn the updated sketch information of the
new parts formed by the merges, each identified with its center which is the
corresponding head-part in $\mathcal{P}_{i-1,z}^{H}$. This is shown in the
following claim. For an illustration of the proof, see Figure 3.

######  Claim 4.14.

Within $\widetilde{O}(D)$ rounds with $\widetilde{O}(1)$ congestion, where
communication is restricted to edges incident to
$\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$ and the $xy$-channel, each
$z\in\\{x,y\\}$ can learn the $(G\setminus\\{x,y\\})$-sketch of each part of
$\mathcal{P}_{i}$ whose center is in $\mathcal{P}_{i-1,z}^{H}$.

###### Proof.

We show this for $z=x$, and the proof for $y$ is symmetric. We consider two
types of star centers: non-light and light.

Non-Light Star Centers. These correspond to the non-light parts in
$P_{i-1,x}^{H}$. There are at most three such parts (at most two heavy parts,
and the $s$-part). For each such non-light $P^{*}\in P_{i-1,x}^{H}$, the
sketch of its corresponding star in $\mathcal{P}_{i}$ is

$\displaystyle\mathsf{sketch}_{G\setminus\\{x,y\\}}(P^{*})\oplus\Big{[}\bigoplus_{\begin{subarray}{c}P\in\mathcal{P}_{i-1,x}^{T}\\\
v_{P}\in
P^{*}\end{subarray}}\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)\Big{]}\oplus\Big{[}\bigoplus_{\begin{subarray}{c}P\in\mathcal{P}_{i-1,y}^{T}\\\
v_{P}\in P^{*}\end{subarray}}\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)\Big{]}.$

The first two terms can be computed locally by $x$. The third one, i.e. the
sketch of all $y$-tail-parts pointing to $P^{*}$, can be computed by $y$ and
then sent to $x$ through the $xy$-channel. Thus, $x$ can compute the sum above
and obtain the sketch of the new part for $P^{*}$.

Light Star Centers. It remains to merge the stars centered at _light_ parts in
$\mathcal{P}_{i-1,x}^{H}$. We start by letting $y$ send $x$ the sketches of
the (at most three) non-light tail-parts in $\mathcal{P}_{i-1,y}^{T}$,
together with the part-IDs of their star centers, through the $xy$-channel. At
this point, in order to compute the sketch of a star centered at a light part
$P^{*}\in\mathcal{P}_{i-1,x}^{H}$, it is enough for $x$ to learn the sum-of-
sketches of all _light_ tail-parts in $\mathcal{P}_{i-1}$ whose outgoing edge
point at $P^{*}$, which we denote by $val(P^{*})$. Namely, $x$ is required to
learn

$val(P^{*})=\bigoplus_{\begin{subarray}{c}P\in\mathcal{P}_{i-1,x}^{T}\cup\mathcal{P}_{i-1,y}^{T}\\\
v_{P}\in P^{*}\text{ and $P$ is
light}\end{subarray}}\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$

for each light $P^{*}\in\mathcal{P}_{i-1,x}^{H}$.

This is done as follows. First, each $z\in\\{x,y\\}$ sends to the leader of
each light part $P\in\mathcal{P}_{i-1,z}^{T}$ its sketch
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ and its outgoing edge
$(u_{P},v_{P})$. This information is then broadcasted over each light tail-
part, in parallel, using 4.12. Then, the $u_{P}$ vertices of the light tail-
parts send this information to their $v_{P}$ neighbors. At this point, for
each light star center $P^{*}\in\mathcal{P}_{i-1,x}^{H}$, the sketch of each
light tail-part $P\in\mathcal{P}_{i-1}$ which points at $P^{*}$ is held by
exactly one vertex $v_{P}\in P^{*}$ (the same vertex can be holding several
such sketches). Thus, each $v\in P^{*}$ can locally compute

$val(v)=\bigoplus_{\begin{subarray}{c}P\in\mathcal{P}_{i-1,x}^{T}\cup\mathcal{P}_{i-1,y}^{T}\\\
\text{$P$ is light and
$v=v_{P}$}\end{subarray}}\mathsf{sketch}_{G\setminus\\{x,y\\}}(P).$

These values are summed on each light star center
$P^{*}\in\mathcal{P}_{i-1,x}^{H}$ in parallel using 4.12, letting all vertices
of $P^{*}$ learn $\bigoplus_{v\in P^{*}}val(v)=val(P^{*})$. The leaders of the
light star centers $P^{*}\in\mathcal{P}_{i-1,x}^{H}$ can now send this
information to $x$, as required. ∎

Figure 3:  Illustration of the first Borůvka phase in algorithm
$\mathcal{A}^{P}_{x,y}$. Here, we assume each subtree of $x$ and $y$ forms a
distinct component in $\mathcal{C}_{x}$ and $\mathcal{C}_{y}$, respectively.
The components in $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$ are striped
triangles. The heavy components are squares. The non-sensitive or pseudo-
sensitive components are part of the $s$-part $U(x,y)$. The solid arrows
correspond to the outgoing edges obtained from tail parts, pointing to head
parts. The sketches of components $C_{y,y_{2}}$ and $C_{x,x_{1}}$ are merged
via communication of the outgoing edge connecting them. The sum-of-sketches of
${C_{y,y_{1}}}$ and $H_{y}$ is sent from $y$ to $x$ on the $xy$-channel
$\Pi_{x,y}$, allowing it to merge them with $H_{x}$.

Finally, we show how conditions (I1-4) are satisfied w.r.t. $\mathcal{P}_{i}$.
Condition (I2) is immediate by 4.14. We next show conditions (I1) and (I3). In
order for $x,y$ to learn the part-IDs of the non-light parts in the new
partition $\mathcal{P}_{i}$, it is enough for them to learn the new part-ID
given to each of the (at most three) non-light parts in the previous partition
$P\in\mathcal{P}_{i-1}$. The vertex $z\in\\{x,y\\}$ which is responsible for
$P$ knows its new-part ID by 4.13 (and knows that $P$ is the $s$-part,
$x_{h}$-part and/or $y_{h}$-part by (I1) and (I3) w.r.t. $\mathcal{P}_{i-1}$),
so $z$ can share this over the $xy$-channel. Now, the
$(G\setminus\\{x,y\\})$-sketches of each non-light part in the new partition
$\mathcal{P}_{i}$ is known to either $x$ or $y$ by 4.14, and sharing them over
the $xy$-channel yields (I1) and (I3) w.r.t. $\mathcal{P}_{i}$. Lastly, we
show condition (I4). Let $z\in\\{x,y\\}$, let $z^{\prime}$ be a child of $z$.
By (I4) w.r.t. $\mathcal{P}_{i-1}$, $z$ knows to which part $z^{\prime}$
belongs in $\mathcal{P}_{i-1}$. If this part is non-light, then the new part-
ID (of the part containing $z^{\prime}$ in $\mathcal{P}_{i}$) is known by the
previous step handling (I1) and (I3). It remains to handle the case where
$z^{\prime}$ belongs to a light part in $\mathcal{P}_{i-1}$. For this, we let
$x,y$ inform the leaders of light parts under their responsibility in
$\mathcal{P}_{i-1}$ of their new part-ID in $\mathcal{P}_{i}$ (which $x,y$
know by 4.13), and this information is broadcasted in parallel on all light
parts in $\mathcal{P}_{i-1}$ using 4.12. This informs each such $z^{\prime}$
of its part-ID, and by sending it to $z$ we establish (I4) w.r.t.
$\mathcal{P}_{i}$.

We are now ready to conclude the description of the algorithm
$\mathcal{A}_{x,y}^{P}$ and prove Theorem 4.7.

###### Proof of Theorem 4.7.

We have shown that the initialization of $\mathcal{A}_{x,y}^{P}$ and each of
the Borůvka phases are implemented in $\widetilde{O}(D)$ rounds with
$\widetilde{O}(1)$ congestion, where communication is restricted only to edges
incident to $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$ and the $xy$-channel.
Next, we assert that the number of growable part reduces by a constant factor
in each phase, in expectation. Indeed, given a sketch information
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$ for a growable part $P$, one can
infer an outgoing edge $(u,v)$ from $P$ with constant probability. In
addition, with probability $1/4$ this edge is valid (i.e., $P$ is a tail part
and $v$ is in a head part). We now deduce, by Markov’s inequality, that w.h.p.
there is no growable part after $K=O(\log n)$ phases, so $\mathcal{P}_{K}$ are
maximal connected components in $G\setminus\\{x,y\\}$. As $x,y$ jointly hold
the part-IDs of all parts in $\mathcal{P}_{K}$, they can use the $xy$-channel
to determine if there is more than one such part. The theorem follows. ∎

####  4.3.1 Implementation Details for Section 4.3

###### Proof of 4.9.

W.l.og., we show this only for $x$. Recall that $x$ can classify each
component in $\mathcal{C}_{x}$ as $y$-sensitive or not using
$\widehat{T}_{x}$. Furthermore, by Lemma 4.5, each $y$-sensitive component
$C\neq H_{x}$ can be further classified as pseudo- or fully-$y$-sensitive. It
remains to classify $H_{x}$. By Lemma 4.5, a problem in doing so occurs only
if $(y,y_{h})\in\pi_{x}(s,H_{x})$. In this case, to classify $H_{x}$ as
pseudo- or fully-$y$-sensitive, it is enough for $x$ to learn
$\pi_{y}^{*}(s,C_{y,y_{h}})=\pi_{y}^{*}(s,H_{y})$. This $\widetilde{O}(1)$-bit
information can be passed to $x$ from $y$ over the $xy$-channel. ∎

###### Proof of 4.10.

W.l.o.g., we show this for $z=x$.

  1. (Ienumi1)

The sketch of the $s$-part in $\mathcal{P}_{0}$ is

$\displaystyle\mathsf{sketch}_{G}(U(x,y))=$
$\displaystyle\Big{[}\mathsf{sketch}_{G}(V)\oplus\mathsf{sketch}_{G}(x)\oplus\Big{(}\bigoplus_{C\in\mathcal{FS}(x,y)}\mathsf{sketch}_{G}(C)\Big{)}\Big{]}$
$\displaystyle\oplus$
$\displaystyle\Big{[}\mathsf{sketch}_{G}(y)\oplus\Big{(}\bigoplus_{C\in\mathcal{FS}(y,x)}\mathsf{sketch}_{G}(C)\Big{)}\Big{]}.$

The first and second square-bracketed terms can be computed locally by $x$ and
$y$, respectively, by 4.9. By exchanging these terms over the $xy$-channel,
and adding them up, both $x,y$ learn $\mathsf{sketch}_{G}(U(x,y))$. The part-
ID is the ID of $s$.

  2. (Ienumi2)

A light part in $\mathcal{P}_{0}$ whose leader is in $T_{x}$ is simply a
component $C\in\mathcal{FS}(x,y)$, and $x$ holds the $G$-sketches of such
components.

  3. (Ienumi3)

We first let $x,y$ exchange $\mathsf{sketch}_{G}(H_{x})$ and
$\mathsf{sketch}_{G}(H_{y})$, and the largest ID of their $T$-children in
$H_{x}$ and $H_{y}$, over the $xy$-channel. Now, a heavy part in
$\mathcal{P}_{0}$ can be either $U(x,y)$, $H_{x}$ or $H_{y}$, so its
$G$-sketch and its part-ID is known to both $x,y$.

  4. (Ienumi4)

Let $x^{\prime}$ be a $T$-child of $x$. If
$C_{x,x^{\prime}}\in\mathcal{FS}(x,y)$ (which $x$ knows by 4.9), then the
part-ID for $x^{\prime}$ is the largest vertex ID of a $T$-child of $x$ in
$C_{x,x^{\prime}}$. Else, $C_{x,x^{\prime}}\subseteq U(x,y)$, so the part-ID
for $x^{\prime}$ is the ID of $s$.

∎

###### Proof of 4.11.

We show (I1-4) for $x$, and the proof for $y$ is symmetric. We start by
letting all $y$-adjacent vertices in $\mathsf{LDS}(x,y)$ send messages to $y$
informing it that they belong to $\mathsf{LDS}(x,y)$ (which they know by Lemma
4.3). This suffices for $y$ to locally compute the following information
(where $E(y,S)$ denotes the set of edges connecting $y$ to a vertex in
$S\subseteq V$):

  1. 1.

$\mathsf{csketch}(E(y,V(T_{x^{\prime}})))$ for every $T$-child $x^{\prime}$ of
$x$ such that $x^{\prime}\in\mathsf{LDS}(x,y)$.

  2. 2.

$\mathsf{csketch}(E(y,V(T_{x_{h}})))$.

  3. 3.

$\mathsf{csketch}(E(y,\mathsf{LD}(x)\setminus\mathsf{LDS}(x,y)))$.

  4. 4.

$\mathsf{csketch}(E(y,U(x,y)\setminus V(T_{x})))$.

Next, we pass the above information to $x$, as follows. Items 2-4 consist only
of $\widetilde{O}(1)$ bits, so they can be sent through the $xy$-channel. To
handle item 1, we let $y$ send $\mathsf{csketch}(E(y,V(T_{x^{\prime}})))$ to
an arbitrary neighbor $v_{x^{\prime}}\in T_{x^{\prime}}$, for each
$x^{\prime}$ which is a $T$-child of $x$ satisfying
$x^{\prime}\in\mathsf{LDS}(x,y)$ (and $E(y,V(T_{x^{\prime}}))\neq\emptyset$).
These cancel-sketches are propagated upwards from the $v_{x^{\prime}}$
vertices to $x$ in parallel, on the disjoint tree paths
$\pi(x,v_{x^{\prime}})$, which contain only edges incident to
$\mathsf{LDS}(x,y)$. By the end of this process, $x$ has all the information
of item 1.

We are now ready to show (I1-3) (note that (I4) is trivial as it is the same
as (I*4)).

Consider first a light part $P\in\mathcal{FS}(x,y)$. Then $x$ can XOR its
sketch $\mathsf{sketch}_{G}(P)$ with
$\mathsf{csketch}(E(y,V(T_{x^{\prime}})))$ for every $T$-child $x^{\prime}$ of
$x$ such that $x^{\prime}\in P$, using (I*4) and the information of item 1,
thus eliminating all $y$-incident edges of $P$. For the same $x^{\prime}$
vertices, it can further XOR this sketch with
$\mathsf{csketch}(E(x,V(T_{x^{\prime}})))$, which is easily computed locally.
This eliminates also the $x$-incident edges of $P$, yielding
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(P)$. This shows (I2).

Next, consider the case where $H_{x}\in\mathcal{FS}(x,y)$, namely $H_{x}$ is
the heavy part. Then $H_{x}$ is the union of the vertices in $T_{x_{h}}$ and
in some subtrees $T_{x^{\prime}}$ of $T$-children $x^{\prime}$ of $x$ such
that $x^{\prime}\in\mathsf{LDS}(x,y)$. Therefore, $x$ can compute
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{x})$ in the same manner done for
light parts, but also using the information of item 2. If
$H_{y}\in\mathcal{FS}(y,x)$, then a symmetric procedure can be applied by $y$,
and then $\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{y})$ is sent to $x$ over
the $xy$-channel. This shows (I3) (except for cases where the $s$-part is also
a heavy part, but these are treated by (I1) next).

Finally, consider the $s$-part $U(x,y)$. We show how $x$ can compute the
cancellation-sketch of all edges $E(y,U(x,y))$. First, $x$ adds-up the
cancellation-sketches of edges in
$E(y,\mathsf{LD}(x)\setminus\mathsf{LDS}(x,y)))$ and $E(y,U(x,y)\setminus
V(T_{x}))$ from items 3 and 4. Next, in case $x_{h}\in U(x,y)$ (which $x$
knows by (I*4)), $x$ also adds the cancellation-sketch of $E(y,V(T_{x_{h}}))$
from item 3. At this point, it remains to add the cancellation-sketches of
edges going from $y$ to $V(T_{x^{\prime}})$ for every light $T$-child
$x^{\prime}$ of $x$ such that $C_{x,x^{\prime}}$ is pseudo-$y$-sensitive (and
therefore, $x^{\prime}\in\mathsf{LDS}(x,y)$). Note that $x$ can determine all
such $x^{\prime}$ children using 4.9 and (I*4), and add up the corresponding
cancellation-sketches from item 1. This yields
$\mathsf{csketch}(E(y,U(x,y)))$. A symmetric procedure allows $y$ to compute
$\mathsf{csketch}(E(x,U(x,y)))$, and then send it to $x$ through the
$xy$-channel. By XORing these last two cancellation sketches with
$\mathsf{sketch}_{G}(U(x,y))$, $x$ can obtain
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(U(x,y))$. This shows (I1). ∎

###### Proof of Claim 4.12.

First, all vertices belonging to light parts can be informed of their part-ID,
by propagating the information of invariant (I4) from $x,y$ to the subtrees of
their children in light parts. By exchanging this information along neighbors,
each vertex in a light part learns all its neighbors with the same part-ID. We
will give a procedure for computing the aggregated value of any specific light
part $P\in\mathcal{P}_{i-1}$, using only edges from $P\times(P\cup\\{x,y\\})$.
Note that the edges used for different light parts are disjoint, and consist
only of edges incident to $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. Hence, the
procedures for all light parts can be executed in parallel.

It remains to describe the aforementioned procedure for some light part
$P\in\mathcal{P}_{i-1}$. Let $P_{x}=P\cap V_{x}$ and $P_{y}=P\cap V_{y}$. Note
that $P_{x}$ is the union of $T_{x^{\prime}}$ subtrees, for the $T$-children
$x^{\prime}$ of $x$ in $P$. We start by aggregating the $val(v)$ values, in
parallel, in each such $T_{x^{\prime}}$ subtree. Each such $x^{\prime}$ then
sends the aggregated value of $T_{x^{\prime}}$ to $x$. This allows $x$ to
compute the aggregated value of $P_{x}$, which we denote by $val(P_{x})$. This
value is then broadcasted down the same subtrees, so it is learned by all
vertices in $P_{x}$. A symmetric procedure allows the vertices of $P_{y}$ to
learn $val(P_{y})$. If any of $P_{x}$ or $P_{y}$ are empty, then we are done.
Otherwise, $val(P_{x})$ and $val(P_{y})$ are exchanged along the edges in
$P_{x}\times P_{y}$ (at least one such edge must exist, as the part $P$ is
connected). This information is propagated upwards to $x$ and $y$ by the
endpoint of these edges (ignoring repeated messages). Then, both $x,y$ can
compute the final aggregated value $val(P)$, and broadcast it in parallel on
each of their subtrees contained in $P$, concluding the procedure. ∎

###### Proof of Claim 4.13.

We show this for $z=x$, and the proof for $z=y$ is similar. Consider first the
(at most three) non-light tail-parts $P\in\mathcal{P}_{i-1,x}^{T}$. By using
the $\mathsf{anc}_{T}$-labels of the endpoints of $e_{P}$ (found in the
$\mathsf{eid}_{T}(e_{P})$), $x$ can determine if they lie in $V(T_{x})$, in
$V(T_{y})$, or in $V\setminus(V(T_{x})\cup V(T_{y}))$. The part-IDs of
endpoints in $V(T_{x})$ can be determined by $x$ using (I4). The part-ID of
endpoints in $V\setminus V(T_{x})\cup V(T_{y})$ is the part-ID of the
$s$-part, known to $x$ by (I1). In order to learn the part-IDs of the
remaining endpoints in $V(T_{y})$, $x$ sends all (at most six) such endpoints
to $y$ through the $xy$-channel, and $y$ can determine their part-IDs using
(I4) and report them back to $x$. At this point, $x$ has the information of
(i) for its non-light tail-parts, i.e. it knows to which parts their outgoing
edges point. If the coin-toss of such a pointed part is not known to $x$, then
it can query $y$ for it using the $xy$-channel. This establishes (ii) for non-
light $P\in\mathcal{P}_{i-1,x}^{T}$.

It remains to handle the light tail-parts in $\mathcal{P}_{i-1,x}^{T}$. First,
we let each vertex in $\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$ learn its part-
ID. This is done by using (I4) and broadcasting the information from $x,y$
along the subtrees of $T_{x}$ of $T_{y}$ whose union consists of
$\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$. Next, each $z\in\\{x,y\\}$ sends to
the leaders of _light_ parts lying in $T_{z}$ their part-ID, coin-toss, and
also the outgoing edge in case the latter is tail. This information is then
broadcasted on all light parts in parallel using 4.12. Within additional
$\widetilde{O}(1)$ rounds, the $u_{P}$ vertices of light tail-parts inform
their $v_{P}$ neighbors of this information. The $v_{P}$ vertices then reply
by one of the three following options, where $P^{\prime}$ is the part
containing $v_{P}$.

  1. 1.

The part-ID and coin-toss of $P^{\prime}$. This happens if $P^{\prime}$ is a
light part.

  2. 2.

Only the part-ID of $P^{\prime}$. This happens if
$v_{P}\in\mathsf{LDS}(x,y)\cup\mathsf{LDS}(y,x)$, but $P^{\prime}$ is non-
light.

  3. 3.

A null message. This happens in all remaining cases.

The replies, along with the identity of the $v_{P}$ vertices, are then
broadcasted on the light parts using 4.12, and sent to $x$ from the leaders of
each tail-part $P\in\mathcal{P}_{i-1,x}^{T}$. If $v_{P}$ replied with option
1, then clearly $x$ learns both (i) and (ii) for $P$. As $x,y$ can share the
coin-tosses of all (at most three) non-light parts on the $xy$-channel, $x$
can learn (i) and (ii) also if $v$ replied with option 2. Finally, assume
$v_{P}$ responded with option 3. In case $v_{P}\in V(T_{x_{h}})$ (which $x$
can detect using $\mathsf{anc}_{T}(v_{P})$), then $v_{P}$ belongs to the
$x$-heavy part. If $v_{P}\in V(T_{y_{h}})$, then $v_{P}$ belongs to the
$y$-heavy part. Otherwise, $v_{P}$ must belong to $U(x,y)$, and thus to the
$s$-part in $\mathcal{P}_{i-1}$, as it can either be outside $V(T_{x})$ and
$V(T_{y})$, or in a non-sensitive component in
$\mathcal{C}_{x}\cup\mathcal{C}_{y}$. As the part-IDs of the non-light parts
are known to $x$ by (I1) and (I3), and their coin-tosses are also known (as in
option 2), this yields (i) and (ii) also when $v_{P}$ responds with option 3.
∎

###  4.4 Omitting the Promise

Our goal now is omitting the promise of Section 4.3. To this end, we first
classify the independent pairs into two types, light and heavy, defined next.
In this section, it is convenient to have the distinction between unorderd and
ordered pairs (which was not significant in previous sections). We denote
unordered pairs by $xy$, and ordered pairs by $\langle x,y\rangle$.

######  Definition 4.3 (Light and Heavy Pairs).

An ordered independent pair $\langle x,y\rangle$ is called an _ordered light
pair_ if there exists a component $C\in\mathcal{C}_{x}$ for which one of the
following holds:

  * •

$\pi_{x}(s,C)$ contains a _light_ $T$-edge $(y,y^{\prime})$ such that
$x\in\pi_{y}(s,C_{y,y^{\prime}})$.

  * •

$y=u_{C}$. (Recall that $(u_{C},v_{C})$ is the last edge of $\pi_{x}(s,C)$,
with $v_{C}\in C$, see beginning of Section 4.)

Equivalently, $\langle x,y\rangle$ is an ordered light pair if there is exists
a fully-$y$-sensitive component $C\in\mathcal{FS}(x,y)$ for which
$(y,y_{h})\notin\pi_{x}(s,C)$.

An (unordered) independent pair $xy$ is called a _light pair_ if at least one
of its orderings $\langle x,y\rangle,\langle y,x\rangle$ is an ordered light
pair. Otherwise, it is called a _heavy pair_.

Figure 4:  Top: A light $xy$ pair. $C_{x,x_{2}}$ is a fully-$y$-sensitive
component lying below the light edge $(y,y_{1})$ in $\widehat{T}_{x}$. Bottom:
A heavy $xy$ pair. All fully-$y$-sensitive components in $\mathcal{C}_{x}$ lie
below the heavy edge $(y,y_{h})$ in $\widehat{T}_{x}$, and vice-versa.

By negating the definition of light pairs, we immediately get:

######  Observation 4.15.

An independent pair $xy$ is a heavy pair iff both of the following hold:

  * •

$C\in\mathcal{FS}(x,y)\implies(y,y_{h})\in\pi_{x}(s,C)$, and

  * •

$C\in\mathcal{FS}(y,x)\implies(x,x_{h})\in\pi_{y}(s,C).$

See Figure 4 for an illustration of light and heavy pairs.

####  4.4.1 Light Pairs

For every ordered light pair $\langle x,y\rangle$, we choose some arbitrary
component $C^{\langle x,y\rangle}\in\mathcal{FS}(x,y)$ such that
$(y,y_{h})\notin\pi_{x}(s,C^{\langle x,y\rangle})$, which exists by Definition
4.3, and define _the $\langle x,y\rangle$-channel_ by

$\displaystyle\Pi_{\langle x,y\rangle}=\pi(x,v_{C^{\langle
x,y\rangle}})\circ(v_{C^{\langle x,y\rangle}},u_{C^{\langle
x,y\rangle}})\circ\pi(u_{C^{\langle x,y\rangle}},y)~{}.$

Let

$\mathcal{P}_{light}=\\{\Pi_{\langle x,y\rangle}\mid\text{$\langle x,y\rangle$
is an ordered light pair}\\}.$

The following lemmas show that this path collection satisfies the promise, and
can be efficiently learned in a distributed manner.

######  Lemma 4.16.

The path collection $\mathcal{P}_{light}$ satisfies the promise. That is, each
path in $\mathcal{P}_{light}$ has length $O(D)$, and each $G$-edge appears in
at most $\widetilde{O}(D)$ many paths from $\mathcal{P}_{light}$.

###### Proof.

The length bound is immediate. For the second condition, it is enough to prove
that every vertex in $G$ appears _as an internal vertex_ in at most
$\widetilde{O}(D)$ many paths from $\mathcal{P}_{light}$. We first observe
that for an internal vertex $a\in\Pi_{\langle x,y\rangle}$, the following hold
by the properties of $C^{\langle x,y\rangle}$:

  1. 1.

If $a\in\pi(x,v_{C^{\langle x,y\rangle}})$, then $x$ is an ancestor of $a$,
and $y\in\mathsf{LA}(u_{C_{x,a}})\cup\\{u_{C_{x,a}}\\}$ (as
$C_{x,a}=C^{\langle x,y\rangle}$).

  2. 2.

If $a\in\pi(u_{C^{\langle x,y\rangle}},y)$, then $y\in\mathsf{LA}(a)$, and
$x\in\pi_{y}(s,C_{y,a})$ (as $C_{y,a}=C_{y,y^{\prime}}$, where
$(y,y^{\prime})\in\pi_{x}(s,C^{\langle x,y\rangle})$ is a light $T$-edge).

By the first observation, each vertex $a$ can be internal in $\Pi_{\langle
x,y\rangle}$ and appear on the first segment for $O(D)$ different $x$
vertices, and for $O(\log n)$ different $y$ vertices for each such $x$. From
the second observation, $a$ can be internal in $\Pi_{\langle x,y\rangle}$ and
appear in the last segment for $O(\log n)$ different $y$ vertices, and $O(D)$
different $x$ vertices for each such $y$. So, overall $a$ can be an internal
vertex in at most $O(D\log n)$ paths from $\mathcal{P}_{light}$. ∎

######  Lemma 4.17.

There is a randomized $\widetilde{O}(D)$-round algorithm such that w.h.p., for
every ordered light pair $\langle x,y\rangle$, both $x$ and $y$ are informed
of their pairing and of the vertices $v_{C^{\langle x,y\rangle}},u_{C^{\langle
x,y\rangle}}$. Consequently, $x$ and $y$ can route messages to each other on
$\Pi_{\langle x,y\rangle}$.

###### Proof.

First, observe that each vertex $x$ can identify all vertices $y$ such
$\langle x,y\rangle$ is a light ordered pair, and choose the corresponding
component $C^{\langle x,y\rangle}$, by using the information of its
connectivity tree $\widehat{T}_{x}$ and of Lemma 4.5. The vertices
$v_{C^{\langle x,y\rangle}},u_{C^{\langle x,y\rangle}}$ can also be identified
by $x$ from $\pi_{x}(s,C^{\langle x,y\rangle})$. Hence, our goal is to supply
the $y$ vertices of each ordered light pair $\langle x,y\rangle$ with all the
required information, which is the list $I_{\langle x,y\rangle}=[\langle
x,y\rangle,v_{C^{\langle x,y\rangle}},u_{C^{\langle x,y\rangle}}]$ consisting
of $\widetilde{O}(1)$ bits (recall that each vertex is identified with its
compressed-path, i.e. its $\mathsf{anc}_{T}$-label). We do this by routing the
message $I_{\langle x,y\rangle}$ from the source $x$ to target $y$ along
$\Pi_{\langle x,y\rangle}$. Note that any vertex in $\Pi_{\langle
x,y\rangle}$, upon receiving the message $I_{\langle x,y\rangle}$, can
determine the next edge of $\Pi_{\langle x,y\rangle}$ along which $I_{\langle
x,y\rangle}$ should be routed, by using the $\mathsf{anc}_{T}$-labels found in
$I_{\langle x,y\rangle}$. Thus, we essentially have an instance of the packet-
routing problem, where the source-target pairs, are the ordered light pairs
$\langle x,y\rangle$, the packets are the messages $I_{\langle x,y\rangle}$,
and the paths are the channels $\Pi_{\langle x,y\rangle}$ respectively. The
dilation and congestion are both $\widetilde{O}(D)$ by Lemma 4.16. Hence, we
can use the scheduling of Theorem 1.8 to execute this packet-routing instance
within $\widetilde{O}(D)$, w.h.p. ∎

Finally, by combining Lemmas 4.16 and 4.17 with Corollary 4.8, we get that
within $\widetilde{O}(D)$-rounds, w.h.p. all ordered light pairs (and thus,
also the unordered light pairs) can determine if they form a cut pair in $G$.

####  4.4.2 Heavy Pairs

We now consider the more challenging task of connectivity checking for heavy
pairs. Our strategy is based on classifying these pairs further as _mutual_
and _non-mutual_. The special configuration of mutual pairs is dealt with in a
similar fashion to light pairs, namely, implementing the promise for the
algorithm of Section 4.3 by choosing bounded-congestion communication
channels. Perhaps surprisingly, for the remaining non-mutual pairs it is
sufficient for the vertices to collect a small amount of information over the
tree $T$, which enables every non-mutual pair $xy$ to determine the
connectivity of $G\setminus\\{x,y\\}$ by local computation in $x$ or $y$.

We start with some preliminary notions required for our definition of mutual
pairs. For a vertex $x\in V$, let $R(x)=\\{v\in V\setminus
V(T_{x})\mid\text{$v$ has a neighbor in $H_{x}$}\\}$, and let $r(x)$ be the
lowest common ancestor of the vertices in $R(x)$ (w.r.t. $T$). Observe that
for the last edge $(u_{H_{x}},v_{H_{x}})$ of $\pi_{x}(s,H_{x})$ we have
$u_{H_{x}}\in V\setminus V(T_{x})$ and $v_{H_{x}}\in H_{x}$, hence
$u_{H_{x}}\in R(x)$. As $r(x)$ is an ancestor of any vertex in $R(x)$, we
obtain that $r(x)\in\pi(s,u_{H_{x}})$.

######  Definition 4.4.

A heavy pair $xy$ is called a _mutual pair_ if $r(x)=y$ and $r(y)=x$.
Otherwise, $xy$ is a _non-mutual pair_.

The following claim concerns the collection of preliminary information
required for the connectivity algorithm of both mutual and non-mutual pairs.

######  Claim 4.18.

Within $\widetilde{O}(D)$ rounds, w.h.p. each $x\in V$ learns $r(x)$ and the
following information for every $y\in V(\widehat{T}_{x})$: (i) $r(y)$, (ii)
$\pi_{y}^{*}(s,H_{y})$, and (iii)
$\mathsf{sketch}_{G\setminus\\{y\\}}(H_{y})$.

###### Proof.

We first describe the procedure letting each $x$ learn $r(x)$. For a (non-
empty) $U\subseteq V$, denote by $\operatorname{LCA}(U)$ the lowest common
ancestor of all vertices in $U$. We first importantly note that
$\operatorname{LCA}$ is an aggregate function. Also, note that given the
compressed-paths of the vertices in $U$, the compressed-path of
$\operatorname{LCA}(U)$ can be deduced. Next, observe that a vertex $a$ can
use the known compressed-paths of its $G$-neighbors to locally determine which
of them belong to $V\setminus V(T_{x})$, for each of its ancestors
$x\in\pi(s,a)$. Hence, by executing bottom-up $\operatorname{LCA}$-aggregation
on $T$ and using standard pipeline techniques, within $\widetilde{O}(D)$
rounds each vertex $a$ can learn, for each of its ancestors $x\in\pi(s,a)$,
the compressed-path of

$\ell_{x,a}:=\operatorname{LCA}(\\{v\in V\setminus V(T_{x})\mid\text{$v$ has a
neighbor in $V(T_{a})$}\\}).$

Within another $\widetilde{O}(1)$ rounds, each vertex $x$ can learn, for each
of its $T$-children $x^{\prime}$, the compressed-path of
$\ell_{x,x^{\prime}}$. By Lemma 4.1, $x$ can detect which of its children
$x^{\prime}$ belongs to $H_{x}$, and thus it can locally compute the
compressed path of $r(x)$, since it holds that

$r(x)=\operatorname{LCA}(\\{\ell_{x,x^{\prime}}\mid\text{$x^{\prime}$ is a
$T$-child of $x$ inside $H_{x}$}\\}).$

This compressed-path enables $x$ to locate $r(x)$ in the tree
$\widehat{T}_{x}$ (stored locally at $x$ by Lemma 4.2).

To finish the proof, it remains to show the procedure letting each $x$ learn
the information
$I_{y}=[r(y),\pi_{y}^{*}(s,H_{y}),\mathsf{sketch}_{G\setminus\\{y\\}}(H_{y})]$
for every $y\in V(\widehat{T}_{x})$. We first observe that each vertex $y$
holds $I_{y}$: The vertex $r(y)$ is known to $y$ by the previous part of the
proof. $\pi_{y}^{*}(s,H_{y})$ is known from $\widehat{T}_{y}$ (by Lemma 4.2).
$\mathsf{sketch}_{G\setminus\\{y\\}}(H_{y})$ is obtained from
$\mathsf{sketch}_{G}(H_{y})$ by Lemma 1.7. We let every vertex $y$ exchange
$I_{y}$ with its neighbors. By propagating this information down on $T$ in a
pipeline manner, each vertex $v$ learns $I_{y}$ for every $y\in\pi(s,v)$,
within $\widetilde{O}(D)$ rounds. Finally, we run again Step 2 of the
procedure for computing connectivity trees $\widetilde{T}_{x}$ in Section 4.1
(with the same random seeds), only now augmenting the path-sketches further by
including next to each stored path $\pi(s,u)$ the additional
$\widetilde{O}(D)$ information of $I_{y}$ for each $y\in\pi(s,u)$. This lets
$x$ learn $I_{y}$ for all vertices $y$ in the paths included in
$\widehat{T}_{x}$ (which are obtained by the path-sketches), as required. ∎

##### Handling Mutual Pairs.

The mutual pairs $xy$ are handled almost exactly as the light pairs, by
defining $xy$ channels satisfying the promise for the connectivity algorithms
of Section 4.3.

First, notice that for a mutual pair $xy$, both $x$ and $y$ know the identity
of their mutual-mate by 4.18. To break the symmetry between $x$ and $y$, we
assume w.l.o.g. that $x$ has the smaller ID, and define the $xy$ channel as

$\Pi_{x,y}=\pi(x,v_{H_{x}})\circ(v_{H_{x}},u_{H_{x}})\circ\pi(u_{H_{x}},y).$

Let $\mathcal{P}_{mutual}=\\{\Pi_{x,y}\mid\text{$xy$ is a mutual pair}\\}$.
Note that the mutual pairs form a matching in the sense, each vertex $x$
appears in at most one mutual pair (i.e., $xr(x)$).

We assert that $\mathcal{P}_{mutual}$ satisfies the promise. The fact that
each path has length $O(D)$ is clear. Next, consider any vertex $a$. Then $a$
can appear in the first segment of a $\mathcal{P}_{mutual}$-path
$\Pi_{x,y}=\Pi_{x,r(x)}=\Pi_{r(y),y}$ only if $x\in\pi(s,a)$, and in the
second segment only if $y\in\pi(s,a)$. Thus, each vertex $a$ can appear in at
most $O(D)$ many $\mathcal{P}_{mutual}$-paths, hence this is also true for
edges.

By applying a procedure identical to Lemma 4.17 (only replacing $u_{C^{\langle
x,y\rangle}}$ and $v_{C^{\langle x,y\rangle}}$ there with $u_{H_{x}}$ and
$v_{H_{x}}$, respectively), we make sure that each mutual pair $xy$ can route
messages on their channel $\Pi_{x,y}$. Corollary 4.8 then applies with $Q$
being the set of all mutual pairs, hence within $\widetilde{O}(D)$ rounds,
w.h.p. each such $xy$ pair determines the connectivity of
$G\setminus\\{x,y\\}$.

##### Handling Non-Mutual Pairs.

Finally, we turn to handle the remaining non-mutual pairs. We will show that
for each such pair $xy$, one of $x,y$ can apply a local computation for
determining the connectivity of $G\setminus\\{x,y\\}$. To this end, we start
with an observation regarding heavy pairs.

######  Observation 4.19.

Let $xy$ be a heavy pair. Then $G\setminus\\{x,y\\}$ is connected iff there is
some $z_{h}\in\\{x_{h},y_{h}\\}$ that is connected to the source $s$ in
$G\setminus\\{x,y\\}$.

###### Proof.

The ‘only if’ direction is trivial. We show the ‘if’ direction for
$z_{h}=y_{h}$ (the case $z_{h}=x_{h}$ is symmetric). By Lemma 4.4, the only
vertices that can disconnect from $s$ in $G\setminus\\{x,y\\}$ are those of
components in $\mathcal{FS}(x,y)\cup\mathcal{FS}(y,x)$.

Consider first a component $C\in\mathcal{FS}(x,y)$. By 4.15, it holds that
$(y,y_{h})\in\pi_{x}(s,C)$. Hence, in $G\setminus\\{x,y\\}$, it is possible to
get from $s$ to $C$ in $G\setminus\\{x,y\\}$ by first walking to $y_{h}$, and
then continuing along $\pi_{x}(s,C)$. We can now conclude that all vertices in
$V_{x}$ are connected to $s$ in $G\setminus\\{x,y\\}$.

Finally, consider a component $C\in\mathcal{FS}(y,x)$. By 4.15, it holds that
$(x,x_{h})\in\pi_{y}(s,C)$. Then, as $x_{h}\in V_{x}$, it is possible to get
from $s$ to $C$ in $G\setminus\\{x,y\\}$ by first walking to $x_{h}$, and then
continuing along $\pi_{y}(s,C)$. ∎

Fix some vertex $x$. By the observation above, if $xy$ is a heavy-pair such
that $G\setminus\\{x,y\\}$ is disconnected, then it must be that
$y\in\pi_{x}(s,H_{x})$. By Lemma 4.17, $x$ knows all of its light-mates, hence
it can determine all its heavy-mates $y\in\pi_{x}(s,H_{x})$. We will show that
for any heavy-mate $y\in\pi_{x}(s,H_{x})$ such that $r(x)\neq y$, $x$ can
determine the connectivity of $G\setminus\\{x,y\\}$ by local computation
(after $\widetilde{O}(D)$ rounds of common preprocessing for all vertices).
This implies that at least one vertex of every non-mutual pair can determine
if it is a cut pair, as desired.

First, we assert that $x$ can disregard all heavy-mates $y$ lying (strictly)
below $r(x)$ in $\pi_{x}(s,H_{x})$, by the following observation.

######  Observation 4.20.

Let $x\in V$. If $y$ is a vertex lying below $r(x)$ in $\pi(s,u_{H_{x}})$,
then the source $s$ is connected to $H_{x}$ in $G\setminus\\{x,y\\}$.

###### Proof.

First note that $y$ cannot be an ancestor of all vertices in $R(x)$, since
this would contradict $r(x)$ being the lowest such vertex. Hence, there exists
some $a\in R(x)$ such that $y\notin\pi(s,a)$. By definition of $R(x)$, $a\in
V\setminus V(T_{x})$, and $a$ has a neighbor $b$ inside $H_{x}$. Thus the path
$\pi(s,a)\circ(a,b)$ connects $s$ to $H_{x}$ in $G\setminus\\{x,y\\}$. ∎

We turn to handle the remaining relevant heavy-mates. Fix some heavy-mate $y$
of $x$ which is strictly above $r(x)$ in $\pi(s,u_{H_{x}})$ (recall that we
only care now about $y\neq r(x)$). If $(y,y_{h})\notin\pi_{x}(s,H_{x})$, then
by 4.15 we have that $H_{x}\notin\mathcal{FS}(x,y)$, so by Lemma 4.4 we have
that $x_{h}$ is connected to $s$ in $G\setminus\\{x,y\\}$. Hence, by 4.19,
$G\setminus\\{x,y\\}$ connected, and we are done. So, from now on assume that
$(y,y_{h})\in\pi_{x}(s,H_{x})$. Denote by $\widehat{C}(x,y)$ the union of all
components in $\mathcal{C}_{x}$ that are below $y_{h}$ in $\widehat{T}_{x}$,
that is

$\widehat{C}(x,y)=\bigcup_{\begin{subarray}{c}C\in\mathcal{C}_{x}\\\
(y,y_{h})\in\pi_{x}(s,C)\end{subarray}}C~{}.$

We have the following key claim:

######  Claim 4.21.

$G\setminus\\{x,y\\}$ is connected iff there is an outgoing edge from
$\widehat{C}(x,y)\cup H_{y}$ in $G\setminus\\{x,y\\}$.

###### Proof.

The ‘only if’ direction is trivial. For the ‘if’ direction, first note that
the vertices of $\widehat{C}(x,y)\cup H_{y}$ are all in the same connected
component in $G\setminus\\{x,y\\}$, since they are all connected to $y_{h}$ in
$G\setminus\\{x,y\\}$. Therefore, it is enough to show that every $a\in
V\setminus(\widehat{C}(x,y)\cup H_{y}\cup\\{x,y\\})$ is connected to $s$ in
$G\setminus\\{x,y\\}$. If $a$ is not a descendant of $x$ or $y$ in $T$ then
this is obvious. If $a$ is a descendant of $x$, then it belongs to some
component $C\in\mathcal{C}_{x}$ such that $(y,y_{h})\notin\pi_{x}(s,C)$, so by
4.15 (as $xy$ is a heavy pair) we have $C\notin\mathcal{FS}(x,y)$, and by
Lemma 4.4 $C$ is connected to $s$ in $G\setminus\\{x,y\\}$. It remains to
consider $a$ which is a descendant of $y$, in some component
$C\in\mathcal{C}_{y}$, $C\neq H_{y}$. It suffices to show that
$(x,x_{h})\notin\pi_{y}(s,C)$, as this would imply that $C$ and $s$ are
connected in $G\setminus\\{x,y\\}$ by using 4.15 and Lemma 4.4 (similarly to
the previous case). Assume towards a contradiction that
$(x,x_{h})\in\pi_{y}(s,C)$. Then for the last edge $(u_{C},v_{C})$ of
$\pi_{y}(s,C)$, we have $u_{C}\in H_{x}$ and $v_{C}\in V\setminus V(T_{x})$.
Hence, $v_{C}\in R(x)$, and thus $r(x)$ is an ancestor of $v_{C}$ in $T$. As
$v_{C}\notin V(T_{y_{h}})$ (since $C\neq H_{y}$), it follows that $r(x)\notin
V(T_{y_{h}})$. But this is a contradiction: as $(y,y_{h})\in\pi(s,u_{H_{x}})$
and $y$ is strictly above $r(x)$ in this path, we have that $r(x)\in
V(T_{y_{h}})$. ∎

By this last claim, in order to determine the connectivity of
$G\setminus\\{x,y\\}$, it is enough for $x$ to have
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(\widehat{C}(x,y)\cup H_{y})$. Indeed,
by using Lemma 1.6 with $O(\log n)$ fresh basic sketch units121212Recall that
each sketch contains $L=c\log n$ basic sketch units. Hence, by taking $c$ to
be a sufficiently large constant, we can guarantee that $O(\log n)$ fresh
basic sketch units exist., $x$ can determine w.h.p. if such an outgoing edge
exists. The only obstacle is canceling the edges of $x,y$ from the sketches,
as $\mathsf{sketch}_{G\setminus\\{x\\}}(\widehat{C}(x,y))$ can be easily
computed locally in $x$, and $\mathsf{sketch}_{G\setminus\\{y\\}}(H_{y})$ is
known to $x$ by 4.18. The following technical lemma gives a procedure allowing
$x$ to overcome this obstacle.

######  Lemma 4.22.

Within $\widetilde{O}(D)$ rounds, each vertex $x\in V$ can learn
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(\widehat{C}(x,y)\cup H_{y})$ for each
heavy-mate $y$ of $x$ lying above $r(x)$ in $\pi(s,u_{H_{x}})$.

###### Proof.

Note that

$\displaystyle\mathsf{sketch}_{G\setminus\\{x,y\\}}(\widehat{C}(x,y)\cup
H_{y})=$
$\displaystyle\mathsf{sketch}_{G\setminus\\{x,y\\}}(\widehat{C}(x,y)\setminus
H_{x})\oplus\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{x})\oplus\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{y})~{}.$

We show how the three terms on the right hand side can be computed by every
$x$, for each heavy-mate $y$ above $r(x)$ in $\pi(s,u_{H_{x}})$.

For the first term, we start by giving an $\widetilde{O}(D)$-round procedure
letting every vertex $v\in V$ learn
$\mathsf{sketch}_{G\setminus\\{y\\}}(V(T_{v}))$ for every
$y\in\bigcup_{x\in\mathsf{LA}(v)}\pi_{x}(s,C_{x,v})$. Denote by $x_{i}(v)$ the
$i^{th}$ highest vertex in $\mathsf{LA}(v)$, and by $y_{ij}(v)$ the $j^{th}$
highest vertex in $\pi_{x_{i}(v)}(s,C_{x_{i}(v),v})$. Let $S(v)$ be a matrix
where the $ij$ entry, for $1\leq i\leq O(\log n)$, $1\leq j\leq O(D)$, is the
bitstring of length $\ell=\widetilde{O}(1)$ defined by

$[S(v)]_{ij}=\begin{cases}\text{if $y_{ij}(v)$ is
defined:}&\mathsf{sketch}_{G\setminus\\{y_{ij}(v)\\}}(v)\\\
\text{otherwise:}&0^{\ell}\text{ (string of $\ell$ zeros) }\end{cases}$

By Lemmas 4.3 and 1.7, each vertex $v$ can locally compute $S(v)$. Next,
observe that if $y_{ij}(v)$ is defined, then for every descendant $u$ of $v$,
we have $y_{ij}(u)=y_{ij}(v)$, and therefore

$\displaystyle\bigoplus_{u\in V(T_{v})}[S(u)]_{ij}=\bigoplus_{u\in
V(T_{v})}\mathsf{sketch}_{G\setminus\\{y_{ij}(v)\\}}(u)=\mathsf{sketch}_{G\setminus\\{y_{ij}(v)\\}}(V(T_{v}))~{}.$

Thus, XOR-aggreagting the $S(u)$ matrices over subtrees yields the required
information for each vertex $v$. Since each such matrix consists of
$\widetilde{O}(D)$ bits, this can be done within $\widetilde{O}(D)$ rounds
using standard pipeline techniques. Within another $\widetilde{O}(D)$ rounds,
each vertex can send its aggregated matrix to its parent. At this point, every
$x\in V$ holds $\mathsf{sketch}_{G\setminus\\{y\\}}(V(T_{x^{\prime}}))$ for
every light $T$-child $x^{\prime}$ of $x$, and
$y\in\pi_{x}(s,C_{x,x^{\prime}})$. Using Lemmas 1.7 and 4.1 and the
connectivity tree $\widehat{T}_{x}$ now allows $x$ to remove its own edges
from the relevant subtree sketches and add them up to locally compute
$\mathsf{sketch}_{G\setminus\\{x,y\\}}(\widehat{C}(x,y)\setminus H_{x})$ for
any heavy-mate $y$ of interest.

We now handle the second term. Recall that $x$ can easily locally compute
$\mathsf{sketch}_{G\setminus\\{x\\}}(H_{x})$ (as shown e.g. in the proof of
4.18). Also, if $y$ lies (strictly) above $r(x)$ in $\pi(s,u_{H_{x}})$, then
$y$ cannot have a neighbor in $H_{x}$ (as $r(x)$ is an ancestor of every $v\in
V(T_{x})$ that has neighbor in $H_{x}$). Thus, for every heavy-mate $y$ of
interest we have
$\mathsf{sketch}_{G\setminus\\{x\\}}(H_{x})=\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{x})$.

Finally, we deal with the third term. By item 3 of Lemma 4.1, $x$ knows for
each of its neighbors $u$ and for each $y\in\pi(s,u)$ the component-ID of
$C_{y,u}$. Thus, for every heavy-mate $y$ of interest, $x$ can identify all
its edges going into $H_{y}$, and cancel them from
$\mathsf{sketch}_{G\setminus\\{y\\}}(H_{y})$ (which is known to $x$ by 4.18)
to obtain $\mathsf{sketch}_{G\setminus\\{x,y\\}}(H_{y})$, as required. ∎

This concludes the $\widetilde{O}(D)$-round algorithm for detecting w.h.p. all
independent cut pairs. By Section 3, within another $\widetilde{O}(D)$ rounds,
we can also detect w.h.p. all dependent cut pairs. Theorem 1.2 follows.

##  5 Conclusion

In this work, we provide distributed ${\mathsf{CONGEST}}$ algorithms for
detecting vertex cuts of size at most two, with round complexity of
$\widetilde{O}(D)$. These bounds are nearly tight, and in addition, nearly
match the current bounds obtained for the corresponding edge cut problems. It
would be interesting if our techniques, e.g., for eliminating the dependency
in the maximum degree $\Delta$, could be extended to detecting vertex cuts of
any constant size within ${\rm poly}(D,\log n)$ rounds. The latter bound is
currently only achievable for the (simpler) edge cut problem [Par19].

##### Acknowledgments.

We thank the anonymous reviewers of Distributed Computing for their insightful
comments and suggestions that considerably improved the presentation of this
work.

## References

  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459–467. SIAM, 2012.
  * [BT89] Giuseppe Di Battista and Roberto Tamassia.  Incremental planarity testing (extended abstract).  In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 436–441. IEEE Computer Society, 1989.