Distributed Potential Game Optimization to 3-Path Vertex Cover of Networks
Jie Chen, Jie Yu Wu, Rongpei Zhou, Weihua Gui · IEEE Transactions on Automation Science and Engineering · 2025
3-path vertex cover of networks is a typical optimization problem in network science, which has a wide range of applications. Toward a 3-path vertex cover of networks from distributed optimization, we first established a potential game to describe the 3-path vertex cover problem. Next, we analyze the inherent relationship between potential game and 3-path vertex cover, that is, only the solution to minimum value of potential function are minimum 3-path vertex covered solutions, and strict Nash equilibriums are intermediate solutions between minimum 3-path vertex covered solutions and 3-path vertex covered solutions. Then, we propose a bounded best response and memory-based distributed algorithm, and prove that our proposed algorithm can guarantee any initial solution converge to a strict Nash equilibrium, and further analyze the complexity of this algorithm. Finally, numerical simulations verify the effectiveness and superiority of our proposed algorithm on some representative networks and benchmark by comparing with existing representative algorithms. This work paves an effective way for distributed optimization that could be modeled as distributed potential game.