On Critical Node Problems with Vulnerable Vertices

Abstract

A vertex pair in an undirected graph is called \emph{connected} if
the two vertices are connected by a path. In the NP-hard
\textsc{Critical Node Problem}~(CNP), the input is an undirected
graph~$G$ with integers~$k$ and~$x$, and the question is whether one
can transform~$G$ by deleting at most~$k$ vertices into a graph whose total
number of connected vertex pairs is at most~$x$. In this work, we
introduce and study two NP-hard variants of CNP where a subset of
the vertices is marked as \emph{vulnerable}, and we aim to obtain a
graph with at most~$x$ connected vertex pairs containing at least one vulnerable vertex. In the first variant, which generalizes CNP,
we may delete vulnerable and non-vulnerable vertices. In
the second variant, we may only delete non-vulnerable vertices.

We perform a parameterized complexity study of both problems. For example, we show that both problems are FPT with respect to~$k+x$. Furthermore, in the case of deletable vulnerable nodes, we provide a polynomial kernel for the parameter~$vc+k$, where~$vc$ is the vertex cover number. In the case of non-deletable vulnerable nodes, we prove NP-hardness even when there is only one vulnerable node.