COMP 3804 — Assignment 4
Due: Sunday April 11, 23:59.
Assignment Policy:
Your assignment must be submitted as one single PDF file through cuLearn.
Use the following format to name your file:
LastName StudentId a4.pdf
Late assignments will not be accepted. I will not reply to emails of the
type “my internet connection broke down at 23:57” or “my scanner stopped
working at 23:58”, or “my dog ate my laptop charger”.
You are encouraged to collaborate on assignments, but at the level of discussion only.
When writing your solutions, you must do so in your own words.
Past experience has shown conclusively that those who do not put adequate effort into
the assignments do not learn the material and have a probability near 1 of doing poorly
on the exams.
When writing your solutions, you must follow the guidelines below.
– You must justify your answers.
– The answers should be concise, clear and neat.
– When presenting proofs, every step should be justified.
Question 1: Write your name and student number.
Question 2: The (0, 1)-integer programming problem is defined as follows:
IntProg := {(A, c) : A is an integer m× n matrix for some integers m and n,
c is an integer vector of length m, and
x ∈ {0, 1}n such that Ax ≤ c (componentwise) }.
Prove that the language IntProg is in NP.
1
Question 3: The subset sum problem is defined as follows:
SubsetSum := {(a1, a2, . . . , am, b) : m, a1, a2, . . . , am, b are integers and
I {1, 2, . . . ,m} such that ∑i∈I ai = b}.
Prove that SubsetSum ≤P IntProg, i.e., in polynomial time, SubsetSum can be reduced
to IntProg.
Question 4: The three-coloring problem is defined as follows:
3Color := {G : G is a graph whose vertices can be colored using three colors
such that any two adjacent vertices have distinct colors }.
The clique covering problem is defined as follows:
CliqueCover := {(G, k) : G = (V,E) is a graph whose vertex set V can be
partitioned into k subsets V1, V2, . . . , Vk such that
each subset Vi forms a clique in G }.
(4.1) Prove that the language 3Color is in NP.
(4.2) Prove that the language CliqueCover is in NP.
(4.3) Prove that 3Color ≤P CliqueCover, i.e., in polynomial time, 3Color can be
reduced to CliqueCover.
Question 5: You are given
a sequence A = (A1, A2, . . . , Ak), where each Ai is a set consisting of three elements,
and
a sequence B = (B1, B2, . . . , B`), where each Bj is a set consisting of two elements.
This pair (A,B) of sequences is called good if there exists a set T such that
T contains at least one element of each set Ai, and
T contains at most one element of each set Bj.
The Problem without a Name is defined as follows:
ProblemWithoutAName := {(A,B) : the pair (A,B) is good}.
Prove that the language ProblemWithoutAName is NP-complete.
Hint: You may remember from class that 3Sat is NP-complete.
2
