Set Cover和Hitting Set问题的研究进展

Set Cover and Hitting Set:A Survey

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。

Set cover and hitting set problems are two important W[2]-complete problems. Set cover problem is applied widely in the testing of VLSI devices and crew scheduling. Hitting set problem has important applications in biological computation. In the parameterized computation and complexity theory, Set Cover and hitting set problems have been focused on. This paper firstly introduced the categories and definitions of set cover and hitting set problems, then analyzed and summarized the computational complexity and the recent research results about these problems. The paper proved the computational complexity levels of （k, h）-set Cover and （k, d）-Set Cover. Finally, the main points are concluded and some future research issues are outlined.