基于混合策略的动态图顶点覆盖边增量自适应算法

doi:10.16088/j.issn.1001-6600.2025121802

广西师范大学学报（自然科学版） ›› 2026, Vol. 44 ›› Issue (5): 101-111.doi: 10.16088/j.issn.1001-6600.2025121802

基于混合策略的动态图顶点覆盖边增量自适应算法

唐文睿¹, 陈京荣^2*, 张雪倩¹

1.兰州交通大学数理学院, 甘肃兰州 730070;
2.兰州交通大学交通运输学院, 甘肃兰州 730070

收稿日期:2025-12-18 修回日期:2026-02-04 出版日期:2026-09-05 发布日期:2026-07-24
通讯作者: 陈京荣(1975—),女, 甘肃榆中人,兰州交通大学教授。E-mail: chenjr@mail.lzjtu.cn
基金资助:
国家自然科学基金(52362044);甘肃省科技计划(24JRRA904,24JRRA847)

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

Tang Wenrui¹, Chen Jingrong^2*, Zhang Xueqian¹

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

摘要/Abstract

摘要： 顶点覆盖问题是图论中一个经典的组合优化问题,在实际问题中具有重要应用。对于动态图环境,随着边不断增量式加入,传统静态算法需从头求解,计算代价高且难以保持解结构的稳定性,因此,本文提出混合策略边增量顶点覆盖算法(hybrid edge-incremental vertex cover,HEIVC)。算法在初始极小顶点覆盖基础上,融合快速候选生成、子图局部搜索与边独立子集划分与冲突图的候选构造3种互补策略,并通过自适应模块选择机制在不同增量尺度和局部扰动条件下动态调整启用策略,旨在保证解合法性与极小性的同时提高稳定性与质量。对比现有2-近似贪心算法和IMVC算法,结果表明,HEIVC在不同模块组合下的覆盖规模表现出显著优势,验证了算法在动态图增量维护中的有效性。

关键词: 动态图算法, 顶点覆盖, 增量算法, 混合策略, 局部搜索, 冲突图

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

中图分类号: O157.6

唐文睿, 陈京荣, 张雪倩. 基于混合策略的动态图顶点覆盖边增量自适应算法[J]. 广西师范大学学报（自然科学版）, 2026, 44(5): 101-111.

Tang Wenrui, Chen Jingrong, Zhang Xueqian. HEIVC: an adaptive edge-incremental vertex cover algorithm for dynamic graphs with hybrid strategies[J]. Journal of Guangxi Normal University(Natural Science Edition), 2026, 44(5): 101-111.

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于混合策略的动态图顶点覆盖边增量自适应算法

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 10