A Dual-Evaluation Local Search Algorithm for the Minimum Hitting Set Problem

Authors:
Open Access
Publisher website
Google Scholar
Abstract
The Minimum Hitting Set (MinHS) problem is a classic NP-hard problem in combinatorial optimization, widely applied across fields such as artificial intelligence diagnosis, bioinformatics, and network monitoring. This paper proposes a local search algorithm with Dual-evaluation mode, named DemHS (Dual-evaluation mode search algorithm), tailored for large-scale hitting set instances. The evaluation employs two types of functions: strong and weak. Strong evaluation accurately calculates the exchange gain by introducing a cross-correction term within the local neighborhood defined by an inserted vertex; meanwhile, weak evaluation quickly estimates the gain through global random sampling to broaden the search scope. These two functions synergistically guide the search process. Furthermore, we introduce an age strategy to break ties and enhance the diversity of the search path. When no improvements are made for extended iterations, a large-scale random perturbation is executed to help the algorithm escape local stagnation. Comparative experiments were conducted using 200 public hitting set instances (100 metaheuristic and 100 exact cases) from PACE-2025. The results show that, in the metaheuristic case group, DemHS improves the record on 62 instances and in the precise case group, DemHS obtains optimal solutions across all tested instances. The ablation studies demonstrate a significant positive gain from the dual-evaluation neighborhood structure on optimization results.
Funding Information
  • National Natural Science Foundation of China (62402164)

This publication has 21 references indexed in Scilit: