Yet Another Self-stabilizing Minimum Vertex Cover of a Network with Stochastic Stability

Vertex covering a network is one of the well-known combinatorial optimization problems, and the focal point in the perspective of autonomous intelligent systems is to achieve the optimal covering solutions with distributed local information by the nodes (individual systems) themselves. In this paper, we utilize a potential game for the vertex cover problem, whose the solutions to the minimum value of its global objective function are the minimum vertex covering states of a network, and newly propose a self-stabilizing parallel game-based (SPG) distributed algorithm for each vertex (player) to learn (update) its strategy parallelly with the local information. Under the proposed SPG algorithm, we prove that only the solutions to the minimum value of the potential game's global objective function are stochastically stable, and the covering strategies of all players will converge with probability one to a stochastically stable state, which is beyond the general Nash equilibrium of vertex covering games in the literatures. Furthermore, we estimate the convergence rate of the proposed SPG algorithm, and extensive samples with numerical examples verify the effectiveness and superiority of the proposed SPG algorithm on a variety of representative complex networks with different scales and standard benchmarks.