Abstract:  The Minimum All-Ones Problem was shown to be NP-complete for general graphs. Therefore, it becomes an interesting question to identify special classes of graphs for which one can find polynomial time algorithms. In this paper we consider this problem for trees. First, for any solution to the All-Ones Problem for a tree we give a characterization on the elements in the solution, by introducing the concept of Quasi-All-Ones Problem. Then we give the enumeration for the number of solutions in a tree. By using the Minimum Odd (Even) Sum Problem as subprocess, we obtain a linear time algorithm for the Minimum All-Ones Problem for trees. We also get a linear time algorithm for finding solutions to the All Ones Problem in a unicyclic graph.
 
  AMS Classification:  05C85, 05C70, 90C27, 68Q25, 68R10.
  
  Keywords:  Lamp Lighting Problem, All-Ones Problem, graph algorithm, time complexity.

   Download: ps