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 ϵ‐far from k‐vertex‐connectivity when at least $\frac{ϵ\mathrm{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 ϵ‐far from k‐vertex‐connectivity with a probability of at least 2/3. The algorithm runs in $O(d(\frac{c}{ϵd}{)}^k\log \frac{1}{ϵd})$ time (c>1 is a constant) for (k-1)‐vertex‐connected graphs, and in $O(d(\frac{\mathrm{ck}}{ϵd}{)}^k\log \frac{k}{ϵ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.