Finding a Small Vertex Cut on Distributed Networks

2023/02/22 by Jiang, Yonggang, Mukhopadhyay, Sagnik · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2302.11651

Abstract

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 κ³⋅ O(D+√(n)) rounds, where n is the number of vertices in the network and D denotes the network's diameter. This implies O(D+√(n)) round complexity whenever κ=polylog(n). Prior to our result, a bound of O(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].

Cited by

• A (Very) Nearly Optimal Sketch for k-Edge Connectivity Certificates

Related

• Near-Optimal Distributed Computation of Small Vertex Cuts
• Small Cuts and Connectivity Certificates: A Fault Tolerant Approach
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Distributed Minimum Cut Approximation
• Minor Excluded Network Families Admit Fast Distributed Algorithms