Parameterized Dominating Set
Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams [1] that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon &gt; 0$, assuming SETH. 

This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see [1]). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega &lt; 2.376$ using matrix multiplication.



[1] Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. 2010.