*n*×

*n*

*m*of its vertices, how big a square grid must be left?

The context from which this comes is a paper (listed as submitted on Sidiropoulos' publication list, but one that I haven't actually seen yet) by Chekuri and Sidiropoulos on approximating the genus of bounded-degree graphs. It was known how to do this with an approximation ratio proportional to the square root of the number of vertices [Chen et al 1997], but this is not good when the genus is small. Instead, Chekuri and Sidiropoulos get an approximation whose genus is something like

^{O(1)}polylog(

*n*);

*n*/√

*m*×

*n*/√

*m*.

*n*×

*n*

*m*+ 1

However, their genus approximation doesn't actually need the undamaged grid to be a subgraph of the larger grid; it is enough for it to be a minor. Questions about the size of grid minors are central to Robertson and Seymour's work on the theory of graph minors, and notoriously difficult. Robertson and Seymour showed the existence of a non-constant function ƒ such that every graph of treewidth

*t*has a grid minor of size ƒ(

*t*) × ƒ(

*t*), but the growth rate of ƒ is not known and the lower bound on its growth rate proven by Robertson and Seymour seems to be very weak. So it may be a bit of a surprise that we can determine the maximum size of a grid minor that we can guarantee to exist in a damaged grid much more precisely, to within a constant factor: it is Θ(min(

*n*,

*n*

^{2}/

*m*)).

To prove that no bigger grid minors can always be found, it is enough to exhibit a specific way of damaging a grid so that all the remaining minors are small. The case when

*m*≤

*n*is uninteresting, because our formula does not provide a nontrivial upper bound on the size of a grid minor in this case, so we can assume

*m*>

*n*. In this case, we can partition the grid into disconnected subgrids of size 2

*n*

^{2}/

*m*× 2

*n*

^{2}/

*m*by deleting all of the vertices in

*m*/2

*n*rows and

*m*/2

*n*columns of the given grid. The constant factor can be improved by deleting the cells in approximately

*m*/

*n*

*n*

^{2}/2

*m*.

*n*

^{2}/2

*m*×

*n*

^{2}/2

*m*.

Finally, to show that there always exists a grid minor with side length proportional to min(

*n*,

*n*

^{2}/

*m*), consider first the case when

*m*≤

*n*/2. One way of forming a grid minor in a damaged grid is to find a collection of disjoint horizontal paths, and another collection of disjoint vertical paths, extending all the way across the grid, so that each horizontal-vertical pair has a connected intersection. The intersections of the paths can be contracted to form the vertices of the grid minor, and the rest of each path can be contracted to form its edges. For instance, our original example of a 25 × 25 grid with 72 deletions has a 15 × 15 grid minor of this type:

But if there are only a small number of damaged vertices, we can find a path system like this in which each path follows one of the undamaged rows or columns, forming a grid minor of size (

*n*−

*m*) × (

*n*−

*m*). Because of the assumption that

*m*is small, this is good enough to match the bound on the size of a grid minor that we'd like to find. On the other hand, if

*m*is larger, subdivide the grid into 4(

*m*/

*n*)

^{2}smaller subgrids of size (

*n*

^{2}/2

*m*) × (

*n*

^{2}/2

*m*). The average number of deleted points per subgrid is

*m*/(4(

*m*/

*n*)

^{2}) =

*n*

^{2}/4

*m*. There exists at least one subgrid whose number of deleted points is at most this average, which is half of the side length of the subgrid. Within this below-average subgrid we may apply the earlier idea of following disjoint paths through undamaged rows and columns, to find an undamaged grid minor of size at least (

*n*

^{2}/4

*m*) × (

*n*

^{2}/4

*m*).

To make this concrete, in the same example of a 25 × 25 grid with 72 or fewer deletions, we may divide it into 25 subgrids of size 5 × 5.

The average number of deleted vertices per subgrid is 72/25 < 3, so there exists a 5 × 5 subgrid with at most two deletions. (In this example we deleted a few more vertices, keeping the total at most 72, to prevent any of the subgrids from having fewer than two deletions.) Within one of these below-average subgrids we can use the method of following paths through the undamaged rows and columns to obtain a grid minor of size at least 3 × 3.

The improvement from

*n*/√

*m*

*n*

^{2}/

*m*in the side length of the undamaged grid that can be found within a damaged grid apparently leads to an improvement in the exponent of approximation in the Chekuri–Sidiropoulos genus algorithm, but I don't know by how much. Tasos tells me that if some other bounds in the algorithm can be similarly tightened, their method might be able to obtain an approximation with quality OPT

^{2}polylog(

*n*), but it isn't there yet.