CC BY 4.0Schestag, Jannik TheodorJannik TheodorSchestagGrüttemeier, NielsNielsGrüttemeierKomusiewicz, ChristianChristianKomusiewiczSommer, FrankFrankSommer2024-06-242024-06-242024https://publica.fraunhofer.de/handle/publica/470319https://doi.org/10.24406/publica-326910.7155/jgaa.v28i1.292210.24406/publica-3269A vertex pair in an undirected graph is calledconnectedif the twovertices are connected by a path. In the NP-hardCritical Node Problem(CNP),the input is an undirected graphGwith integerskandx, and the question is whetherone can transformGby deleting at mostkvertices into a graph whose total numberof connected vertex pairs is at mostx. In this work, we introduce and study two NP-hard variants of CNP where a subset of the vertices is marked asvulnerable, and weaim to obtain a graph with at mostxconnected vertex pairs containing at least onevulnerable vertex. In the first variant, which generalizes CNP, we may delete vulnerableand non-vulnerable vertices. In the second variant, we may only delete non-vulnerablevertices.We perform a parameterized complexity study of both problems. For example, weshow that both problems are FPT with respect tok+x. Furthermore, in the case ofdeletable 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, weprove NP-hardness even when there is only one vulnerable node.engraph connectivityvertex deletionsocial networksjournal article