On Critical Node Problems with Vulnerable Vertices

Jannik Schestag¹ ; Niels Gruettemeier² ; Christian Komusiewicz¹ ; Frank Sommer¹

¹ Institute of Computer Science, Friedrich Schiller Universität Jena
² Fraunhofer IOSB-INA Lemgo

Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 1-26.

Résumé

A vertex pair in an undirected graph is called \emph{connected} ifthe two vertices are connected by a path. In the NP-hard\textsc{Critical Node Problem}~(CNP), the input is an undirectedgraph~$G$ with integers~$k$ and~$x$, and the question is whether onecan transform~$G$ by deleting at most~$k$ vertices into a graph whose totalnumber of connected vertex pairs is at most~$x$. In this work, weintroduce and study two NP-hard variants of CNP where a subset ofthe vertices is marked as \emph{vulnerable}, and we aim to obtain agraph 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. Inthe 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.

Détail

DOI : 10.7155/jgaa.v28i1.2922

Keywords: graph connectivity, vertex deletion, social networks