# Maximum Independent Subset of 2D Grid Subgraph

In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.

However consider the following subset of graphs:

• Create an $N \times N$ grid of unit square cells.
• Build a graph $G$ by creating a vertex corresponding to every cell. Notice that there are $N^2$ vertices.
• Create an edge between two vertices if their cells share a side. Notice there are $2N(N-1)$ edges.

A Maximum Independent Subset of $G$ is obviously a checker pattern. A cell at the $R$th row and $C$th column is part of it if $R+C$ is odd.

Now we create a graph $G'$ by copying $G$ and removing some vertices and edges. (If you remove a vertex also remove all edges it ended of course. Also note you can remove an edge without removing one of the vertices it ends.)

By what algorithm can we find a Maximum Independent Subset of $G'$?

• Hint: Grid graphs are bipartite. – JeffE Aug 3 '12 at 16:47
• @JeffE: There is one way to partition a grid graph into two sets of verticies such that they have no internal edge (by R+C parity). Once you start removing verticies and edges doesn't the number of ways to partition it grow exponentially. (maybe I have it. a single connected component maybe only still has one way to partition it) – Andrew Tomazos Aug 3 '12 at 16:56
• Hint 2: Matching. – JeffE Aug 3 '12 at 16:56
• Yeah I think I see it. Sort it into connected components. Split each component into the unique two partition. Select the larger partition from each component. – Andrew Tomazos Aug 3 '12 at 16:58
• @JeffE: I still haven't figured out how to get from a bipartite graph to a maximum independent set. See my post here. – Andrew Tomazos Aug 3 '12 at 19:22