On Critical Node Problems with Vulnerable Vertices

A 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.