Algorithms 3027/3927 Assignment 4
Task 1: Among Us [50 marks]
You are playing your favourite social deduction game, Among Us, and it has nally 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 f1; 2; : : : ; ng could be imposters if
I contains exactly k players
For any clear (p; q) in C, if p is not in I then q is not in I
For any accusation (p; q) in A, if p is not in I, then q is in I
The sus of a subset I of the players is the sum of the sus of each player, ie
Pi2I 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.
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 nd 2 imposters. Formally:
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:
fbatman; shrekg could be imposters, total sus: 111
fbatman; catg could not be imposters because mini is accusing shrek, and because shrek is clearing
fbatman;minig could not be imposters because shrek is clearing batman, and because cat is clearing
mini, and because shrek is accusing cat
fshrek; catg could not be imposters because batman is clearing shrek
fshrek;minig could not be imposters because batman is clearing shrek, and because cat is clearing
mini, and because batman is accusing cat
fcat;minig 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 certicate and a verier.
(b) Give a brief justication of the correctness of the verier.
(c) Give a brief justication that the verier 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
(c) Prove that your reduction is polynomial-time.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx