Finding a Small Vertex Cut on Distributed Networks

We present an algorithm for distributed networks to efficiently find a small vertex cut in the CONGEST model. Given a positive integer κ, our algorithm can, with high probability, either find κ vertices whose removal disconnects the network or return that such κ vertices do not exist. Our algorithm takes κ 3 • Õ(D + √ n) rounds, where n is the number of vertices in the network and D denotes the network's diameter. This implies Õ(D + √ n) round complexity whenever κ = polylog(n).

Prior to our result, a bound of Õ(D) is known only when κ = 1, 2 [Parter, Petruschka DISC'22]. For κ ≥ 3, this bound can be obtained only by an O(log n)-approximation algorithm [Censor-Hillel, Ghaffari, Kuhn PODC'14], and the only known exact algorithm takes O (κ∆D) O(κ) rounds, where ∆ is the maximum degree [Parter DISC'19]. Our result answers an open problem by Nanongkai, Saranurak, and Yingchareonthawornchai [STOC'19].