English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present near-optimal algorithms for detecting small vertex cuts in theCONGEST model of distributed computing. Despite extensive research in thisarea, our understanding of the vertex connectivity of a graph is stillincomplete, especially in the distributed setting. To this date, alldistributed algorithms for detecting cut vertices suffer from an inherentdependency in the maximum degree of the graph, $\Delta$. Hence, in particular,there is no truly sub-linear time algorithm for this problem, not even fordetecting a single cut vertex. We take a new algorithmic approach for vertexconnectivity which allows us to bypass the existing $\Delta$ barrier. As awarm-up to our approach, we show a simple $\widetilde{O}(D)$-round randomizedalgorithm 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 andThurimella, ICALP 2008]. Our key technical contribution is an$\widetilde{O}(D)$-round randomized algorithm for computing all cut pairs inthe graph, improving upon the state-of-the-art $O(\Delta \cdot D)^4$-roundalgorithm by [Parter, DISC '19]. Note that even for the considerably simplersetting of edge cuts, currently $\widetilde{O}(D)$-round algorithms are knownonly for detecting pairs of cut edges. Our approach is based on employing thewell-known linear graph sketching technique [Ahn, Guha and McGregor, SODA 2012]along with the heavy-light tree decomposition of [Sleator and Tarjan, STOC1981]. Combining this with a careful characterization of the survivablesubgraphs, allows us to determine the connectivity of $G \setminus \{x,y\}$ forevery pair $x,y \in V$, using $\widetilde{O}(D)$-rounds. We believe that thetools provided in this paper are useful for omitting the $\Delta$-dependencyeven for larger cut values.

Near-Optimal Distributed Computation of Small Vertex Cuts