Given an undirected graph and an integer $B$, we ask to find the minimum set of nodes whose removal partitions the generated graph into connected components, each having at most $B$ nodes.We can consider this to be a generalization of the minimum vertex cover, where $B=1$, since deleting the vertex cover set of a graph $G$ gives an independent set, i.e. partition G on connected component of no more than 1 node.Are there similar problems in literature?This problem is NP-complete on general graphs. Which known problem on graph theory help to study its (in)approximation?I want to study it on chordal graphs. For which cases it may be polynomial and for which it is NP-complete?
Graph partitioning by node deletion
cc.complexity theory;graph theory;np hardness