南京理工大学学报（自然科学版）2026，Vol.50Issue(3)：263-273,11.DOI:10.14177/j.cnki.32-1397n.2026.50.03.003
最小碰集问题分支定界算法约简与分支策略优化
Optimization of reduction and branching strategies for branch-and-bound algorithm for the minimum hitting set problem
摘要
Abstract
The minimum hitting set problem is an NP-hard problem and has wide applications in fields such as fault diagnosis and drug design.Recently,Bläsius proposed a branch-and-bound algorithm that was the first to outperform mixed-integer linear programming approaches.Through an in-depth analysis,two performance limitations were found in the algorithm.First,the asymmetric reduction efficiency between the left and right branches results in inefficient reduction in the right branch.Second,the degree-based branch vertex selection strategy remains relatively coarse-grained.This paper proposes two optimization strategies:first,an asymmetric reduction strategy based on branch characteristics to reduce inefficient reduction operations in the right branch and improve overall reduction efficiency;second,a bound-based branch vertex set selection strategy based on bound calculation,along with the design of a heuristic scoring mechanism to minimize the branch vertex set.Experimental results on the UCC,CVD,EN1 and EN2 datasets show that the asymmetric reduction strategy significantly improves the reduction efficiency of the algorithm and accelerates the solving speed of the algorithm;the branch vertex selection strategy based on bound calculation can reduce the search tree size by 30%to 80%on most graph instances.The new algorithm combining two optimization strategies greatly improves solving speed and overall solves six more graph instances than the original algorithm.关键词
最小碰集问题/分支定界算法/约简策略/分支策略Key words
minimum hitting set problem/branch-and-bound algorithm/reduction strategy/branching strategy分类
信息技术与安全科学引用本文复制引用
罗文桃,罗来文,郑知菲,江华..最小碰集问题分支定界算法约简与分支策略优化[J].南京理工大学学报（自然科学版）,2026,50(3):263-273,11.基金项目
国家自然科学基金(62162066) （62162066）
