The Art Gallery Guardian

Lights out game on a grid


Problem1

Let GG be a graph, let AA be the adjacency matrix of GG. Solve the equation Ax=bAx=b in F2\F_2.

The problem is equivalent to the lights out game. Each vertex has state 00 or 11. Activate a vertex flips the state of itself and all its neighbors. Find a set of activations that turns all state into 00. Originally I thought this problem can be solved in O(nω/2)O(n^{\omega/2}) when GG is planar graph on nn vertices by nested dissection. However, only recently I found out the matrix must be non-singular. Therefore nested dissection does not apply.

Recently I saw an algorithm that shows if the graph is a n×nn\times n grid, then it can be solved in O(n3)O(n^3) time. The solution in Chinese and can be seen here.

Given a n×nn\times n grid graph. Let vi,jv_{i,j} be the node on the iith row and jjth column. Let bi,jb_{i,j} be the state of the vertex vi,jv_{i,j}. The state is in F2\F_2 If we activates a node, the state of the node and its neighbors change by 11. The set of activated node is called the activation set.

We are interested in finding an activation set SS, such the state of all nodes after activate SS is 00.

Let SS be the activation set, and S1S_1 to be the activation set of the first row.

Theorem2

S1S_1 uniquely determines SS. Moreover, One can compute SS from S1S_1 in O(n2)O(n^2) time.

Proof

Indeed, consider apply activation to the nodes in S1S_1. Consider any vertex in row 11. If it 00, then the remaining neighbor (on the second row) cannot be activated. If it is 11, then the remaining neighbor has to be activated.

Let D[i,j]D[i,j] indicates if we activate vi,jv_{i,j} or not. We create formal variables Z={z1,,zn}Z=\set{z_1,\ldots,z_n}. Here ziz_i is an indicator variable that represents if v1,iv_{1,i} is activated or not. The base case D[1,j]=zjD[1,j] = z_j. The observation shows that for each ii and jj, D[i+1,j]=1+D[i,j1]+D[i,j]+D[i,j+1]+D[i1,j]+bi,jD[i+1,j] = 1 + D[i,j-1]+D[i,j]+D[i,j+1]+D[i-1,j]+b_{i,j}. We can express D[i,j]D[i,j] as a sum of elements in ZZ and a constant, and we are summing a constant number of previous states. So it has size O(n)O(n). We can compute the expression of D[i,j]D[i,j] in O(n)O(n) time. So computing all D[i,j]D[i,j] for i2i\geq 2 takes O(n3)O(n^3) time.

We are interested in D[n,1],,D[n,n]D[n,1],\ldots,D[n,n]. We can see it is of the following form.

D[n,1]=c1,1z1++c1,nzn+u1D[n,2]=c2,1z1++c2,nzn+u2D[n,n]=cm,1z1++cm,nzn+un\displaystyle \begin{aligned} D[n,1] &= c_{1,1} z_1+\ldots +c_{1,n} z_{n} + u_{1}\\ D[n,2] &= c_{2,1} z_1+\ldots +c_{2,n} z_{n} + u_{2}\\ \vdots &\qquad \vdots\\ D[n,n] &= c_{m,1} z_1+\ldots + c_{m,n} z_n + u_{n} \end{aligned}

We solve the equation Cz=uCz=u. Note here CC is just a n×nn\times n matrix. We finds z1,,znz_1,\ldots,z_n. So now we have found the activation set restricted on the first row. We can use it to find the entire activation set.

The total running time is O(n3)O(n^3). Building the table DD and solving Cz=uCz=u. One can generalize this a bit further. We can obtain O(m2n)O(m^2n) running time for a m×nm\times n grid, where mnm\leq n. Also, there is no reason we have to work in F2\F_2, any arbitrary field is fine.

Theorem3

Let GG be a m×nm\times n grid and AA is a matrix where the non-zero entires are precisely the position of 11s in the adjacency matrix of AA. Finding Ax=bAx=b can be done in O(m2n)O(m^2n) time.

I did not think too much into it, but maybe it works for all integral domains too. Interestingly, this algorithm is so special, that we have no idea how to extend it to other graphs. Maybe it works for directed graph, maybe it works for subgraph of the grid graphs.

It would be really interesting to see an algorithm with running time O(n3/2)O(n^{3/2}) for a planar graph of nn vertices.

Posted by Chao Xu on .
Tags: algorithm, algebra.