During my recent visit to UIUC, Tasos Sidiropoulos asked me a question about grid graphs that turns out to have a surprisingly clean answer. In rough terms, the question is: if an \( n\times n \) square grid graph is damaged by the deletion of some number \( 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 \( \mathrm{OPT}^{O(1)} \mathrm{polylog}(n) \); that is, up to polylogs, the approximation ratio is a polynomial of the minimum genus itself. Deep within the proof of their result, one of their lemmas uses the observation that a damaged grid must have an undamaged grid subgraph of size approximately \( \tfrac{n}{\sqrt{m}}\times\tfrac{n}{\sqrt{m}} \). For, if the original \( n\times n \) grid is partitioned into \( m+1 \) subgrids of this size, then one of the subgrids must be undamaged. For instance, the \( 25\times 25 \) grid below has \( 72 \) deleted vertices. It has no undamaged \( 3\times 3 \) subgrids, but if we partition it into \( 144 \) little \( 2\times 2 \) subgrids (ignoring one leftover row and column) there aren't enough holes to hit them all, so there has to be at least one undamaged \( 2\times 2 \) subgrid left (and in fact there are a lot of them).

25 x 25 grid with 72 deleted vertices

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 \( f \) such that every graph of treewidth \( t \) has a grid minor of size \( f(t)\times f(t) \), but the growth rate of \( f \) 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 \( \Theta\bigl(\min(n, n^2/m)\bigr) \).

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\le 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\gt n \). In this case, we can partition the grid into disconnected subgrids of size \( \tfrac{2n^2}{m}\times\tfrac{2n^2}{m} \) by deleting all of the vertices in \( m/2n \) rows and \( m/2n \) columns of the given grid. The constant factor can be improved by deleting the cells in approximately \( 2m/n \) diagonals of the grid, leaving a graph of pathwidth approximately \( n^2/2m \). The pathwidth of a grid is given by its side length, and pathwidth can't be increased by taking minors, so the biggest grid minor in the remaining graph has size approximately \( \tfrac{n^2}{2m}\times\tfrac{n^2}{2m} \). For instance, in our example \( 25\times 25 \) grid, fewer than \( 72 \) deletions suffice to make the pathwidth of the remaining graph too small to contain a \( 5\times 5 \) grid minor.

Deleting diagonals from a 25 x 25 grid eliminates all 5 x 5 grid minors

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\le 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\times 25 \) grid with \( 72 \) deletions has a \( 15\times 15 \) grid minor of this type:

Overlaying horizontal and vertical disjoint paths to find a grid minor in a damaged grid

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)\times(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 \( \tfrac{n^2}{2m}\times\tfrac{n^2}{2m} \). The average number of deleted points per subgrid is \[ \frac{m}{4(m/n)^2} = \frac{n^2}{4m}. \] 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 \( \tfrac{n^2}{4m}\times\tfrac{n^2}{4m} \).

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

Dividing the 25 x 25 grid into 25 smaller 5 x 5 grids leaves at least one smaller grid only lightly damaged

The average number of deleted vertices per subgrid is \( 72/25\lt 3 \), so there exists a \( 5\times 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\times 3 \).

The improvement from \( n/\sqrt{m} \) to \( 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 \( \mathrm{OPT}^2 \mathrm{polylog}(n) \), but it isn't there yet.




Comments:

None:
2012-12-17T15:05:19Z
elegant !!