CS170 Efficient Algorithms and Intractable Problems Section10

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

这次回顾Section 10。

1. NP Basics

1. 无法判断$B$
2. $A$属于$\mathrm P$
3. $B$属于$\mathrm{NP-hard}$
4. 无法判断$A$

2. Hitting Set

下面证明顶点覆盖问题可以规约到此问题。

对于图$G(V,E)$以及顶点$v$，构造集合

$$S_{(u,v)}=\{u,v\}$$

那么该集合族大小小于等于$b$的Hitting Set即为原问题大小小于等于$b$的顶点覆盖，这是因为Hitting Set为$S=\{v_1,\ldots,v_n\}$，该顶点集合和每个$S_{(u,v)}$（边）都有交点。

3. Reliable Network

此题参考了习题解答。

下面证明Rudrata问题可以规约到Reliable Network问题。

取

• $b=n$
  • 最多$n$条边
• $d_{ij}=1,(i,j)\in E,d_{ij}=n+1,(i,j)\in E$
  • 这样取值保证只取$E$中包含的边。
• $r_{ij}=2$
  • 任意两点之间有$2$条路径（对应环）

那么利用Reliable Network算法可以求解Rudrata问题，后续只要说明Reliable Network是NP即可，即对于$E$（邻接矩阵），在多项式时间内验证：

• $\sum_{(i, j) \in E} d_{i j}\le d$
  • 显然。
• $i\to j$有恰好$r_{ij}$条路径
  • 以$i$为起点，$j$为终点的最大流问题。

4. Dominating Set

此题参考了习题解答。

证明最小集合覆盖问题可以规约到此问题。

假设集合族为$\{S_1,\ldots, S_n\}$，给定集合$S_0$以及预算$b$，构造图$G$，其中顶点集合为

$$V=S_0\cup \{S_1,\ldots, S_n\}$$

边集合为

$$E=\{(u,S_i)| u\in S_0, u\in S_i\}$$

求出该图的Dominating Set $S$（其中$k=b$），那么$S_0$中的元素或者属于$S$，或者和$S$中某个$S_i$相邻，对于前一种情况，将该元素替换为某个相邻的顶点$S_i$，利用该方法最终可以将$S$变换为$S_i$的集合，该集合即为最小集合覆盖。