  The K-way vertex cut problem} consists in, given a graph G, finding a subset
of vertices of a given size, whose removal partitions G into the maximum number
of connected components. This problem has many applications in several areas.
It has been proven to be NP-complete on general graphs, as well as on split and
planar graphs. In this paper, we enrich its complexity study with two new
results. First, we prove that it remains NP-complete even when restricted on
the class of bipartite graphs. This is unlike what it is expected, given that
the K-way vertex cut problem is a generalization of the Maximum Independent set
problem which is polynomially solvable on bipartite graphs. We also provide its
equivalence to the wellknown problem, namely the Critical Node Problem (CNP),
On split graphs. Therefore, any solving algorithm for the CNP on split graphs
is a solving algorithm for the K-way vertex cut problem and vice versa.
