课程主页:

https://cs170.org/

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$,因此满足了条件。

其次证明该方法得到的解满足

注意到