The problem that you are describing seems to be a variation of a critical node detection problem. In general, most critical node detection problems aim to identify a set of at most $B$ nodes (or if you are considering the weighted case, a set of nodes with a weighted sum of at most $B$ ) whose deletion results in the maximum disruption of a given property of the graph. In many of the papers that you can find in the literature, the property that is being disrupted often represents a measure of how well connected the residual graph is. For instance, such property may account for the total number of node pairs that remain connected, the number of maximally connected components, or the size of the largest connected component after the critical nodes are removed (you can also search for node interdiction or node blocker problems for other versions). Some references are: Arulslevan et al [1], Shen et al [2], Di Summa et al [3], Addis et al [4], Oosten et al [5] among others. There is also a very short survey [7] on some of these problems. Although, several other papers have been published after that chapter was in press.
These problems are indeed NP-Hard for general graphs. However, there are some polynomially solvable cases (trees and series-parallel graphs, see [3], [4], and [6]).
For the version that you mention, which is somehow a complement of the above problems (instead of maximizing the disruption, you minimize the number of critical nodes to achieve the desired disruption) there is an article that proves inapproximability for the version of the problem in which the disrupted property is the total number of pairwise connections [8]. Your intuition is correct, vertex cover is commonly used to as a steeping stone.
If have some other questions or ideas, you can send me an email. This is one of my research interests. I will be happy to provide you with more ideas and to collaborate.
There is also something to keep in mind. These problems lay in the intersection of several fields, so there may be some similar versions with different names (I have found problems that belong to the same family, like graph separators, pivotal vertices, and articulation points).
[1]: Detecting critical nodes in sparse graphs
[2]: Exact interdiction models and algorithms for disconnecting networks via node deletions
[3]: Complexity of the critical node problem over trees
[4]: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth
[5]: Disconnecting graphs by removing vertices: A polyhedral approach
[6]: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
[7]: Selected Topics in Critical Element Detection
[8]: On New Approaches of Assessing Network Vulnerability: Hardness and Approximation
