On the complexity of Bandwidth Minimization
The bandwidth problem is $W[t]$-hard for all $t$. It was shown by Bodlaender et al. in "Beyond NP-completeness for problems of bounded width." See the paper.

On the other hand, it is also known that for any $k$, whether a given graph has bandwidth at most $k$ can be decided in $O(f(k)n^{k+1})$ time. This implies that the bandwidth problem is in $XP$. See the another paper by Saxe.