Parameterized complexity of critical node cuts

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(κ)⋅nO(1) time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters κ. We consider four such parameters: