The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs. The decision version of the problem is as follows:
Component Order Connectivity:
Input: Graph $G = (V,E)$, integers $k$ and $\ell$
Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?
The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover. Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W[1]$). The problem is also known to be $W[1]$-hard when parameterized by $k$. Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.
Very interesting question. For input $G,k,\ell$, a brute force approach would be:
branching(G,k,l):
Find a connected set of vertices D of G of size l+1
if no such D exists:
return True // no component of size > l
for v in D:
if branching(G-v,k-1,l):
return True
return False
The algorithm runs in time $(\ell + 1)^k \cdot n^2$.
Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$. This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$. Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag. It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.
A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:
Vertex Integrity:
Input: Graph $G = (V,E)$, integer $p$
Question: Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max_{D \in cc(G-X)}|D| \leq p$?
That is, the sum of the deletion set and the size of the maximal component should be minimized. This problem is also NP-hard. See, e.g.,
- Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
- Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)
