  Vertex connectivity is a well-studied concept in graph theory with numerous
applications. A graph is $k$-connected if it remains connected after removing
any $k-1$ vertices. The vertex connectivity of a graph is the maximum $k$ such
that the graph is $k$-connected. There is a long history of algorithmic
development for efficiently computing vertex connectivity. Recently, two near
linear-time algorithms for small k were introduced by [Forster et al. SODA
2020]. Prior to that, the best known algorithm was one by [Henzinger et al.
FOCS'96] with quadratic running time when k is small.
  In this paper, we study the practical performance of the algorithms by
Forster et al. In addition, we introduce a new heuristic on a key subroutine
called local cut detection, which we call degree counting. We prove that the
new heuristic improves space-efficiency (which can be good for caching
purposes) and allows the subroutine to terminate earlier. According to
experimental results on random graphs with planted vertex cuts, random
hyperbolic graphs, and real world graphs with vertex connectivity between 4 and
15, the degree counting heuristic offers a factor of 2-4 speedup over the
original non-degree counting version for most of our data. It also outperforms
the previous state-of-the-art algorithm by Henzinger et al. even on relatively
small graphs.
