Grid algorithm puzzle

Question

I have a grid of some width and height, where each cell can be of three possible values (presented as white, green and red in this illustration):

_{(source: corexii.com)}

You may select any number of green cells (marked blue on the following illustration), which covers all red cells (marked yellow) in a pre-determined square radius (here 2) around the selected cells:

_{(source: corexii.com)}

The goal is to:

• Cover as many red cells as possible
• Using as few blue cells as possible
• Do it as fast as possible

Anyone have any ideas for an algorithm?

I'm looking at a lot of theory, but what I'm most interested in is an approximation to do this quickly rather than accurately. A fast, reasonable result is preferable to computing the optimal one all day.

(The illustrations above may present the most normal distribution of these cells, but shouldn't be assumed to resemble all possible distributions.)

Answer 1

This problem is a special case of the important NP-hard set cover problem. (The universe consists of the red cells, and each set consists of the red cells within the radius of one of the green cells.) The greedy algorithm gets within a log n factor of the optimal result.

---

templatetypedef is right to point out that the fact that this problem is a special case of an NP-hard problem does not prove that it is in fact NP-hard too. That's why I was careful in my phrasing above not to imply the latter. But being a special case of an NP-hard problem is a signal that shouldn't be ignored: many special cases turn out on further investigation to be NP-hard themselves.

So here's a rough sketch that this problem is in fact NP-hard, by a reduction from VERTEX COVER FOR PLANAR GRAPHS OF DEGREE AT MOST FOUR.

Suppose we have a planar graph of degree at most four, for example:

Represent each vertex by a green square, and each edge by an alternating chain of red and green squares such that there are an even number of green squares, an odd number of red squares, and each green square will only cover the two red squares on either side if chosen. With a radius of 2, this is one possible representation of the graph:

In order to cover all the red squares, we need to choose at least half of the green squares on each chain corresponding to an edge the original graph. If we choose exactly half of the green squares on each chain, that leaves an uncovered red square at one end of each edge (and we can choose which end). So we get the minimum set of green squares if we can find the minimum set of vertices such that every edge is incident to a vertex in that set.

In the example, we can cover the red squares using eight green squares if we pick vertices a and d:

And this corresponds to the minimum vertex cover in the original graph: