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

#### 2. 2-SAT and Variants

##### (b)

https://cs170.org/assets/pdf/dis12-sol.pdf

#### 4. Reduction to 3-Coloring

https://cs170.org/assets/pdf/hw11-sol.pdf

##### (b)

$\Rightarrow$：

0		a
0		2
0		b						1

1						0

$\Leftarrow$：

1   	0
1		0
1/0		2						1

0						2

0   	1
2		0
1		0							1

0						2
##### (c)

• 根据(a)，$x_i,\neg x_i$为颜色$0$或$1$（对应True或False）。
• 根据(i)，$C_j$为颜色$1$。
• 如果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)$

#### 6. Vertex Cover Approximation

##### (b)

https://www.cse.iitk.ac.in/users/rmittal/prev_course/f14/notes/lec24.pdf

http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf

• 如果$x_v \ge \frac 1 2$，取$x_v’ =1$
• 否则取$x_v’ =0$