Let $ G = (V, E)$ be a connected undirected graph. We call $ G$ $ k$ -connected if the removal of any $ k – 1$ vertices leaves $ G$ connected. The 1-connected graphs are the connected graphs, the 2-connected graphs are also known as biconnected graphs, etc. The largest $ k$ so that $ G$ is $ k$ -connected is called the *connectivity* of $ G$ .

For 1-connected graphs, there is an efficient algorithm that splits a graph into so-called biconnected components, which are connected via *articulation* points, the points which upon removal would disconnect the graph.

For 2-connected graphs, there similarly is an efficient algorithm that gives triconnected components and so-called 2-vertex cuts: those pairs of vertices whose removal would disconnect the graph.

I am interested in the more general situation for $ k$ -connected graphs. I know that we can determine the connectivity of $ G$ in polynomial time (see for example here), although much slower than linear time like the algorithms above. However, at least at first glance, these algorithms only give me the connectivity as a number. For practical(-ish) reasons, I am interested in enumerating the $ k$ -vertex cuts. So my question is:

What is a (relatively) efficient algorithm for enumerating those sets of $ k$ vertices in a $ k$ -connected (but not $ k+1$ -connected) graph that will disconnect the graph?

We may assume for simplicity that not too many $ k$ -vertex cuts exist, if that makes the question more interesting.

(Because I want to use the algorithm for practical(-ish) reasons, I am potentially interested in fairly fine-grained distinctions: an exponential algorithm that is fast “most of the time” is still useful to me, as is the distinction between polynomial time algorithms.)