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 activation 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 [1]. Therefore, nested dissection does not apply. In particular, even grid graphs can have singular adjacency matrix. For example, a $2\times 3$ grid.

If the graph is a $n\times n$ grid, then solving the linear system takes $O(n^6)$ time. Recently, I saw an $O(n^3)$ time solution. The solution by Zheng Wang and can be seen here(in Chinese). Here I gave my interpretation of the algorithm.

1 The algorithm

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}$ in the input. Each state is in ${\mathbb{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 a activation set, and $S_1\subseteq S$ to be the activation set of the first row.

Naively, by the above theorem, we can obtain a $O(2^n{n}^2)$ time algorithm by trying all possible $S_1$ until we find one that works.

Wang realized the proof of the theorem actually allows us to solve for $S_1$ directly. In the beginning, we don’t know what $S_1$ should be, but we do know its relations with $S$. The high level idea is a $3$ step process.

1. Express the activation state of $v_{i,j}$ as a linear combination of the activation state of $v_{1,j}$ for all $i,j$. This allows us to express $S$ parametrized by $S_1$.
2. Solve for a $S_1$ by setting up a system of linear equations with the activation states of the last row.
3. Using $S_1$ to obtain $S$.

Formally, we create formal variables $Z=\left\{z_1,\dots ,z_n\right\}$. Here $z_i$ is an indicator variable that represents if $v_{1,i}\in S_1$. Let $D[i,j]$ be a linear combination of $Z$, such that it evaluates to $1$ if $v_{i,j}\in S$ and $0$ otherwise.

We compute $D[i,j]$ through dynamic programming. First, set $D[1,j]=z_j$ for all $j$. 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 compute $D[i,j]$ in $O(n)$ time. Computing all $D[i,j]$ for $i\ge 2$ takes $O(n^3)$ time.

At this point, we have expressed if $v_{i,j}\in S$ through a linear combination of $Z$. How do we find a $S_1$ that works? The idea is to consider the linear relations defined by $D[n,1],\dots ,D[n,n]$. We can see it is of the following form.

$$\begin{array}{rl}D[n,1]& =C_{1,1}{z}_1+\dots +C_{1,n}{z}_n+u_1\\ D[n,2]& =C_{2,1}{z}_1+\dots +C_{2,n}{z}_n+u_2\\ ⋮& ⋮\\ D[n,n]& =C_{m,1}{z}_1+\dots +C_{m,n}{z}_n+u_n.\end{array}$$

If we solve the equation $Cz=u$, we find $z_1,\dots ,z_n$, which implies we find $S_1$. Note $C$ is just a $n\times n$ matrix, solving the equation takes $O(n^3)$ time. Now, we use the theorem again to find the entire activation set $S$ through $S_1$ in $O(n^2)$ time.

Building the table $D$ takes $O(n^3)$ time, solving $Cz=u$ also takes $O(n^3)$ time, compute $S$ from $S_1$ takes $O(n^2)$ time. The total running time is $O(n^3)$.

However, why is this algorithm correct? Zheng did not provide a proof, hence leaving a gap to fill.

2 Remarks

One can see this is similar to the light chasing technique. There is no need to access a precomputed lookup table, since we compute the correct first row on the fly.

One can generalize this further. We can obtain $O(m^{2}n)$ running time for a $m\times n$ grid, where $m\le n$. Also, there is no reason we have to work in ${\mathbb{F}}_2$, any field is fine.

How can this be generalized to other graphs?

Turns out this is related to the zero forcing set [2]. Consider the vertices are colored black and white. If a black vertex has only a single white neighbor, color the white neighbor black. If eventually all vertices become black, then we say the set of black vertices in the beginning is a zero forcing set. The zero forcing number of $G$ is the size of the smallest zero forcing set of $G$.

Jianbo Wang, Siyun Zhou and I wrote up a paper on this. We also improved the running time for solving the $n\times n$ grid lights out game to $O(n^{\omega }\log n)$.

Unfortunately, minimum (weighted) zero forcing set is NP-hard to find [3]. It is also very large for simple graphs. Caterpillars have a $\Omega (n)$ size zero forcing set.

Is this a new viable algorithm for solving system of linear equations?

The zero forcing number is at least the pathwidth [3], which is in turn at least the treewidth, which implies there are good separators. This should mean nested dissection is better than this zero forcing number algorithm for non-singular matrices.

References