Given an undirected graph $G = (V, E)$ and an integer $k$, the well-known minimum (edge) $k$-cut problem asks to find $E' \subseteq E$ with minimum $|E'|$ that the graph $(V, E \setminus E')$ has at least $k$ connected components.
We can similarly define the minimum vertex $k$-cut problem: find $V' \subseteq V$ with minimum $|V'|$ such that the subgraph induced by $V \setminus V'$ has at least $k$ connected components.
There is a slight difference between the edge and the vertex version: for the edge version, a feasible solution $E'$ exists iff $|V| \geq k$, but for the vertex version, a feasible solution $V'$ exists iff $G$ has an independent set of size $k$. Therefore, if $k$ is part of input, for the vertex version, even finding a feasible solution is NP-hard. For the edge version, it is NP-hard to find the minimum solution, but we can get a good (<2)-approximation.
My main question is when $k \geq 3$ is a fixed constant (of course when $k = 2$ both vertex and edge versions can be easily solved). For the edge version, the following paper by Goldschmidt and Hochbaum shows that the minimum $E'$ can be found in time $O(n^{k^2})$.
https://www.computer.org/csdl/proceedings/focs/1988/0877/00/021960.pdf
What is the complexity of computing the minimum vertex $k$-cut when $k$ is a fixed constant? Currently I do not know the answer for $k = 3$.
