Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs

Let $G=(V,E)$ be a graph and let each vertex of $G$ has a lamp and a button. Each button can be of ${\sigma }^{+}$-type or $\sigma$-type. Assume that initially some lamps are on and others are off. The button on vertex $x$ is of ${\sigma }^{+}$-type ($\sigma$-type, respectively) if pressing the button changes the lamp states on $x$ and on its neighbors in $G$ (the lamp states on the neighbors of $x$ only, respectively). Assume that there is a set $X\subseteq V$ such that pressing buttons on vertices of $X$ lights all lamps on vertices of $G$. In particular, it is known to hold when initially all lamps are off and all buttons are of ${\sigma }^{+}$-type. Finding such a set $X$ of the smallest size is NP-hard even if initially all lamps are off and all buttons are of ${\sigma }^{+}$-type. Using a linear algebraic approach we design a polynomial-time approximation algorithm for the problem such that for the set $X$ constructed by the algorithm, we have $\mathrm{\mid }X\mathrm{\mid }\le \min \{r,(\mathrm{\mid }V\mathrm{\mid }+\mathrm{o}\mathrm{p}\mathrm{t})\mathrm{/}2\},$ where $r$ is the rank of a (modified) adjacent matrix of $G$ and $\mathrm{o}\mathrm{p}\mathrm{t}$ is the size of an optimal solution to the problem. To the best of our knowledge, this is the first polynomial-time approximation algorithm for the problem with a nontrivial approximation guarantee.