Algorithms 3927 Assignment 5 The University of Sydney 2019 Semester 1 School of Computer Science
This assignment is for COMP3927 students only.
Task 1: [20 marks]
You are a pirate captain. After looting a cargo ship, you need to divide up the n treasure chests among k pirates in an egalitarian manner to avoid mutiny. A reasonable way to model this is that the happiness of a pirate is the total value of his allocation, and the goal is to find an allocation such that least-happy pirate is as happy as possible.
This suggests the following decision problem called Mutiny-Free-Allocation (or MFA for short). The input to Mutiny-Free-Allocation consists of:
• a list of n non-negative integers v1, . . . , vn, • the number of pirates k, and
• a lower bound l.
The problem is to decide if there is a partition of v1,…,vn into k subsets S1,…,Sk such that each subset Si sums to at least l.
Your task is to prove that
(a) Mutiny-Free-Allocation is in NP,
(b) Mutiny-Free-Allocation is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problem.]
Task 2: [40 marks]
You are planning a road trip across Australia and need to decide which destinations you can reach from Sydney. The constraints are as follows: each road has a length and a toll cost; moreover, your car can travel K kilometers before it breaks down and you have D dollars. A destination is reachable if there exists a path from Sydney to the destination with total length at most K and total cost at most D.
This suggests the following decision problem called Road-Trip-Reachability (or RTR for short). The input consists of:
• an undirected graph G = (V,E) where each edge e has a non-negative integer length l(e) and a non-negative integer cost c(e),
• a source vertex s and a destination vertex t in V ,
• a non-negative integer length budget K and a non-negative integer cost budget D.
The problem is to decide if there exists a simple path P from s to t in G with total length e∈P l(e) ≤ K and total cost e∈P c(e) ≤ D.
Your task is to prove that
(a) Road-Trip-Reachability is in NP,
(b) Road-Trip-Reachability is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problem.]
Task 3: [40 marks]
Consider the following decision problem. The input consists of:
• an undirected graph G = (V, E), where each edge e has a non-negative integer cost c(e), • arootvertexr∈V andterminalverticest1,…,tk ∈V,
• a non-negative integer upper bound B.
1
The problem is to decide if there is a collection of paths P1 , . . . , Pk where Pi is a shortest path from ti to r (shortest by cost) such that the total cost of the union of these paths is at most B, i.e.
ce ≤ B. e∈P1 ∪…∪Pk
Your task is to prove that
(a) this problem is in NP
(b) this problem is NP-hard using a Karp reduction. [Hint: Reduce from the Set Cover problem.]
Submission details
• Submission deadline is Wednesday May 29th, at 23:59pm. Late submissions without special con- sideration will be subject to the penalties specified in the first lecture (5% per day or part thereof; 100% after 10 days.)
• Submit your answers as a single document (preferably a pdf or doc file) to Canvas. Your work must be typed text (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
• Your assignment will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as (but not limited to) parts of the actual algorithms, (counter)examples, proofs, writing, or code.
Guidelines for NP-hardness proofs
• Each NP-hardness proof should use a Karp reduction from an NP-complete problem covered in lectures/tutorials (see below for a list).
• A Karp reduction from problem X to problem Y is an algorithm that takes as input an instance I of X and produces an instance I′ of Y such that the answer to I is YES if and only if the answer to I′ is YES.
Level of detail required in this assignment
• Please do not write pseudocode (it’s an unnecessarily precise level of detail for these reductions, and usually harder to follow than prose.)
• Please try to be fairly concise.
• It’s reasonable to write things like these without having to explain precisely how it’s done:
– ‘check that P is a simple path’
– ‘check that all the subsets are disjoint’
• You don’t need to detail data structures etc., unless the choice of structure is important for showing that the time complexity is still polynomial.
• Don’t forget that you’re not trying to solve these problems, you only need to find polynomial time certifiers / polynomial time reductions as appropriate.
Appendix: NP Complete problems
This is just a short list of some well known NP Complete problems that have been mentioned in lec- tures/tutorials, in case you need inspiration for problems to reduce from for your NP Completeness proofs.
• 3-SAT: Given a formula in Conjunctive Normal Form, where each clause has exactly 3 literals, is there a satisfying truth assignment?
2
• 3-Colour: Given a graph, is it possible to colour the vertices using at most 3 colours, such that no pair of adjacent vertices have the same colour?
• Hamiltonian-Cycle: Given a graph, is there a simple cycle which visits every vertex of the graph?
• Independent-Set: Given a graph G = (V,E) and an integer k, is there a subset of vertices S ⊆ V
such that |S| ≥ k and for each edge at most one of its endpoints is in S?
• Knapsack: Given a set of items with weights and values, an integer capacity C, and an integer k, is it possible to select a subset of items with total weight no greater than C, but total value at least k?
• Subset-Sum: Given a set of integers S and an integer k, is there a subset of S which sums to k?
• Partition: Given a set of integers S, is there a partition of S into two subsets S1 and S2 such that
the sum of integers in S1 equals the sum of integers in S2?
• Set-Cover: Given a set of elements U, a collection of subsets of it, and an integer k, does there exist
a collection of k of these subsets whose union covers U?
• Traveling-Salesman-Problem: Given a set of n cities and a pairwise distance function d(u,v), is
there a tour of length ≤ D?
• Vertex-Cover: Given a graph G = (V,E) and integer k, is there a subset of vertices S ⊆ V such
that |S| ≤ k and for each edge at least one of its endpoints is in S?
3