<p>If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$;  you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$.</p>

<p>Then connect each of the $n-2$ remaining nodes of the last row to each of the nodes in $|V| \setminus \{s,t\}$ adding $(n-2)^2$ edges.</p>

<p>The resulting graph $G'$ has a graph minor of size $n \times n$ if and only if there is an Hamiltonian path from $s$ to $t$ in the source graph $G$.</p>

<p>In the following picture a no instance (left) and a yes instance (right) with the corresponding $n \times n$ grid graph minor.</p>

<p><img src="https://i.sstatic.net/W9Kck.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2013-07-10T15:52:04.530Z
2013-07-10T15:52:04.530Z
Marzio De Biasi
<p>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.</p>

<p>There are some papers on constant factor approximations to this problem, e.g.:</p>

<ul>
<li><p>Demaine, E.D.; Hajiaghayi, M.; Kawarabayashi, K. (2005). <a href="http://dx.doi.org/10.1109/SFCS.2005.14">Algorithmic graph minor theory: Decomposition, approximation, and coloring</a>. FOCS, 637–646.</p></li>
<li><p>Gua, Q.-P.; Tamaki, H. (2011). <a href="http://dx.doi.org/10.1016/j.tcs.2010.07.017">Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time</a>. Theoretical Computer Science 412 (32): 4100–4109.</p></li>
</ul>

<p>Is it hard to $(1+\epsilon)$-approximate, for some $\epsilon&gt;0$?</p>

<graph-theory><np-hardness><approximation-hardness><graph-minor>
Complexity of finding large grid minors
David Eppstein
# Complexity of finding large grid minors

(Asked by: username_0 on 2013-07-09)

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](http://dx.doi.org/10.1109/SFCS.2005.14). 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](http://dx.doi.org/10.1016/j.tcs.2010.07.017). Theoretical Computer Science 412 (32): 4100–4109.

Is it hard to $(1+\epsilon)$-approximate, for some $\epsilon>0$?

**Tags:** graph-theory, np-hardness, approximation-hardness, graph-minor

---

## 1 answers

### Answer by username_1 on 2013-07-10. Score: 10 | Accepted answer

If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$; you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$.

Then connect each of the $n-2$ remaining nodes of the last row to each of the nodes in $|V| \setminus \{s,t\}$ adding $(n-2)^2$ edges.

The resulting graph $G'$ has a graph minor of size $n \times n$ if and only if there is an Hamiltonian path from $s$ to $t$ in the source graph $G$.

In the following picture a no instance (left) and a yes instance (right) with the corresponding $n \times n$ grid graph minor.

![enter image description here](https://i.sstatic.net/W9Kck.jpg)


---

