Abstract:

The Minimum Partial Vertex Cover (MPVC) problem aims to identify a minimum set of vertices that covers at least k edges in a graph and arises in performance-critical scenarios such as network monitoring, fault detection, and coverage optimization under resource constraints. As a classical NP-hard combinatorial optimization problem, MPVC requires efficient heuristic approaches to balance solution quality and computational efficiency in large-scale systems.

This paper proposes an Improved Randomized Iterated Greedy (IRIG) algorithm that incorporates adaptive mechanisms to regulate both the construction greediness and the intensity of solution perturbation based on online performance feedback. The approach combines a reactive Restricted Candidate List, a cooling-warming destruction strategy, an elite solution pool, and a reverse-delete pruning procedure to enhance solution compactness while maintaining robustness. The effectiveness of the proposed method is evaluated on 31 benchmark instances from the DIMACS and BHOSLIB datasets. Experimental results indicate that IRIG achieves competitive and often superior performance compared to representative baseline methods, while exhibiting stable behavior across multiple independent runs. These results suggest that the proposed approach provides an effective and computationally efficient solution framework for MPVC in performance-oriented optimization contexts.

Key words: minimum partial vertex cover, greedy heuristic, covering problems, combinatorial optimization problem