Puncturable Graph Sketches and the Complexity of Distributed Vertex ConnectivityResearch Paper
Deciding how strongly a graph is connected is a basic problem in combinatorics and network analysis. A graph is -connected if deleting fewer than of its vertices leaves a connected graph with at least two vertices. With the whole graph in hand this is solved in time by maximum-flow computations. The question changes when no single machine…