Parameterized Complexity of Critical Node Cuts

Danny Hermelin, Moshe Kaspi, Christian Komusiewicz +1

We consider the following natural 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$…