COMP4141 Assignment 4 2021 Term 1
Due: Monday, 26th April, 12:00 (AEST)
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should
be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted at a high level, but the work submitted must
be your own in line with the University’s plagiarism policy.
Problem 1 (10 marks)
Consider the following decision problem:
4-Col
Input: A graph G
Question: Does G have a valid 4-colouring? That is, an assignment of one of four colours to each
vertex such that no edge has two endpoints the same colour.
Show that 4-Col is NP-complete.
Problem 2 (14 marks)
The Job scheduling problem is defined as follows: we have two processors and a set of n jobs, j1, j2, . . . , jn
each of which takes time t1, t2, . . . tn (respectively) to complete on either processor. Each job can only be
run on one processor and each processor can only process one job at a time (the order does not matter).
The Job scheduling problem is to allocate the jobs to the processors so as to minimize the processing
time: that is minimize the maximum time taken by either processor. For example, if we had four jobs
j1, j2, j3, j4 with completion times of t1 = 1, t2 = 2, t3 = 3, and t4 = 7, then the allocation of j1, j2, j3 to one
processor and j4 to the other processor would have the minimum processing time of max{1+ 2+ 3, 7} = 7.
(a) State the Job scheduling problem as a decision problem. (4 marks)
(b) Show that the decision version of the Job scheduling problem is NP-complete. (10 marks)
Problem 3 (16 marks)
The Knapsack problem is the problem of maximizing the value of contents of a knapsack, without ex-
ceeding a specified weight limit. More precisely, the decision problem is:
1
Knapsack
Input: A set of n pairs of positive integers: {(w1, v1), (w2, v2), . . . (wn, vn)}; and two positive integers
W and V.
Question: Is there a subset K ⊆ {1, 2, . . . n} such that
∑
i∈K
wi ≤W and ∑
i∈K
vi ≥ V?
Show that Knapsack is NP-complete.
Problem 4 (30 marks)
Consider the following graph:
x
y y′
x
(a) Give a valid 3-colouring of this graph where x and y have different colour. (2 marks)
(b) Give a valid 3-colouring of this graph where x and y have the same colour. (2 marks)
(c) What can be said about any valid 3-colouring of this graph? Justify your answer. (4 marks)
A graph is planar if it can be drawn on the plane with no crossing edges. The graph above is an example
of a planar graph.
(d) Consider the following decision problem:
Planar 3-Col
Input: A planar graph G
Question: Does G have a valid 3-colouring?
Show that Planar 3-Col is NP-complete. Hint: Use the above graph to “uncross” edges (16 marks)
(e)∗ Prove that there is no planar graph G, with x, y, x′, y′ on an outer face (in that order), that satisfies
the conditions indicated in (a), (b) and (c), but with a 4-colouring rather than a 3-colouring. (6 marks)
2
Problem 5 (20 marks)
A boolean program is a program in which all variables have type Boolean, and which may use the following
constructions:
• Boolean expressions e may be formed from boolean variables using the operators ∧,∨,¬ and con-
stants true, false
• if x is a variable and e is a Boolean expression, then the statement x := e is a program. It runs by
calculating the value of e and updating x to have this value.
• If P and Q are programs, then P; Q is a program that runs by first executing P and then executing
Q.
• If P and Q are programs and e is a boolean expression, then
if e then {P} else {Q}
is a program that runs by first calculating the value of e and executing P if e is true and executing Q
otherwise.
• If P is a program and e is a boolean expression, then
while e do {P}
is a program that runs by repeatedly testing if e is true and executing P if so. The loop exits as soon
as e evaluates to false.
Boolean programs run starting from some given initial assignment pi to their boolean variables, and
update this assignment during their execution. They may terminate or not, possibly depending on the
initial assignment. For example
while x do {if y then {y := false} else {y := true}}
when run from initial assignment pi, halts immediately if pi(x) = false and is non-terminating if pi(x) =
true.
Consider the following decision problem
BP-Halt
Input: A boolean program P
Question: Does there exist an assignment pi such that P terminates when run from initial assign-
ment pi?
Show that BP-Halt is PSPACE-complete.
Problem 6 (10 marks)
Consider the following decision problem:
3
2-SAT
Input: A boolean formula ϕ in CNF with at most 2 literals per clause
Question: Is ϕ satisfiable?
Show that
PATH ≤L 2-SAT.
Hint 1: Find a reduction first then check if it is log-space.
Hint 2: The 2-CNF clause (¬x ∨ y) is logically equivalent to the expression (x → y).
4































































































学霸联盟