CS170 Efficient Algorithms and Intractable Problems HW11
课程主页：
https://inst.eecs.berkeley.edu/~cs170/fa18/
课程视频：
https://www.bilibili.com/video/BV1wK411g7ck
参考资料：
https://cs170.org/assets/pdf/dis12-sol.pdf
https://www.cse.iitk.ac.in/users/rmittal/prev_course/f14/notes/lec24.pdf
http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf
https://cs170.org/assets/pdf/hw11-sol.pdf
这次回顾HW11。
2. 2-SAT and Variants
(a)
注意到$x \vee y$等价于
所以构造图，图中节点为$x,\neg x$，对于$x\vee y$，增加有向边
然后计算该图的SCC，判断强连通分量中是否同时存在$x,\neg x$即可。
(b)
参考资料：
https://cs170.org/assets/pdf/dis12-sol.pdf
此题较难，参考了习题解答。
关键点是如何区分cut和非cut，思路是对于$(u,v)\in E$，构造变量$x_u,x_v$，如果$x_u =x_v$，则$(u,v)$不是割边，否则为割边；这点利用XOR即可，对应两个clause
如果$(u,v)$为割边，则两个clause都满足；否则只能满足一个clause。
注意到假设有$k$个割边，那么存在$|E|-k$个非割边，从而满足的clause数量为
所以如果将图转换为clause，然后求出参数为$|E|+k$的Max-2-SAT问题的解，那么找到其中同时满足如下条件的对
那么边$(u,v)$属于Max-Cut的割边。
3. Reduction to (3,3)-SAT
假设$x$的出现次数$k >2$，将其替换为$x_i, i=1,\ldots,k $，然后增加子句
即可。
4. Reduction to 3-Coloring
参考资料：
https://cs170.org/assets/pdf/hw11-sol.pdf
(a)
增加边
则$x_i$为True或False。
(b)
$\Rightarrow$：
考虑左边前两个节点。
如果这两个灰色节点中存在颜色为$1$的节点，则结论成立。
如果这两个灰色节点颜色都不为$1$，则颜色必然为$0$（因为灰色节点颜色不为$2$），最终的情形如下：
0 a
0 2
0 b 1
1 0说明左边第三个灰色节点颜色为$1$。
$\Leftarrow$：
如果左边第三个灰色节点颜色为$1$，则结论成立，否则其颜色为$0$，那么两种情形如下
1 0
1 0
1/0 2 1
0 2或
0 1
2 0
1 0 1
0 2(c)
此题较难，参考了习题解答。
对每个变量$x_i$，按照(a)增加边；对于clause $C_j$，按照(b)的方式构造gadget，其中$C_j$为右边的灰色节点，$C_j$中literal为左边$3$个灰色节点，然后增加边$(C_j, \text{False}),(C_j,\text{Base})$，。
如果该图中存在$3$-coloring，不失一般性，假设$0$对应False，$1$对应True，$2$对应Base。
- 根据(a)，$x_i,\neg x_i$为颜色$0$或$1$（对应True或False）。
- 根据(i)，$C_j$为颜色$1$。
- 根据(ii)可得gadget存在合理的涂色。
- 如果literal为$x_i$，那么当颜色为$0$时赋值为False，颜色为$1$时赋值为$0$；$\neg x_i$时则相反。
5. Coloring: Two’s Company, Three’s a Crowd
(a)
构造记录节点颜色的数组$a[|V|]$，初始化为$-1$，表示未涂色。
def $dfs(v,c)$:
if $a[v] = 1-c$:
- return false
$a[v]=c$
for $(v, u)\in E$:
- $f=dfs(u, 1-c)$
- if $f=$ false:
- return false
return true
return $dfs(1, 0)$
(b)
增加一个节点$v$，其和$V$中任意节点都相连，然后给$v$涂某种颜色，在该图上求解$k+1$- coloring问题，即可求出原问题$k$-coloring问题。
6. Vertex Cover Approximation
将问题推广为带权重的最小割可以得到更一般的结论
(a)
由于取值范围更大，所以LP问题的最优解小于等于最小顶点覆盖的大小，即
(b)
参考资料：
https://www.cse.iitk.ac.in/users/rmittal/prev_course/f14/notes/lec24.pdf
http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf
对于LP的最优解$x_i$，构造如下算法：
- 如果$x_v \ge \frac 1 2 $，取$x_v’ =1$
- 否则取$x_v’ =0$
按照该方法得到的顶点集合记为$S$。
首先，证明该方法得到的解为顶点覆盖。
注意到如果整数解满足条件$x_u’ +x_v’\ge 1$，则其为顶点覆盖，而这可以由规则一满足，这是因为如果$x_u +x_v\ge 1$，那么$x_u \ge \frac 1 2$或$x_v\ge \frac 1 2$，从而按规则一可得其中必然存将其中一个变量（$x_u’$或$x_v’$）赋值为$1$，因此满足了条件。
其次证明该方法得到的解满足
注意到