I have this problem, maybe anybody could help. Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \setminus \{v_1, \dots,v_l\}$ have at most $k$ vertices.I wonder it this problem can be solved quickly (in polynomial time)?(Related: finding the vertices when $k$ is small)
Minimum number of vertices to remove to bound the largest connected component of a graph
graph theory;np complete;combinatorics
The optimization version of this problem is known as Graph Integrity, which is unfortunately NP-Hard problem:The integrity of a graph G, denoted $I(G)$, is defined by:   $I(G) = min\{ |S| + m(G  S) : S \subset V (G) \}$ where $m(G  S)$ denotes the maximum  order of a component of $G  S$;