I'm curious about some terminology for graphs and the existence of an algorithm. Let $G$ be a graph and $H \leq G$ a subgraph. Is there a name given to $H$ if $|N(H)|$ is minimum over all subgraphs of size $|H|$? Are there algorithms to compute such a set rather than brute force?
If by $|N(H)|$ you mean neighborhood of $H$, then this is close to the notion of graph expansion.
As for your last question, I am positive, judging from inherent difficulty of calculating other expansion rates, I bet this one would be a hard problem as well. I am not sure, if there is nothing better than a brute force algorithm, but even if there is I wouldn't expect it to break the exponential barrier.