Algorithms 3027/3927 Assignment 4 The University of Sydney 2021 Semester 1 School of Computer Science
3027 students: Do Tasks 1 and 2. 3927 students: Do Tasks 1 and 3.
Task 1: Among Us [50 marks]
You are playing your favourite social deduction game, Among Us, and it has finally come time to accuse the imposters. You have kept track of which players have been cleared and by who, which players have been accused and by who, and how sus each player is in general. You trust that any crewmate would only clear a crewmate, and any crewmate would only accuse an imposter, but imposters cannot be trusted at all. You must determine a group of players that could be imposters such that the sum of their sus is at least some threshold.
Formally, you are given
• n: the number of players
• k: the number of imposters
• t: sus threshold
• s1, s2, …sn: a number representing the sus of each player
• C: a list of ordered pairs (p,q) indicating player p has cleared player q • A: a list of ordered pairs (p, q) indicating player p has accused player q
A subset I of the players {1, 2, . . . , n} could be imposters if
• I contains exactly k players
• Foranyclear(p,q)inC,ifpisnotinIthenqisnotinI
• Foranyaccusation(p,q)inA,ifpisnotinI,thenqisinI
The sus of a subset I of the players is the sum of the sus of each player, ie i∈I si. The Among Us decision problem is to determine if there exists a subset of players that could be imposters with sus at least the threshold t.
Sus: 69
Sus: 42
Sus: 0
Sus: 100
Figure 1: Example: Top = batman, right = cat, bottom = mini, left = shrek.
In Figure 1, each of the 4 players has sus, red double-arrows indicate accusations, blue single-arrows indicate clears, and we are trying to find 2 imposters. Formally:
1
•n=4
•k=2
• t = 105
• sbatman = 69, scat = 0, smini = 100, sshrek = 42
• C = [(shrek, batman), (cat, mini), (batman, shrek)] • A=[(shrek,cat),(mini,shrek),(batman,cat)]
There are 6 subsets of size 2:
• {batman, shrek} could be imposters, total sus: 111
• {batman, cat} could not be imposters because mini is accusing shrek, and because shrek is clearing batman
• {batman, mini} could not be imposters because shrek is clearing batman, and because cat is clearing mini, and because shrek is accusing cat
• {shrek, cat} could not be imposters because batman is clearing shrek
• {shrek, mini} could not be imposters because batman is clearing shrek, and because cat is clearing
mini, and because batman is accusing cat
• {cat, mini} could be imposters, total sus: 100
Since there are two subsets that could be imposters with total sus 100 and 111, the answer to the Among Us decision problem is YES.
Task 1a: Prove decision problem is in NP
(a) Describe a certificate and a verifier.
(b) Give a brief justification of the correctness of the verifier.
(c) Give a brief justification that the verifier runs in polynomial time.
Task 1b: Prove decision problem is NP-hard
Your task is to give a polynomial-time Karp reduction from an NP-complete problem (see Appendix) to the Among Us decision problem
(a) Describe how you transform an instance of the NP-complete problem into an instance of the Among Us decision problem.
(b) Prove the correctness of your reduction, i.e. the instance of the NP-complete problem is a YES- instance if and only if the instance of the Among Us decision problem created by your reduction is a YES-instance.
(c) Prove that your reduction is polynomial-time.
Task 2 (3027 only): Odd Wurst K ̈ase [50 marks]
After successfully handling Taco Mania at Cinco de Mayo, you and your genius friend head to your favorite German restaurant Wurst K ̈ase Essen Haus. There are n items on the menu; the cost of item i is ci, a positive integer. The good news is that they accept the NSW dining vouchers, each worth V , and you still have one unused voucher. Being a thrifty fellow, you would like to use up the entirety of the voucher. The bad news is that the restaurant has an odd requirement: you can only purchase an odd number of items. Thus, you want to determine if there is an odd number of items you can order whose total cost is exactly V .
Formally, you are given:
2
• n: the number of menu items
• positive integers c1, . . . , cn: the cost of each item • a positive integer V : the value of the voucher
The Odd Wurst K ̈ase decision problem is to decide if there exists a set of items X with |X| odd and i∈X ci = V .
For example, suppose you have four items on the menu: weisswurst (cost = 13), bratwurst (cost = 13), butterk ̈ase (cost = 14) and rauchk ̈ase (cost = 12) and your voucher value V = 25, then the answer is NO even though weisswurst and rauchk ̈ase has a combined cost of 25. For the same items and costs, but the voucher value is now V = 40, the answer is YES: weisswurst, bratwurst and butterk ̈ase is a subset of odd cardinality and their total cost is 40.
Task 2a: Prove decision problem is in NP
(a) Describe a certificate and a verifier.
(b) Give a brief justification of the correctness of the verifier.
(c) Give a brief justification that the verifier runs in polynomial time.
Task 2b: Prove decision problem is NP-hard
Your task is to give a polynomial-time Karp reduction from the Positive Subset Sum problem: given a set S of positive integers and a target value t, determine if there exists a subset S′ whose sum equals t. (Note that there may be repetitions in S and S′, and the number of copies of a number in S′ needs to be at most the number of copies in S.)
(a) Describe how you transform an instance of the Positive Subset Sum problem into an instance of the Odd Wurst K ̈ase decision problem.
(b) Prove the correctness of your reduction, i.e. the instance of the Positive Subset Sum problem is a YES-instance if and only if the instance of the Odd Wurst-K ̈ase decision problem created by your reduction is a YES-instance.
(c) Prove that your reduction is polynomial-time.
Task 3 (3927 only): Balanced Wurst K ̈ase [50 marks]
After successfully handling Taco Mania at Cinco de Mayo, you and your genius friend head to your favorite German restaurant Wurst K ̈ase Essen Haus. As the name indicates, they only have two kinds of items on their menu: sausage and cheese. The good news is that they accept the NSW dining vouchers, each worth V , and you still have one unused voucher. Being a thrifty fellow, you would like to use up the entirety of the voucher. In the interests of maintaining a balanced diet, you want to order equal numbers of cheese items and sausage items. Thus, you want to determine if there is a subset of items consisting of equal numbers of sausage items and cheese items whose total cost is exactly V .
Formally, you are given:
• n: the number of cheese items
• positive integers c1, . . . , cn: the costs of the cheese items
• m: the number of sausage items
• positive integers s1, . . . , sm: the costs of the sausage items • positive integer V : voucher value
The Balanced Wurst K ̈ase decision problem is to determine if there is a subset Xc of cheese items and subset Xs of sausage items with |Xc| = |Xs| such that their combined cost i∈Xc ci + j∈Xs sj = V .
3
Task 3a: Prove decision problem is in NP
(a) Describe a certificate and a verifier.
(b) Give a brief justification of the correctness of the verifier.
(c) Give a brief justification that the verifier runs in polynomial time.
Task 3b: Prove decision problem is NP-hard
Your task is to give a polynomial-time Karp reduction from the Positive Subset Sum problem: given a set S of positive integers and a target value t, determine if there exists a subset S′ whose sum equals t. (Note that there may be repetitions in S and S′, and the number of copies of a number in S′ needs to be at most the number of copies in S.)
(a) Describe how you transform an instance of the Positive Subset Sum problem into an instance of the Balanced Wurst K ̈ase problem.
(b) Prove the correctness of your reduction, i.e. the instance of the Positive Subset Sum problem is a YES-instance if and only if the instance of the Balanced Wurst-K ̈ase decision problem created by your reduction is a YES-instance.
(c) Prove that your reduction is polynomial-time.
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.
Submission details
• Submission deadline is Wednesday 19 May, at 23:59. Late submissions will not be accepted.
• Please do not submit in German.
• Submit your answers as a single document to Gradescope. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
• Your report 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 parts as the precise algorithms, examples, proofs, writing, or code.
• To facilitate anonymous grading, please do not write your name on your submission.
4
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?
• 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?
• Directed Hamiltonian-Cycle: Given a directed graph, is there a simple directed 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?
• Clique: Given a graph G = (V, E) and an integer k, is there a subset of vertices S ⊆ V such that
|S| ≥ k and for every u,v ∈ S, we have (u,v) ∈ E, i.e. S is a complete subgraph?
• 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?
• Positive Subset-Sum: Given a set of positive integers S and a positive integer k, is there a subset
of S which sums to k?1
• 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?
1This problem is also NP-complete, as the reduction from vertex cover only uses positive integers. 5