算法代写 | Computer Science C63 Homework Assignment #4

这个作业是完成NP问题相关的算法
Computer Science C63 August 3, 2020
Homework Assignment #4

Question 1. (10 marks) The disjoint set problem, abbreviated DisjSets, is the following decision
problem:
Instance: hU, C, ki, where U is a set (the “universe”), C ⊆ P(U) is a collection of subsets of U, and k is
a positive integer.
Question: Are there k disjoint sets in C?
For example, if U = {n ∈ Z : 1 ≤ n ≤ 10}, C =

{1, 3, 5}, {2, 3, 7}, {2, 7, 9}, {1, 2}

, then the answer for
instance hU, C, 2i is yes, but the answer for instance hU, C, 3i is no.
Prove that DisjSets is NP-complete.
Hint: Use the fact that IndependetSet is NP-complete.
Question 2. (10 marks) An (s, t) Hamiltonian path in a directed graph G = (V, E), where s, t ∈ V
and s 6= t, is a path in G that starts in s, ends in t, and visits every node exactly once. The (s, t)-Directed
Hamiltonian Path (DHP) problem is the following decision problem:
Instance: hG, s, ti, where G = (V, E) is a directed graph, and s, t ∈ V such that s 6= t.
Question: Does G have an (s, t) Hamiltonian path?
Prove that (s, t)-DHP is an NP-complete problem.
1
Note. Having proved that (s, t)-DHP is NP-complete, one can prove that the corresponding problem
in undirected graphs is also NP-complete. You can do this by reducing (s, t)-DHP to its undirected
counterpart using the same trick that we used to reduce DHC (the Directed Hamiltonian Cycle problem)
to UHC (its undirected counterpart). You should do this as an exercise, but don’t include it with your
answer to this question.
Question 3. (10 marks) Vassos has n topics P1, P2, . . . , Pn that he wants to present to his class. Each
topic Pi has an associated duration di — the amount of time that he needs to present it. He must present
these topics in k lectures, each of duration at most T. (He does not need to completely fill each lecture.)
The topics can be presented in any order: any one of them could be in any lecture. Vassos’ problem is to
determine whether he can present all n topics in the k lectures without exceeding the length of any lecture.
For example, if he has 10 topics to present, 5 of which take 10 minutes each, 2 take 15 minutes each,
1 takes 20 minutes, and 2 take 25 minutes each (for a total of 150 minutes) he can present all of them in
three 50-minute lectures. On the other hand, if he has 8 topics to present, 1 of which takes 5 minutes,
1 takes 15 minutes, 4 take 20 minutes each, and 2 take 25 minutes each (again for a total of 150 minutes)
it is impossible to present them all in three 50-minute lectures.
Vassos’s dilemma (VDil) is the following decision problem:
Instance: hD, k, Ti, where D = d1, d2, . . . , dn is a sequence of positive integers (the durations of the topics
that Vassos wants to present); k ≥ 2 is a positive integer (the number of lectures in which to present these
topics); and T is a positive integer (the maximum duration of each lecture).
Question: Can Vassos present these n topics (in any order) in k lectures each of duration at most T?
Prove that VDil is an NP-complete problem.
Hint: Reduce a problem we have proved to be NP-complete to VDil when k = 2. This is simpler to
do, and proves a stronger result: VDil is NP-complete even in the special case k = 2. (It is easy to see
that for k = 1 the problem is in P.)
Question 4. (10 marks) [EXTRA CREDIT] Prove that the 3-colourability problem from Assignment 3 is NP-complete, using a reduction from 3Sat that uses the “gadgets” described in Figure 1. Do
not prove this using a different reduction!
Intuition and hints: Given a 3-CNF formula φ you want to construct a graph Gφ that is 3-colourable
if and only if φ is satisfiable.
For each variable x in φ introduce a “variable gadget” as shown in Figure 1(a). For the entire graph
introduce a single “colour palette gadget” as shown in Figure 1(b). For each clause `∨`
0∨`
00 of φ introduce
a “clause gadget” as shown in Figure 1(c). Your goal is to assemble the graph Gφ from such gadgets.
The colour palette is a clique of size 3 and its three nodes must therefore have three different colours,
which we think of as T (“true”), F (“false”), and N (“neutral”).
We want to force each variable gadget node to be coloured T or F. How should you connect it to the
palette gadget to ensure this? Note that once we have forced the two nodes of each variable gadget to be
coloured T or F, the edge between them ensures that they won’t both be assigned the same colour, which
is what we want: a variable and its negation must not have the same truth value.
Next consider the “clause gadget” shown in Figure 1(c). The nodes `, `
0
, and `
00 represent literals, which
are nodes of the variable gadgets. If these nodes are assigned colours T or F (in any combination) and
we force the node labeled ` ∨ `
0 ∨ `
00 to be coloured T, the remaining nodes of the gadget can be coloured
consistently (meaning that no adjacent nodes are assigned the same colour) using our three colours T, F,
and N if and only if at least one of `, `
0
, and `
00 is coloured T. (This fact is something that you must
prove as part of the argument that your reduction works.) So, in some sense, this gadget can be made to
act like a logical-or of the truth values (i.e., colours) of `, `
0
, and `
00
.
1Smart-aleck answers such as “yes, by speaking faster and faster, as he is known to do”, receive a chuckle but no credit.
2
(b) Colour palette gadget
x x
T F
N
(c) Clause gadget
` `
0
`
00
` ∨ `
0 ∨ `
00
(a) Variable gadget
Figure 1: Gadgets for reduction of 3Sat to 3-colourability
Given the above discussion you should be able to describe how to combine these gadgets to construct
from φ a graph Gφ that is 3-colourable if and only if φ is satisfiable.