On the parameterized complexity of cutting a few vertices from a graph

We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph G and integers k, t, the task is to find a vertex set X with |X| ≤ k and |N(X)| ≤ t. We show that - the problem is fixed-parameter tractable (FPT) when parameterized by t but W[1]-hard when parameterized by k, and - a terminal variant of the problem, where X must contain a given vertex s, is W[1]-hard when parameterized either by k or by t alone, but is FPT when parameterized by k + t. We also show that if we consider edge cuts instead of vertex cuts, the terminal variant is NP-hard.