Open Question: Lions and Contamination

I'd like to point to you an open problem that I find interesting. A good reference is the paper "How many lions are needed to clear a grid?" by Florian Berger, Alexander Gilbers, Ansgar Grüne, and Rolf Klein [1].

Disclaimer:  I would classify this problem as more combinatorial than topological.

Suppose we have a graph which is an n \times n grid. This graph contains n^2 vertices, and the case n=5 is drawn below.

5x5grid

We have k lions moving on this grid. At each time step a lion occupies a vertex, and between adjacent time steps a lion either stays put or travels across one edge to an adjacent vertex.

We also need to define the subset of vertices W(t) which are "contaminated" at time t. A lion can clean a contaminated vertex, but in the absence of lions, the contamination spreads. At starting time t=0 every vertex not occupied by a lion is contaminated; this gives W(0). How does the contaminated set update as the lions move? A vertex v is in W(t+1) if v is not covered by a lion at time t+1 and either

  • v belongs to W(t), or
  • v has a neighbor u in W(t) such that no lion travels from vertex v to u between times t and t+1.

Suppose you are given k lions. You get to choose the lions' starting vertices at time zero in the grid - all other vertices begin contaminated. You get to pick how each lion moves at each time step. Can you design a way to clear all contaminated vertices from the grid?

If k \geq n then this problem is easy. At time zero simply line up the lions along the left-hand side of the grid, from top to bottom. At each time step, sweep each lion one step to the right. At time t=n-1 the lions will be on the right-hand side of the grid, and there will be no contaminated vertices.

It is unknown whether k=n-1 lions are sufficient to clear the grid or not. I would guess that most people think k=n-1 lions are insufficient, but nobody has a proof!

An equivalent way to phrase this problem is to use a mobile evader instead of the set of contaminated vertices. Suppose our evader moves at the same speed as the lions: at each time step the evader occupies a vertex, and between adjacent time steps the evader either stays put or crosses one edge. The evader is caught if it occupies the same vertex or crosses the same edge as any lion. It is known that k\geq n lions can catch any such evader (say by sweeping from left to right), and it is unknown whether k=n-1 lions are sufficient or not. To see the equivalence between the formulations using a mobile evader or contaminated vertices, note that W(t) is the set of all possible locations of a mobile evader at time t.

This is one of those problems that is harder than it sounds. Upon first hearing it your reaction is that you will have a proof after one evening of hard work. A week later you still haven't made much progress, and you're a week behind on your normal research agenda. Consider yourself warned!

One reason why I classify this problem as more combinatorial than topological is that the details of the discretization matter. For example, see Figure 1 of [1] (Note - in this figure, a vertex of the n \times n grid is drawn as a square. This is their representation of a 4 \times 4 grid with 16 vertices, not a 5 \times 5 grid with 25 vertices). For a second example, see Figure 5 of [1]. In the 3d version of this problem, you might expect that n^2 lions are necessary to clear an n \times n \times n grid. Figure 5 of [1] shows that this is false - 8 lions (which is less than 9) are sufficient to clear the 3 \times 3 \times 3 grid.

References

[1] Florian Berger, Alexander Gilbers, Ansgar Grüne, and Rolf Klein. How many lions are needed to clear a grid? Algorithms 2009, 2, 1069-1086.

Leave a Reply

Your email address will not be published. Required fields are marked *