# 算法设计与分析笔记0x0E —— Part 3 NP完全

## Partitioning Problems

### 3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T X × Y × Z of triples, does there exist a set of n triples in T such that each element of X Y Z is in exactly one of these triples?

Claim. 3-SAT $\leq _p$ 3D-MATCHING
Pf. Given an instance Φ of 3-SAT, we construct an instance of 3D-matching that has a perfect matching iff Φ is satisfiable.

Construction

• Create gadget for each variable x i with 2k core elements and 2k tip elements.
• No other triples will use core elements.
• In gadget i, 3D-matching must use either all the grey triples(corresponding to x i = true) or all the blue ones (corresponding to x i = false).
• For each clause Cj create gadget with two elements and three triples.
• Exactly one of these triples will be used in any 3D-matching.
• Ensures any 3D-matching uses either
1. grey core of x1
1. blue core of x2
1. grey core of x3
• There are 2nk tips. nk covered by blue/gray triples, k covered by clause triples.
• To cover the remaining (n-1)k tips, create (n-1)k cleanup gadgets, each connected to all the 2nk tips.
• Q. What are X, Y, and Z? Does each triple contain one element from each of X, Y, Z?
• A. X = red, Y = green, Z = blue
• Pf. =>
• If 3D-matching, then assign xi according to the color of the selected triples in gadget xi
• Pf. <=
• If Φ is satisfiable, then use assignment of xi to select gadget xi triples and use true literal in Cj to select gadget Cj triple

Note

• https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/3dm.pdf
• 每个3-SAT中的变量转换成一个零件，含四个“核心”和四个“边梢”两个部分
• 每一个clause转换为一个含两个“核心”的零件，根据变量取值连接变量零件中的一个“边梢”
• 对每个没有被cover的“边梢”，创建一个“清理零件”去cover掉

### 3-Colorability

3-COLOR Given an undirected graph G does there exist a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?
Claim. 3-SAT p 3-COLOR
Pf. Given 3-SAT instance Φ, we construct an instance of 3-COLOR that is 3-colorable iff Φ is satisfiable.
Construction.

1. For each literal, create a node.
1. Connect each literal to its negation.
1. Create 3 new nodes T, F, B; connect them in a triangle
1. Connect each literal to B.
1. For each clause, add gadget of 6 nodes and 13 edges (to be described later)

Claim. Graph is 3-colorable iff Φ is satisfiable.
Pf. => Suppose graph is 3-colorable.

• Set all the literals with T color to true.
1. ensures each literal is T or F.
1. ensures a literal and its negation are opposites.
1. ensures at least one literal in each clause is T.

Pf. <= Suppose 3-SAT formula Φ is satisfiable

• Color all true literals T.
• Color node below green node F, and node below that B.
• Color remaining middle row nodes B.
• Color remaining bottom nodes T or F as forced.

Note

• 每个变量和它的negation必须是不同的颜色
• 每个节点颜色必须和B不同
• B T F为不同颜色

## Numerical Problems

### Subset Sum

SUBSET-SUM. Given natural numbers w1, …, wn and an integer W, is there a subset that adds up to exactly W?
Claim. 3-SAT p SUBSET-SUM
Pf. Given an instance Φ of 3-SAT, we construct an instance of SUBSET-SUM hat has solution iff Φ is satisfiable.
Construction. Given 3-SAT instance Φ with n variables and k clauses, form 2n + 2k decimal integers, each of n+k digits, as illustrated below.

• One digit for each variable and for each clause
• Two numbers for each variable
• Two numbers for each clause
• Sum of each variable digit is 1; sum of each clause digit is 4.

Claim. Φ is satisfiable iff there exists a subset that sums to W.
Pf. => Suppose Φ is satisfiable

• Choose numbers corresponding to each true literal
• Since Φ is satisfiable, each clause digit sums to at least 1 from the chosen numbers
• Choose dummy numbers to make each clause digit sum to 4.

Pf. <= Suppose there is a subset that sums to W

• Each variable digit forces the subset to choose exactly one from x and ¬x
• Each clause digit forces the subset to choose at least one literal in the clause
• Assign each variable according to the chosen literal

3D-MATCHING reduces to SUBSET-SUM
Construction. Let X Y Z be a instance of 3D-MATCHING with triplet set T. Let n = |X| = |Y| = |Z| and m = |T|.

• Let X = {x1, x2, x3, x4}, Y = {y1, y2, y3, y4} , Z = {z1, z2, z3, z4}
• For each triplet t= ( xi, yj, zk) T, create an integer wt in base m+1 with 3n digits that has a 1 in positions i, n+j, and 2n+k.

Claim. 3D-matching iff some subset sums to W = 111,…, 111.

### Scheduling With Release Times

SCHEDULE-RELEASE-TIMES. Given a set of n jobs with processing time ti, release time ri, and deadline di, is it possible to schedule all jobs on a single machine such that job i is processed with a contiguous slot of ti time units in the interval [ri, di]?
Claim. SUBSET-SUM p SCHEDULE-RELEASE-TIMES.
Pf. Given a instance of SUBSET-SUM w1, …, wn, and target W.

• Create n jobs with processing time ti = wi, release time ri = 0, and deadline $d_i = 1 + \sum_{j} w_j$.
• Create job 0 with t0 = 1, release time r0 = W, and deadline d0 = W+1.