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).