The general σσ all-ones problem for trees

The general σσ all-ones problem is defined as follows: Given a graph G=(V,E)G=(V,E), where V and E denote the vertex-set and the edge-set of G, respectively. Denote C as an initial subset of V. The problem is to find a subset X of V   such that for every vertex vv of G⧹CG⧹C the number of vertices in X   adjacent to vv is odd while for every vertex vv of C the number is even. X   is called a solution to the problem. When C=∅C=∅, this problem is the so-called σσ all-ones problem. If a vertex is viewed to be adjacent to itself, the σσ all-ones problem is addressed as the σ+σ+ all-ones problem. The σ+σ+ all-ones problem has been studied extensively. However, the σσ all-ones problem has received much less attention. Unlike the σ+σ+ all-ones problem, which has solutions for any graphs, the σσ all-ones problem may not have solutions for many graphs, even for some very simple graphs like C3C3 and P5P5. So, it becomes an interesting question to find polynomial time algorithms to determine if for a given tree the problem has solutions. And if it does, to find a solution to the minimum σσ all-ones problem. In this paper we present two algorithms of linear time to solve the general σσ all-ones problem for trees. The first one is good for counting the number of solutions if solutions do exist, and the second one is good for solving the minimum σσ all-ones problem. Furthermore, we can modify the algorithm slightly to solve the general minimum σσ all-ones problem.