往期文章：
本文介绍如何通过3SAT归约，进而证明支配集是NPC问题。
3SAT问题
$\rightarrow$ 3-Satisfiability (3Sat)
给定一个有穷的布尔变量集合$X=\lbrace x_1,x_2,\ldots,x_n \rbrace$，变量$x_i$取值为1或者0，另有一组子句$C=\lbrace c_1,c_2,\ldots,c_m \rbrace$，$\mathbb{C}=c_1\wedge c_2 \wedge \ldots \wedge c_m$，$c_i = x_j \vee x_k \vee x_l$。求是否存在一组取值使得$\mathbf{C}$为真，即任意$c_i$为真。
Dominating Set(支配集)
$\rightarrow$ Dominating Set
给定图$G$，正整数$k$，是否存在dominating set的大小最多为$k$。
Dominating Set $D$是点集$V$的一个子集，并且对于不在$D$中的点$v$，至少存在一条边$(u,v)\in E$，$u\in D$。
解题思路：
我们知道将支配集归约到3SAT进而证明3SAT是NPC是很容易的。CSCI5320的习题里，要进行相反方向的归约，将3SAT的问题转化成支配集的问题进行求解，相对来说比较难。
- 对于每个变量$x_i$，我们都构造两个点，$x_i$和$\overline{x_i}$，以及一条边$(x_i,\overline{x_i})$
- 对于$c_i$当中的三个变量$x_j \vee x_k \vee x_l$，我们构造一个点$c_i$，三条边$(x_j,c_i)$,$(x_k,c_i)$和$(x_l,c_i)$。如果布尔表达式取反，那么我们可以对应的连接$(\overline{x_j},c_i)$。
- 最关键的一步，我们如何确保$x_i$,$\overline{x_i}$恰好有且仅有一个点落在支配集里。我们增加一个点$y_i$，并且添加两条边$(x_i,y_i)$与$(\overline{x_i},y_i)$。
那么我们可以知道$\mathbb{C}$可满足当且仅当上述构造的图中有一个大小$m$的支配集。
证明：
- 当$\mathbb{C}$可满足时，显而易见，对应取真的变量构成一个支配集。
- 当上述构造的图中有一个大小为$m$的支配集时，因为$(x_i,\overline{x_i},y_i)$三个点当中最少有一个点在支配集当中，所以支配集的大小最小为$m$。那么我们可以得到结论$(x_i,\overline{x_i},y_i)$三个点恰好有且仅有一个点在支配集当中。当$y_i$在支配集当中时，我们总可以由$(x_i,\overline{x_i})$当中的一个点来替换。那么由此便可得到一个令$\mathbb{C}$可满足的取值。