Lights out game on a grid
Let be a graph, let be the adjacency matrix of . Solve the equation in .
The problem is equivalent to the lights out game. Each vertex has state or . Activate a vertex flips the state of itself and all its neighbors. Find a set of activations that turns all state into . Originally I thought this problem can be solved in when is planar graph on 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 grid, then it can be solved in time. The solution in Chinese and can be seen here.
Given a grid graph. Let be the node on the th row and th column. Let be the state of the vertex . The state is in If we activates a node, the state of the node and its neighbors change by . The set of activated node is called the activation set.
We are interested in finding an activation set , such the state of all nodes after activate is .
Let be the activation set, and to be the activation set of the first row.
uniquely determines . Moreover, One can compute from in time.
Indeed, consider apply activation to the nodes in . Consider any vertex in row . If it , then the remaining neighbor (on the second row) cannot be activated. If it is , then the remaining neighbor has to be activated.
Let indicates if we activate or not. We create formal variables . Here is an indicator variable that represents if is activated or not. The base case . The observation shows that for each and , . We can express as a sum of elements in and a constant, and we are summing a constant number of previous states. So it has size . We can compute the expression of in time. So computing all for takes time.
We are interested in . We can see it is of the following form.
We solve the equation . Note here is just a matrix. We finds . 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 . Building the table and solving . One can generalize this a bit further. We can obtain running time for a grid, where . Also, there is no reason we have to work in , any arbitrary field is fine.
Let be a grid and is a matrix where the non-zero entires are precisely the position of s in the adjacency matrix of . Finding can be done in 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 for a planar graph of vertices.