证明碰撞集问题(Hitting Set)是NP-complete

Problem

In the HITTING SET problem, we are given a family of sets {S1, S2, ... , Sn} and a budget b, and we wish to find a set H of size ≤ b which intersects every Si, if such an H exists. In other words, we want H ∩ Si ≠ ∅ for all i.

Show that HITTING SET is NP-complete.

Solution

  1. 首先，HITTING SET是一个NP问题。

    对于H中的所有元素，和Si逐个比较是否有交集并且大小小于等于b，这个操作显然是多项式时间复杂度的问题。

  2. 其次，Vertex Cover是一个NP难问题。

    由书本P241、242，可知最小顶点覆盖问题（Vertex Cover）是NP难问题。

  3. 最后，将Vertex Cover归约到HITTING SET，即可证明碰撞集问题是一个NP完全问题。

    假设要求图G(V, E) 的Vertex Cover，可以建立一个HITTING SET实例，其中S1, S2, ... , Sn是图G的各条边，比如：S1={v1, v2}，这样可以构造出|E|个集合，求图G的Vertex Cover，可以转化成求这|E|个集合的HITTING SET。Vertex Cover的顶点就是H的元素，Vertex Cover的个数即为b。

最新文章

  1. windows 环境和linux环境下 ping命令的区别：
  2. 获取PHP文件绝对地址$_SERVER['SCRIPT_FILENAME'] 与 __FILE__ 的区别
  3. 16个常用IO流
  4. java 中遍历hashmap 和hashset 的方法
  5. 【Leetcode】【Medium】Pow(x, n)
  6. ASP.NET MVC- ActionFilter的使用
  7. JSOI2007建筑抢修
  8. OWASP Top 10 – 2013, 最新十大安全隐患（ASP.NET解决方法）
  9. MyGui 3.2.0(OpenGL平台)的编译（五篇文章）
  10. Python之基础（一）
  11. 1021 Fibonacci Again （hdoj）
  12. PHP中如何定义类及其成员属性与操作
  13. SVN和Git的功能和区别，尚学堂SVN和Git学习视频资料免费下载
  14. linux基础之正则表达式
  15. 20165326 Linux系统安装及学习
  16. Window环境下Python和Django的安装，以及项目的创建
  17. TypeError: 'MongoClient' object is not callable
  18. chrome浏览器使用jqprint插件打印时偶尔空白页问题
  19. Shell基础学习(三) 传递参数
  20. 怎么创建Porlet项目

热门文章

  1. if return 和 if else
  2. java 获取项目根目录
  3. POJ3376 Finding Palindromes —— 扩展KMP + Trie树
  4. EOS智能合约为何选择Web Assembly(wasm)
  5. 让 SyntaxHighlighter 3.x 支持 Lua 语法着色
  6. html5--6-44信纸设计
  7. hdu 4022 Bombing（map,multiset）
  8. LibSVM学习详细说明
  9. 【POJ 1655】 Balancing Act
  10. CodeForces 1103C. Johnny Solving