  We present near-optimal algorithms for detecting small vertex cuts in the
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)$-round 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.

Data Structures and Algorithms;Distributed, Parallel, and Cluster Computing