In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established in [1], here we study the subclass of CNP over trees. We will prove that weighted CNP over trees is still NP-complete, while the unweighted version can be proved to be solvable in polynomial time through a dynamic programming approach.
Citation
[1] Arulselvan A., Commander C.W., Elefteriadou L., Pardalos P.M., Detecting critical nodes in sparse graphs, Computers & Operations Research, 36, 2193–220 (2009)