Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth

We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure of the surviving nodes. We prove that the problem isNPNP-complete even on quite particular types of graphs, and define a dynamic programming recursion that solves the problem in polynomial time when the graph has bounded treewidth. We extend this polynomial algorithm to several variants of the problem.