What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version asking whether there exists such a minor for given $k$) but I don't know of a published proof.
There are some papers on constant factor approximations to this problem, e.g.:
Demaine, E.D.; Hajiaghayi, M.; Kawarabayashi, K. (2005). Algorithmic graph minor theory: Decomposition, approximation, and coloring. FOCS, 637–646.
Gua, Q.-P.; Tamaki, H. (2011). Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time. Theoretical Computer Science 412 (32): 4100–4109.
Is it hard to $(1+\epsilon)$-approximate, for some $\epsilon>0$?