A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 7.847, Top 10% (SCI Q1)
    CiteScore: 13.0, Top 5% (Q1)
    Google Scholar h5-index: 64, TOP 7
Turn off MathJax
Article Contents
Jie Chen, Kaiyi Luo, Changbing Tang, Zhao Zhang, and Xiang Li, "Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game," IEEE/CAA J. Autom. Sinica,doi: 10.1109/JAS.2022.105521
Citation: Jie Chen, Kaiyi Luo, Changbing Tang, Zhao Zhang, and Xiang Li, "Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game," IEEE/CAA J. Autom. Sinica,doi: 10.1109/JAS.2022.105521

Optimizing Polynomial-Time Solutions to a Network Weighted Vertex Cover Game

doi: 10.1109/JAS.2022.105521
Funds:  This work was partly supported by the National Natural Science Foundation of China (61751303, U20A2068, 11771013), the Zhejiang Provincial Natural Science Foundation of China (LD19A010001), and the Fundamental Research Funds for the Central Universities
More Information
  • Weighted vertex cover (WVC) is one of the most important combinatorial optimization problems. In this paper, we provide a new game optimization to achieve efficiency and time of solutions for the WVC problem of weighted networks. We first model the WVC problem as a general game on weighted networks. Under the framework of a game, we newly define several cover states to describe the WVC problem. Moreover, we reveal the relationship among these cover states of the weighted network and the strict Nash equilibriums (SNEs) of the game. Then, we propose a game-based asynchronous algorithm (GAA), which can theoretically guarantee that all cover states of vertices converging in an SNE with polynomial time. Subsequently, we improve the GAA by adding 2-hop and 3-hop adjustment mechanisms, termed the improved game-based asynchronous algorithm (IGAA), in which we prove that it can obtain a better solution to the WVC problem than using a the GAA. Finally, numerical simulations demonstrate that the proposed IGAA can obtain a better approximate solution in promising computation time compared with the existing representative algorithms.


  • loading
  • [1]
    E. Xu, Z. Ding, and S. Dasgupta, “Target tracking and mobile sensor navigation in wireless sensor networks,” IEEE Trans. Mobile Computing, vol. 12, no. 1, pp. 177–186, Jan. 2013. doi: 10.1109/TMC.2011.262
    N. Nguyen and B. Liu, “The mobile sensor deployment problem and the target coverage problem in mobile wireless sensor networks are NP-Hard,” IEEE Systems Journal, vol. 13, no. 2, pp. 1312–1315, Jun. 2019. doi: 10.1109/JSYST.2018.2828879
    Y. Yang, L. Liao, H. Yang, and S. Li, “An optimal control strategy for multi-UAVs target tracking and cooperative competition,” IEEE/CAA Journal of Automatica Sinica, vol. 8, no. 12, pp. 1931–1947, Dec. 2021.
    N. Xiao, X. Wang, L. Xie, T. Wongpiromsarn, E. Frazzoli, and D. Rus, “Road pricing design based on game theory and multi-agent consensus,” IEEE/CAA Journal of Automatica Sinica, vol. 1, no. 1, pp. 31–39, Jan. 2014. doi: 10.1109/JAS.2014.7004617
    D. Cheng, T. Xu, F. He, and H. Qi, “On dynamics and Nash equilibriums of networked games,” IEEE/CAA Journal of Automatica Sinica, vol. 1, no. 1, pp. 10–18, Jan. 2014. doi: 10.1109/JAS.2014.7004614
    X. Liu, X. Zhang, and V. Venkatasubramanian, “Distributed voltage security monitoring in large power systems using synchrophasors,” IEEE Trans. Smart Grid, vol. 7, no. 2, pp. 982–991, Mar. 2016. doi: 10.1109/TSG.2015.2410219
    X. Wang, Z. Zhao, D. Xu, Z. Zhang, Q. Hao, and M. Liu, “An M-cache-based security monitoring and fault recovery architecture for embedded processor,” IEEE Trans. Very Large Scale Integration (VLSI)Systems, vol. 28, no. 11, pp. 2314–2327, Nov. 2020. doi: 10.1109/TVLSI.2020.3021533
    F. Li, R. Xie, Z. Wang, L. Guo, J. Ye, P. Ma, and W. Song,, “Online distributed IoT security monitoring with multidimensional streaming big data,” IEEE Internet of Things Journal, vol. 7, no. 5, pp. 4387–4394, May 2020. doi: 10.1109/JIOT.2019.2962788
    X. Song and Y. Li, “Data gathering in wireless sensor networks via regular low density parity check matrix,” IEEE/CAA Journal of Automatica Sinica, vol. 5, no. 1, pp. 83–91, Jan. 2018. doi: 10.1109/JAS.2017.7510448
    M. Usman, M. A. Jan, X. He, and J. Chen, “A mobile multimedia data collection scheme for secured wireless multimedia sensor networks,” IEEE Trans. Network Science and Engineering, vol. 7, no. 1, pp. 274–284, Jan. 2020. doi: 10.1109/TNSE.2018.2863680
    J. A. Ansere, G. Han, L. Liu, Y. Peng, and M. Kamal, “Optimal resource allocation in energy-efficient internet-of-things networks with imperfect CSI,” IEEE Internet of Things Journal, vol. 7, no. 6, pp. 5401–5411, Jun. 2020. doi: 10.1109/JIOT.2020.2979169
    H. Wu, X. Liu, L. Fu, and X. Wang, “Energy-efficient and robust tensor-encoder for wireless camera networks in Internet of things,” IEEE Trans. Network Science and Engineering, vol. 6, no. 4, pp. 646–656, Oct. 2019. doi: 10.1109/TNSE.2018.2865511
    M. Dai, J. Li, Z. Su, W. Chen, Q. Xu, and S. Fu, “A privacy preservation based scheme for task assignment in Internet of things,” IEEE Trans. Network Science and Engineering, vol. 7, no. 4, pp. 2323–2335, Oct. 2020. doi: 10.1109/TNSE.2020.2970767
    S. Taoka and T. Watanabe, “Performance comparison of approximation algorithms for the minimum weight vertex cover problem,” in Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS), Seoul, Korea (South), 2012. pp. 632−635,
    J. Zhou, Z. Cao, X. Dong, N. Xiong, and A. Vasilakosd, “4S: A secure and privacy-preserving key management scheme for cloud-assisted wireless body area network in m-healthcare social networks,” Information Sciences, vol. 314, pp. 255–276, 2015. doi: 10.1016/j.ins.2014.09.003
    A. Gondeau, Z. Aouabed, M. Hijri, P. R. Peres-Neto, and V. Makarenkov, “Object weighting: A new clustering approach to deal with outliers and cluster overlap in computational biology,” IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 18, no. 2, pp. 633−643, 1 2021.
    D. Coppersmith and U. Vishkin, “Solving NP-hard problems in almost trees: Vertex cover,” Discrete Applied Mathematics, vol. 10, no. 1, pp. 27–45, 1985. doi: 10.1016/0166-218X(85)90057-5
    E. Halperin, “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs,” SIAM Journal on Computing, vol. 31, no. 5, pp. 1608–1623, 2002. doi: 10.1137/S0097539700381097
    G. Karakostas, “A better approximation ratio for the vertex cover problem,” in Int. Colloquium on Automata, Languages, and Programming. Berlin, Heidelberg: Springer, pp. 1043−1050, 2005.
    F. Yang, N. Wu, Y. Qiao, and R. Su, “Polynomial approach to optimal one-wafer cyclic scheduling of treelike hybrid multi-cluster tools via Petri nets,” IEEE/CAA Journal of Automatica Sinica, vol. 5, no. 1, pp. 270–280, Jan. 2018. doi: 10.1109/JAS.2017.7510772
    M. Weigt and A. K. Hartmann, “Typical solution time for a vertexcovering algorithm on finite-connectivity random graphs,” Physical Review Letters, vol. 86, no. 8, Article No. 1658, 2001. doi: 10.1103/PhysRevLett.86.1658
    W. Chang, T. Ren, and M. Feng, “Quantum algorithms and mathematical formulations of biomolecular solutions of the vertex cover problem in the finite-dimensional hilbert space,” IEEE Trans. NanoBioscience, vol. 14, no. 1, pp. 121–128, Jan. 2015. doi: 10.1109/TNB.2014.2375356
    S. Khuri and T. Bäck, “An evolutionary heuristic for the minimum vertex cover problem,” in Proc. KI-94 Workshop Genetic Algorithms Within Framework Evolutionary Computation, Saarbrcken, Germany, 1994, pp. 86−90.
    R Bar-Yehuda and S. Even, “A linear-time approximation algorithm for the weighted vertex cover problem,” Journal of Algorithms, vol. 2, no. 2, pp. 198–203, 1981. doi: 10.1016/0196-6774(81)90020-1
    R Niedermeier and P. Rossmanith, “On efficient fixed-parameter algorithms for weighted vertex cover,” Journal of Algorithms, vol. 47, no. 2, pp. 63–77, 2003. doi: 10.1016/S0196-6774(03)00005-1
    L. E. Blume, “The statistical mechanics of strategic interaction,” Games and economic behavior, vol. 5, no. 3, pp. 387–424, 1993. doi: 10.1006/game.1993.1023
    M. A. Nowak and R. M. May, “Evolutionary games and spatial chaos,” Nature, vol. 359, no. 6398, pp. 826–829, 1992. doi: 10.1038/359826a0
    R. B. Myerson, Game Theory: Analysis of Conflict. Cambridge, USA: Harvard University Press, 1991.
    J. F. Nash, “Equilibrium points in n-person games,” Proc. the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950. doi: 10.1073/pnas.36.1.48
    Z. Hu, X. Li, J. Wang, C. Xia, Z. Wang, and M. Perc, “Adaptive reputation promotes trust in social networks,” IEEE Trans. Network Science and Engineering, vol. 8, no. 4, pp. 3087–3098, Dec. 2021. doi: 10.1109/TNSE.2021.3103771
    Y. Zhu, J. Zhang, J. Han, and Z. Chen, “Evolutionary game dynamics based on local intervention in multi-agent systems,” IEEE Trans. Circuits and Systems II:Express Briefs, vol. 68, no. 4, pp. 1293–1297, April. 2021.
    R. Gopalakrishnan, J. R. Marden, and A. Wierman, “An architectural view of game theoretic control,” ACM SIGMETRICS Performance Evaluation Review, vol. 38, no. 3, pp. 31–36, 2011. doi: 10.1145/1925019.1925026
    Y. Yang and X. Li, “Towards a snowdrift game optimization to vertex cover of networks,” IEEE Trans. Cybernetics, vol. 43, no. 3, pp. 948–956, Jun. 2013. doi: 10.1109/TSMCB.2012.2218805
    J. Chen and X. Li, “Toward the minimum vertex cover of complex networks using distributed potential games,” Science China: Information Science, to be published, 2021, DOI: 10.1007/s11432-021-3291-3.
    C. Tang, A. Li, and X. Li, “Asymmetric game: A silver bullet to weighted vertex cover of networks,” IEEE Trans. Cybernetics, vol. 48, no. 10, pp. 2994–3005, Oct. 2018. doi: 10.1109/TCYB.2017.2754919
    C. Sun, W. Sun, X. Wang, and Q. Zhou, “Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems,” IEEE Trans. Cybernetics, vol. 49, no. 5, pp. 1968–1978, May 2019. doi: 10.1109/TCYB.2018.2817631
    P. Erdős and A. Rényi, “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960.
    G. Szabó and G. Fath, “Evolutionary games on graphs,” Physics Reports, vol. 446, no. 4-6, pp. 97–216, 2007. doi: 10.1016/j.physrep.2007.04.004
    D. J. Watts and S. H. Strogatz, “Collective dynamics of smallworldnetworks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. doi: 10.1038/30918
    A. L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. doi: 10.1126/science.286.5439.509


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(10)  / Tables(4)

    Article Metrics

    Article views (78) PDF downloads(14) Cited by()


    DownLoad:  Full-Size Img  PowerPoint