Minimum number of vertices to remove to bound the largest connected component of a graph
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$;