The critical node cut (CNC) problem is defined as follows: given an (undirected) graph G and two integers k and x, decide if k nodes can be removed from G such that in the resulting subgraph there are at most x pairs of vertices connected by a path. It generalizes various families of well-known graph-cut problems and has numerous applications in real life.

This paper investigates the fixed-parameter tractability (FPT) of CNC: choosing a parameter l like the number k above, is there an algorithm with a complexity bound of the form f(l)p(n), where f is an arbitrary function, p a polynomial, and n the number of vertices (or, equivalently, the size of the input)? A related question is whether or not there exists a polynomial kernel for such l: can any given instance of CNC be reduced in polynomial time to an equivalent instance whose size is polynomially bounded in terms of l? The following parameters are considered: the numbers k and x in the above description of the problem, a lower bound y for the number of connected pairs to be removed, the tree width w of G, and any combination of k, x, y, and w.

The resulting questions are answered almost completely; the only one left open is whether CNC is FPT with respect to parameter k+w. Negative results are obtained conditionally, that is, under the assumptions that the polynomial-time hierarchy and the w-hierarchy do not collapse. In a few cases, the answer is trivial; for instance, CNC reduces to the NP-complete problem VERTEX COVER for x=0, so CNC cannot be FPT with respect to x unless P=NP. Otherwise the solution is derived by providing either an algorithm of desired behavior, or a reduction from a problem of known complexity classification, using constructions that are in some cases quite involved.