Property Testing on k-Vertex-Connectivity of Graphs

We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called epsilon-far from k-vertexconnectivity when at least epsilon dn/2 dn 2 edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is k-far from k-vertex-connectivity with a probability of at least 2/ 3. The algorithm runs in O(d(c/epsilon d) k log 1/epsilon d) time (c > 1 is a constant) for (k -1)-vertex-connected graphs, and in O(d(ck/epsilon d) k log k/epsilon d) time (c > 1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k = 4.