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

Jie Chen; Kaiyi Luo; Changbing Tang; Zhao Zhang; Xiang Li

doi:10.1109/JAS.2022.105521

Volume 10 Issue 2

Feb. 2023

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 11.8, Top 4% (SCI Q1)

CiteScore: 17.6, Top 3% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2023 > 10(2): 512-523

J. Chen, K. Y. Luo, C. B. Tang, Z. Zhang, and X. Li, “Optimizing polynomial-time solutions to a network weighted vertex cover game,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 512–523, Feb. 2023. doi: 10.1109/JAS.2022.105521

Citation:

J. Chen, K. Y. Luo, C. B. Tang, Z. Zhang, and X. Li, “Optimizing polynomial-time solutions to a network weighted vertex cover game,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 512–523, Feb. 2023. doi: 10.1109/JAS.2022.105521

Citation:

PDF( 3062 KB)

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

doi: 10.1109/JAS.2022.105521

Jie Chen^1
,,
Kaiyi Luo^2
,,
Changbing Tang^{3
,
,},
Zhao Zhang^4
,,
Xiang Li^5
,

1.
Adaptive Networks and Control Laboratory, Department of Electronic Engineering, Fudan University, Shanghai 200433, China
2.
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004. He is now with Yuxi Middle School, Taizhou 317399, China
3.
College of Physics and Electronics Information Engineering, Zhejiang Normal University, Jinhua 321004, China
4.
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
5.
Adaptive Networks and Control Laboratory, Department of Electronic Engineering, Fudan University, Shanghai 200433. He is now with the Institute of Complex Networks and Intelligent Systems, Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University, Shanghai 201210, China

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

Author Bio:
Jie Chen received the B.S. degree in building electrical and intelligent engineering from Anhui Jianzhu University, in 2015, and the M.S. degree in electrical engineering from Central South University, in 2018. He is currently a Ph.D. candidate at Fudan University.His current research interests focus on evolutionary game theory and game-theoretical optimization of complex networks

Kaiyi Luo received the B.S. degree in mathematics and applied mathematics from Tianjin University of Technology in 2018, and the M.S. degree in mathematics from Zhejiang Normal University in 2021. He currently works as a Mathematics Teacher in Yuxi Middle School. His current research interests focus on game-theoretical optimization of complex networks

Changbing Tang (Member, IEEE) received the B.S. and M.S. degrees in mathematics and applied mathematics from Zhejiang Normal University, in 2004 and 2007, respectively, the Ph.D. degree from the Department of Electronic Engineering, Fudan University in 2014. He is currently an Associate Professor with College of Physics and Electronics Information Engineering, Zhejiang Normal University. His research interests include game theory, blockchain and its applications, networks and distributed optimization. He was the recipient of the Academic New Artist Doctoral Post Graduate from the Ministry of Education of China in 2012 and the recipient of the Academician Pairing Training Program for Young Talents of Zhejiang Province in 2019

Zhao Zhang (Member, IEEE) received the Ph.D. from Xinjiang University in 2003. She worked in Xinjiang University from 1999 to 2014, and now is a Professor in the College of Mathematics and Computer Science, Zhejiang Normal University.Her main interest is in combinatorial optimization, especially approximation algorithms for NP-hard problems which have their background in networks

Xiang Li (Senior Member, IEEE) received the B.S. and Ph.D. degrees in control theory and control engineering from Nankai University, in 1997 and 2002, respectively. He was at the City University of Hong Kong, Int. University Bremen, and Shanghai Jiao Tong University, and Fudan University as a Post-Doc Research Fellow, Humboldt Research Fellow, Associate Professor, and Full Professor/Distinguished Professor in 2002−2004, 2005−2006, 2004−2007, and 2008−2021, respectively. Currently, he is the Founding Director of the Institute of Complex Networks and Intelligent Systems at the Shanghai Research Institute for Intelligent Autonomous Systems, Tongji University. His main research interests include network science and systems control in both theory and applications. He serves as the Associate Editor of the Journal of Complex Networks and the IEEE Circuits and Systems Society Newsletter, and the Associate Editor (2018−2021) and Area Editor (since 2022) of the IEEE Transactions on Network Science and Engineering Journal. He received the IEEE Guillemin-Cauer Best Transactions Paper Award from the IEEE Circuits and Systems Society in 2005, the Shanghai Natural Science Award (1st class) in 2008, National Science Foundation for Distinguished Young Scholar of China in 2014, the National Natural Science Award of China (2nd class) in 2015, the Ten Thousand Talent Program of China in 2017, and TCCT CHEN Han-Fu Award of Chinese Automation Association in 2019, and the Excellent Editor Award of the IEEE Trans. Network Science and Engineering in 2021, among other awards and honors
Corresponding author: Changbing Tang, e-mail: tangcb@zjnu.edu.cn
Received Date: 2021-09-07
Revised Date: 2021-12-06
Accepted Date: 2021-12-30

Available Online: 2022-03-17

Abstract

Abstract

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.
- Game-based asynchronous algorithm (GAA),
- game optimization,
- polynomial time,
- strict Nash equilibrium (SNE),
- weighted vertex cover (WVC)

FullText(HTML)

References(40)

References

[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
[2]	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
[3]	Y. Yang, L. Liao, H. Yang, and S. Li, “An optimal control strategy for multi-UAVs target tracking and cooperative competition,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 12, pp. 1931–1947, Dec. 2021.
[4]	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 J. Autom. Sinica, vol. 1, no. 1, pp. 31–39, Jan. 2014. doi: 10.1109/JAS.2014.7004617
[5]	D. Cheng, T. Xu, F. He, and H. Qi, “On dynamics and Nash equilibriums of networked games,” IEEE/CAA J. Autom. Sinica, vol. 1, no. 1, pp. 10–18, Jan. 2014. doi: 10.1109/JAS.2014.7004614
[6]	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
[7]	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
[8]	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 J., vol. 7, no. 5, pp. 4387–4394, May 2020. doi: 10.1109/JIOT.2019.2962788
[9]	X. Song and Y. Li, “Data gathering in wireless sensor networks via regular low density parity check matrix,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 83–91, Jan. 2018. doi: 10.1109/JAS.2017.7510448
[10]	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
[11]	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 J., vol. 7, no. 6, pp. 5401–5411, Jun. 2020. doi: 10.1109/JIOT.2020.2979169
[12]	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
[13]	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
[14]	S. Taoka and T. Watanabe, “Performance comparison of approximation algorithms for the minimum weight vertex cover problem,” in Proc. IEEE Int. Symp. Circuits and Systems, Seoul, Korea (South), 2012. pp. 632−635,
[15]	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
[16]	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.
[17]	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
[18]	E. Halperin, “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs,” SIAM J. Computing, vol. 31, no. 5, pp. 1608–1623, 2002. doi: 10.1137/S0097539700381097
[19]	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.
[20]	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 J. Autom. Sinica, vol. 5, no. 1, pp. 270–280, Jan. 2018. doi: 10.1109/JAS.2017.7510772
[21]	M. Weigt and A. K. Hartmann, “Typical solution time for a vertex covering algorithm on finite-connectivity random graphs,” Physical Review Letters, vol. 86, no. 8, p. 1658, 2001. doi: 10.1103/PhysRevLett.86.1658
[22]	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
[23]	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.
[24]	R. Bar-Yehuda and S. Even, “A linear-time approximation algorithm for the weighted vertex cover problem,” J. Algorithms, vol. 2, no. 2, pp. 198–203, 1981. doi: 10.1016/0196-6774(81)90020-1
[25]	R. Niedermeier and P. Rossmanith, “On efficient fixed-parameter algorithms for weighted vertex cover,” J. Algorithms, vol. 47, no. 2, pp. 63–77, 2003. doi: 10.1016/S0196-6774(03)00005-1
[26]	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
[27]	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
[28]	R. B. Myerson, Game Theory: Analysis of Conflict. Cambridge, USA: Harvard University Press, 1991.
[29]	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
[30]	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
[31]	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, Apr. 2021.
[32]	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
[33]	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
[34]	J. Chen and X. Li, “Toward the minimum vertex cover of complex networks using distributed potential games,” Science China: Information Science, 2021, DOI: 10.1007/s11432-021-3291-3.
[35]	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
[36]	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
[37]	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.
[38]	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
[39]	D. J. Watts and S. H. Strogatz, “Collective dynamics of small world networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998. doi: 10.1038/30918
[40]	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

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(10) / Tables(4)

Get Citation

PDF

XML

Article Metrics

Article views (514) PDF downloads(34)

Highlights

We establish a novel general game model for the weighted vertex cover (WVC) problem, and define three cover states to describe the WVC problem, which can narrow the scope of searching for the optimal solution for the WVC problem
We reveal the relationship between the cover states and the strict Nash equilibriums (SNEs) of the established game model
We propose a game-based asynchronous algorithm (GAA) with memory length m=1, which can guarantee to obtain an SNE in polynomial time
We propose an improved game-based asynchronous algorithm (IGAA) with memory length m> =1 by adding the l-hop adjustment mechanism into the GAA, which can guarantee to obtain an better SNE than that of the GAA

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

doi: 10.1109/JAS.2022.105521

Abstract

References

Proportional views

Catalog

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

Article Metrics

Highlights

Export File

Citation

Format

Content