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)

1

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] Tang Chenghua, Yi Jianbing, Wu Xin, Xiong Wenwu, Wang Jingyong. A review of cross-domain few-shot image semantic segmentation methods[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(4): 1 -27 .
[2] Tian Sheng, Xie Hualin, Chen Dong. Energy management strategy for fuel cell vehicles based on improved deep reinforcement learning[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(4): 28 -45 .
[3] Zhang Xu, Liu Didi. Intelligent charging/discharging scheduling strategy for electric vehicles based on TD3 algorithm[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(4): 46 -55 .
[4] Yan Yuanyang, Xie Lirong, Zhang Longjun, Ren Juan, Huang Chenchen, Hu Chao. Ultra-short-term wind power prediction model based on multi-objective optimization[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(4): 56 -70 .
[5] Lü Hui, Su Jing, Xiong Feng, Zhang Duanyu, Chang Wenhan, Wang Can, Ma Hui. Bi-level coordinated optimization scheduling method for microgrid clusters based on improved SAC algorithm[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 1 -15 .
[6] Yang Zhen, Tang Yue, Geng Zhaojie, Yin Xu, Huang Yong. Giant magnetoimpedance biosensor based on composite amorphous wire for sensitive detection of cTnI[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 16 -26 .
[7] Tian Peiyi, Jiang Pinqun, Song Shuxiang, Xia Haiying, Cai Chaobo. High-efficiency and fast-stabilizing boost charge pump controlled by multi-phase clock[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 27 -37 .
[8] Chen Geng, Song Shuxiang, Jiang Pinqun, Cai Chaobo. Design of 12 bit 100 MS/s successive approximation analog-to-digital converter[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 38 -48 .
[9] Suo Guidong, Lu Zhimin, Li Zili. EMD-YOLO: a PCB defect detection model based on improved YOLO11n[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 49 -62 .
[10] Hu Zhiqiang, Lü Xiaoqi, Gu Yu. Skin lesion segmentation model based on improved Mamba local feature acquisition[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 63 -74 .
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