Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
<|reference_start|>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 $|X|\le \min\{r,(|V|+{\rm opt})/2\},$ where $r$ is the rank of a (modified) adjacent matrix of $G$ and ${\rm opt}$ 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.<|reference_end|>
@article{wang2024approximation,
    title={Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs},
    author={Chen Wang, Chao Wang, Gregory Z. Gutin, Xiaoyan Zhang},
    journal={arXiv preprint arXiv:2404.16540},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16540},
    primaryClass={cs.DS cs.DM}
}