三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.

Three New Versions of the All-ones Problem

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.