Irreversible k-conversion set is introduced in connection with the mathematical modeling of the spread of diseases or opinions. We show that the problem to find a minimum irreversible 2-conversion set can be solved in O(n2log 6n) time for graphs with maximum degree at most 3 (subcubic graphs) by reducing it to the graphic matroid parity problem, where n is the number of vertices in a graph. This affirmatively settles an open question posed by Kyncl et al. (2014).

In this paper, we propose the majority algorithm to choose the connection weights for the neural networks with quantized connection weights of 1 and 0. We also obtained the layered network to solve the parity problem with the input of arbitrary number N through an application of this algorithm. The network can be expected to have the same ability of generalization as the network trained with learning rules. This is because it is possible to decide the connection weights, regardless of the size of the training set. One can decide connection weights without learning according to our case study. Thus, we expect that the proposed algorithm may be applied for a real-time processing.