关键词: 全一问题, 最小权的完美匹配, 图算法

Abstract: The authors study three new versions of the all-ones problem and the minimum all-ones problem. The original all-ones problem is simply called the vertex-vertex problem, and the three new versions are called the vertex-edge problem, the edge-vertex problem and the edge-edge problem, respectively. The vertex-vertex problem is studied extensively. For example, the existence of solutions and efficient algorithms for finding solutions are obtained, and the minimum vertex-vertex problem for general graphs is shown to be NP-complete, however for trees, unicyclic and bicyclic graphs it can be solved in linear time, etc. In this paper, for the vertex-edge problem, the authors show that a graph has a solution if and only if it is bipartite, and therefore it has only two possible solutions and optimal solutions. For the edge-vertex problem, the authors show that a graph has a solution if and only if it contains even number of vertices. By showing that the minimum edge-vertex problem can be polynomially transformed into the minimum weight perfect matching problem, the authors obtain that the minimum edge-vertex problem can be solved in polynomial time in general. The edge-edge problem is reduced to the vertex-vertex problem for the line graph of a graph.

Key words: All-ones problem, Minimum weight perfect matching, Graph algorithm