Finding Large Clique Minors is Hard - Eppstein, David (Journal of Graph Algorithms and Applications, 2009)
We prove that it is NP-complete, given a graph G and a parameter h, to determine whether G contains a complete graph Kh as a minor. <!---->