 # Lights out game on a grid

Problem1

Let $G$ be a graph, let $A$ be the adjacency matrix of $G$. Solve the equation $Ax=b$ in $\F_2$.

The problem is equivalent to the lights out game. Each vertex has state $0$ or $1$. Activate a vertex flips the state of itself and all its neighbors. Find a set of activations that turns all state into $0$. Originally I thought this problem can be solved in $O(n^{\omega/2})$ when $G$ is planar graph on $n$ 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\times n$ grid, then it can be solved in $O(n^3)$ time. The solution in Chinese and can be seen here.

Given a $n\times n$ grid graph. Let $v_{i,j}$ be the node on the $i$th row and $j$th column. Let $b_{i,j}$ be the state of the vertex $v_{i,j}$. The state is in $\F_2$ If we activates a node, the state of the node and its neighbors change by $1$. The set of activated node is called the activation set.

We are interested in finding an activation set $S$, such the state of all nodes after activate $S$ is $0$.

Let $S$ be the activation set, and $S_1$ to be the activation set of the first row.

Theorem2

$S_1$ uniquely determines $S$. Moreover, One can compute $S$ from $S_1$ in $O(n^2)$ time.

Proof

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

Let $D[i,j]$ indicates if we activate $v_{i,j}$ or not. We create formal variables $Z=\set{z_1,\ldots,z_n}$. Here $z_i$ is an indicator variable that represents if $v_{1,i}$ is activated or not. The base case $D[1,j] = z_j$. The observation shows that for each $i$ and $j$, $D[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]$ as a sum of elements in $Z$ and a constant, and we are summing a constant number of previous states. So it has size $O(n)$. We can compute the expression of $D[i,j]$ in $O(n)$ time. So computing all $D[i,j]$ for $i\geq 2$ takes $O(n^3)$ time.

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

\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=u$. Note here $C$ is just a $n\times n$ matrix. We finds $z_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(n^3)$. Building the table $D$ and solving $Cz=u$. One can generalize this a bit further. We can obtain $O(m^2n)$ running time for a $m\times n$ grid, where $m\leq n$. Also, there is no reason we have to work in $\F_2$, any arbitrary field is fine.

Theorem3

Let $G$ be a $m\times n$ grid and $A$ is a matrix where the non-zero entires are precisely the position of $1$s in the adjacency matrix of $A$. Finding $Ax=b$ can be done in $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(n^{3/2})$ for a planar graph of $n$ vertices.

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