On the Complexity of the K-way Vertex Cut Problem

Mohammed Lalou

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…