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 isNP N P -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.
complexity treewidth dynamic programming critical node problem