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

arXiv: https://arxiv.org/abs/1304.6189 · HTML: https://mlsanity.com/paper/1304.6189/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [The Karp Dataset](https://mlsanity.com/paper/2501.14705/) (2025)

## Abstract (arXiv)

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.