Kernelization of 2-Vertex for Vertex Cover in Random Graphs Based on Subgraphs

While the exact solution to vertex cover problem can be found within the frame of parameterized computation, there are some limits in the theory and practice, due to the lacking both in the analysis of algorithms mechanism and process and in the grasp of problems macroscopical and dynamic properties. On the basis of fixed-parameter tractability, the d-decision makable by way of kernelization (d-DMK) of the parameterized vertex cover problem of random graph is put forward and the counting method for triangle subgraphs with 2-degree vertex is also presented. According to the studies of the sharing relationship of the vertex between the subgraphs, the dynamic and evolvement mechanism of the kernel and the degree distribution in the process of 2-degree vertex kernelization are described, from which two deductions are drawn: the first states that the strength of the kernelization algorithm based on 2-degree gets its maximum in a random graph when the probability of its 2-degree vertex is about 0.75; the second states that the parameterized vertex cover problem (G, k) of random graph given by φ(x) is 2-DMK when k smaller than a given value relation to φ(x). The results of the emulation show that the theory can not only deal with the mechanism of the kernelization, but also offer an effective way to analyze such an NP-completeness problem in random graph and a new method to solve a class of uncertain problems with known degree distributions.