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