Journal of Guangxi Normal University(Natural Science Edition) ›› 2026, Vol. 44 ›› Issue (5): 101-111.doi: 10.16088/j.issn.1001-6600.2025121802

• Mathematics and Statistics • Previous Articles     Next Articles

HEIVC: an adaptive edge-incremental vertex cover algorithm for dynamic graphs with hybrid strategies

Tang Wenrui1, Chen Jingrong2*, Zhang Xueqian1   

  1. 1. School of Mathematics and Physics, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China;
    2. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China
  • Received:2025-12-18 Revised:2026-02-04 Online:2026-09-05 Published:2026-07-24

PDF (PC)

133

Abstract: The Vertex Cover (VC) problem, a classical combinatorial optimization problem in graph theory, has significant practical applications. In dynamic graph environments where edges are added incrementally, traditional static algorithms must recompute solutions from scratch at a high computational cost and with difficulty to maintain the structural stability of solutions. To address these challenges, a Hybrid Edge-Incremental Vertex Cover algorithm (HEIVC) is proposed in this paper. Starting from an initial minimal vertex cover, three complementary strategiesare integrated: rapid candidate generation, subgraph local search, and edge-independent subset partitioning combined with conflict graph-based candidate construction. Then, an adaptive module selection mechanism is designed to dynamically activate these strategies based on incremental scales and local perturbations with the objectives to maintain solution feasibility and minimality while enhancing stability and quality. Compared with the existing 2-approximation greedy algorithms and the IMVC algorithm, the results show that HEIVC achieves a significant advantage in solution size across different module combinations. These results validate the effectiveness of the proposed approach in dynamic graph incremental maintenance.

Key words: dynamic graph algorithm, vertex cover, incremental algorithm, hybrid strategy, local search, conflict graph

CLC Number:  O157.6
[1] Bondy J A, Murty U S R. Graph theory with applications[M]. London: Macmillan, 1976.
[2] Ivković Z, Lloyd E L. Fully dynamic maintenance of vertex cover[C]//Graph-Theoretic Concepts in Computer Science. Berlin, Heidelberg: Springer, 1994: 99-111. DOI: 10.1007/3-540-57899-4_44.
[3] Bhattacharya S, Henzinger M, Italiano G F. Deterministic fully dynamic data structures for vertex cover and matching[J]. SIAM Journal on Computing, 2018, 47(3): 859-887. DOI: 10.1137/140998925.
[4] Pourhassan M, Gao W R, Neumann F. Maintaining 2-approximations for the dynamic vertex cover problem using evolutionary algorithms[C]//Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM, 2015: 903-910. DOI: 10.1145/2739480.2754700.
[5] 占善华, 谢小军. 一种增量式约简方法求解最小顶点覆盖问题[J]. 计算机应用研究, 2018, 35(12): 3685-3688. DOI: 10.3969/j.issn.1001-3695.2018.12.037.
[6] 乔龙, 陈德刚. 大规模图顶点覆盖的增量算法研究[J]. 北京信息科技大学学报(自然科学版), 2020, 35(5): 51-56. DOI: 10.16508/j.cnki.11-5866/n.2020.05.010.
[7] Zhang Y, Wang S Z, Liu C J, et al. TIVC: an efficient local search algorithm for minimum vertex cover in large graphs[J]. Sensors, 2023, 23(18): 7831. DOI: 10.3390/s23187831.
[8] Cai S, Su K, Luo C, et al. NuMVC: an efficient local search algorithm for minimum vertex cover[J]. Journal of Artificial Intelligence Research, 2013, 46: 687-716. DOI: 10.1613/jair.3907.
[9] Cai S W, Hou W Y, Lin J K, et al. Improving local search for minimum weight vertex cover by dynamic strategies[C]//IJCAI’18: Proceedings of the 27th International Joint Conference on Artificial Intelligence, Washington, DC: AAAI Press, 2018: 1412-1418. DOI: 10.24963/IJCAI.2018/196.
[10] Sun R, Liu P Y, Wang Y Y, et al. InfVC: an inference-enhanced local search algorithm for the minimum vertex cover problem in massive graphs[C]//Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. August 16-22, 2025. Montreal, Canada. International Joint Conferences on Artificial Intelligence Organization, 2025: 8977-8986. DOI: 10.24963/ijcai.2025/998.
[11] 庄晟阳. 大规模图极小顶点覆盖问题的高效算法[D]. 北京:华北电力大学, 2020.
[12] 余谦, 陈庆锋, 何乃旭, 等. 基于矩阵运算加速的改进社区发现遗传算法[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 105-119. DOI: 10.16088/j.issn.1001-6600.2023052903.
[13] 李贺, 刘延娜, 杨舒琪, 等. 基于顶点组重分配的动态增量图划分算法[J]. 软件学报, 2024, 35(4): 1819-1840. DOI: 10.13328/j.cnki.jos.006842.
[14] Zhao J, Zhang Y, He L G, et al. GraphTune: an efficient dependency-aware substrate to alleviate irregularity in concurrent graph processing[J]. ACM Transactions on Architecture and Code Optimization, 2023, 20(3): 1-24. DOI: 10.1145/3600091.
[15] Yamout P, Barada K, Jaljuli A, et al. Parallel vertex cover algorithms on GPUs[C]//2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS),Lyon, France,IEEE, 2022: 201-211. DOI: 10.1109/IPDPS53621.2022.00028.
[16] 马洪玲, 马璐. 基于MOEA/D算法求解最小加权顶点覆盖问题[J]. 哈尔滨商业大学学报(自然科学版), 2022, 38(5): 530-536. DOI: 10.19492/j.cnki.1672-0946.2022.05.001.
[17] 曾宾, 宁爱兵, 付振星, 等. 最小连通顶点覆盖问题的降阶回溯算法[J]. 运筹与管理, 2024, 33(3): 28-34.
[18] 张宇. 若干图论问题的启发式算法研究[D]. 广州: 广州大学, 2024.
[19] 王方洲. 基于局部搜索和深度强化学习的顶点覆盖问题的求解及其应用研究[D]. 长春: 吉林财经大学, 2024.
[20] 李向利, 梅建平, 莫元健. 基于超图正则NMF的自适应半监督多视图聚类[J]. 广西师范大学学报(自然科学版), 2024, 42(4): 137-152. DOI: 10.16088/j.issn.1001-6600.2023110202.
[21] Bhoe S, Chan T M. Fully dynamic geometric vertex cover and matching[PP/OL].V1.arXiv(2024-02-12)[2025-12-18]. https://arxiv.org/abs/2402.07441.
[22] Herrmann A, Komusiewicz C, Morawietz N, et al. Timeline problems in temporal graphs: vertex cover vs. dominating set[PP/OL].V1.arXiv(2025-10-09)[2025-12-18]. https://arxiv.org/abs/2510.08124.
[23] Luiz F S, Iwakami A K F, Moraes D H, et al. Scalable quantum walk-based heuristics for the minimum vertex cover problem[PP/OL].V1.arXiv(2025-12-02)[2025-12-18]. https://arxiv.org/abs/2512.02940v1.
[24] Zhu E Q, Bao Q Q, Zhang Y, et al. Optimizing minimum vertex cover solving via a GCN-assisted heuristic algorithm[PP/OL].V1.arXiv(2025-03-09)[2025-12-18].https://arxiv.org/abs/2503.06396.
[25] Chen Z, Liang K K, Yuan L, et al. Recent advances in efficient dynamic graph processing[J]. Applied Sciences, 2025, 15(11): 6003. DOI: 10.3390/app15116003.
[26] Kobayashi Y, Kurita K, Matsui Y, et al. Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints[C]//Combinatorial Algorithms. Cham: Springer, 2024: 232-246. DOI: 10.1007/978-3-031-63021-7_18.
[27] Bhore S, Chan T M. Fast static and dynamic approximation algorithms for geometric optimization problems: piercing, independent set, vertex cover, and matching[M]//Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2025: 2357-2386. DOI: 10.1137/1.9781611978322.79.
[28] 荣欣琪. 动态图上最大加权独立集求解算法研究[D]. 上海: 东华大学, 2022.
[29] Li Y X, Zhang D P, Wang Y. MetaPlanner: A decentralized metaheuristic-driven framework for spatio-temporal trajectory planning of agent swarms in dynamic environments[J]. Expert Systems with Applications, 2025: 129868. DOI: 10.1137/1. 9781611978322.79.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Yuhui, CHEN Zening, HUANG Zhonghao, ZHOU Qihai. Activity Time Budget of Assamese macaque (Macaca assamensis) during Rainy Season in Nonggang Nature Reserve, Guangxi, China[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(3): 80 -86 .
[2] MIAO Xinyan, ZHANG Long, LUO Yantao, PAN Lijun. Study on a Class of Alternative Competition-Cooperation Hybrid Population Model[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(3): 25 -31 .
[3] HUANG Yanping, WEI Yuming. Multiple Solutions of Multiple-points Boundary Value Problem for a Class of Fractional Differential Equation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(3): 41 -49 .
[4] HUANG Bingfang,WEN Binghai,QIU Wen,ZHAO Wanling,CHEN Yanyan. Research on Real Time Measurement of Contact Angle Based on Lattice Boltzmann Method[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(1): 34 -43 .
[5] ZHENG Wei,WEN Guoqiu,HE Wei,HU Rongyao,ZHAO Shuzhi. Low-rank Unsupervised Feature Selection Based on Self-representation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(1): 61 -69 .
[6] TANG Guoji. Solvability for Generalized Mixed Variational Inequalities with Perturbation[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(1): 76 -83 .
[7] ZHAO Hang,WANG Renxiang,LIU Ling. Systematic Significance of Leaf Morphology in Plagiogyriaceae[J]. Journal of Guangxi Normal University(Natural Science Edition), 2018, 36(1): 142 -148 .
[8] FU Jie, ZOU Yanli, XIE Rong. Study on Synchronization and Stability of Cluster Network[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(1): 7 -15 .
[9] ZHONG Xianggui, DING Ruifang, LING Simin. Influence of the Number of Conjugacy Classes of Nonsubnormal Subgroups on the Structure of Finite Groups[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(1): 44 -48 .
[10] LI Guofeng,XU Simao. The Regulation Role of Exercise on Heme Oxygenase-1 Expression and Antioxidant Capacity in the Liver by PKC-Nrf2 Pathway[J]. Journal of Guangxi Normal University(Natural Science Edition), 2017, 35(1): 113 -118 .
Copyright © Journal of Guangxi Normal University(Natural Science Edition), All Rights Reserved.
Tel: 0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
Powered by Beijing Magtech Co. Ltd