Define $Radius(G=(V,E),k)$ as the maximal radius of a graph constructed from $G$ by removing all vertices in any set $X$ of size up to $k$.
More formally:
$Radius(G,k) = \underset{X\subseteq{V},|X|\leq{k}}{max}\{Radius(G\setminus{X})\}$
The question is - does calculating $Radius(G,k)$ is NP-complete? what about finding the set $X$ that maximizes the radius? It does have a sort of equivilancy to Independent Set problem, but I couldn't construct a formal reduction..
Also, does the answer changes if we know that the graph is $(k+1)$-connected? (does the problem become simpler with this assumptiom?)