Computer Science

Thebuyer-fulfilling problemis described as follows. Suppose you are an auctioneer in an auction witha setBofnbuyers and a setCofmobjects. Each object can go to only one buyer, and each buyerb?Bhas a subsetCb?Cof objects that must go tobin order to “fulfill"b. The decision problem wewant to solve is: given an integerk?N, is it possible to distribute the objects to the buyers so that wecan fulfill at leastkbuyers?(a)[6 marks]Devise a simple algorithm that checks if there is a subset ofkbuyers who can befulfilled. Compute its time complexity in terms ofn,m,andk.(b)[14 marks]Recall the3-D Matching Problem: LetX,Y ,andZbe finite, disjoint sets, and letTbe a subset ofX×Y×Z. That is,Tconsists of triples(x,y,z) such thatx?X,y?Y ,andz?Z.NowM?Tis said to be a3-dimensional matching if the following holds: for any two distincttriples(x1,y1,z1),(x2,y2,z2)?M, we havex1,x2,y1,y2andz1,z2. The decision problem of3-D Matching Problem then is: “given a setTand an integerk, does there exist a3-dimensionalmatchingM?Twith|M|=k?” This problem is NP-Complete (you do not need to prove this).Show that the buyer-fulfilling problem isNP-Complete by reducing 3-D Matching to it.2.[20 marks]An epidemiologist is studying the transmission of the COVID-19 virus in the Greater Toronto Area(GTA). The community is represented by a graphG= (V ,E) where vertices represent people in theGTA and edges represent two individuals who have interacted with each other. To study how thevirus may have spread, the epidemiologist wants to know if people in the GTA can be divided into atmostkgroupsG1,...,Gkwhere:•Everyone inVis in some group, and no person is in two different groups.•Everyone in groupGihas interacted with each other.(a)[5 marks]Show that the above problem given the graphGand integerkas inputs is inNP.(b)[5 marks]Show that the above problem whenk=2 is decidable in polynomial time.(c)[10 marks]Show that the above problem whenk=3 isNP-Complete.3.[20 marks]A propositional formulafis in3-Positive Conjunctive Normal Form (3-PCNF)iffit is writtenin 3-CNF with no negative literal, i.e., all the variables in the formula are positive. For example,f= (x1?x3?x4)?(x2?x3?x2)?(x1?x2?x3) is in 3-PCNF. Obviouslyfis satisfiable by setting allthe variables toTrue.We are interested in a different question: howfewvariables must be set toTruein order to satisfyf?For example, the previous formula can be satisfied by setting just one variable toTrue, namely,x3.This is an NP-Hard problem (you do not need to prove this).(a)[8 marks]Define the corresponding Decision Problem for this optimization problem, and showthat this optimization problem is polynomial-time self-reducible 



 Read less