关键词: 集合覆盖，撞碰集，近似算法，固定参数可解

Abstract: Set cover and hitting set problems are two important W[2]-complete problems. Set cover problem is applied widely in the testing of VI_SI 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 fo-cused 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. hhe 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 arc outlined.

Key words: Set cover, Hitting set, Approximation algorithm, Fixed parameter tractable