The Graph k-Cut problem is that of finding a set of edges of minimum total weight, in an edge-weighted graph, such that their removal from the graph results in a graph having at least k connected components. An algorithm with a running time of O(nk2) for this problem has been known since 1988, due to Goldschmidt and Hochbaum. We show that the problem is hard for the parameterized complexity class W. We also investigate the complexity of a related problem, cutting a few vertices from a Graph, that asks for the minimum cost of separating at least k vertices from an edge-weighted connected graph. We show that this problem also is hard for W.
Electronic Notes in Theoretical Computer Science Vol. 78, p. 209-222