6
$\begingroup$

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'$?

$\endgroup$
  • 5
    $\begingroup$ Hint: Grid graphs are bipartite. $\endgroup$ – JeffE Aug 3 '12 at 16:47
  • $\begingroup$ @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) $\endgroup$ – Andrew Tomazos Aug 3 '12 at 16:56
  • 4
    $\begingroup$ Hint 2: Matching. $\endgroup$ – JeffE Aug 3 '12 at 16:56
  • $\begingroup$ 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. $\endgroup$ – Andrew Tomazos Aug 3 '12 at 16:58
  • 1
    $\begingroup$ @JeffE: I still haven't figured out how to get from a bipartite graph to a maximum independent set. See my post here. $\endgroup$ – Andrew Tomazos Aug 3 '12 at 19:22
8
$\begingroup$

As JeffE mentions in a comment, a grid graph is an example of a bipartite graph. If you take a bipartite graph, and remove some of the vertices, it will still be a bipartite graph.

Königs Theorem states, that for bipartite graphs, the number of vertices in a minimum covering, equals the number of edges in a maximum matching.

As mentioned in the answer for Maximum Independent Set of a Bipartite Graph:

The complement of a maximum independent set is a minimum vertex cover

What you are asking, is how to find a maximum independent set in a grid graph with some vertices removed, and the way to do that, is to use some of the algorithms for finding a maximum matching in a bipartite graph, from that construct a minimum vertex cover, and then invert it to get a maximum independent set.

The figure below shows a bipartite graph with a maximum matching (in blue), a minimum vertex cover (in red) and consequently also a maximum independent set (in white):

from Wikipedias article on Königs Theorem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.