This assignment is due on May 17 and should be submitted on Gradescope. All submitted work must be done individually without consulting someone else’s solu- tions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.

As a first step go to the last page and read the section:  “Advice on how to do the assignment” .

Important: This assignment is for all COMP3x27 students.  COMP3027 students should do Problems 1 and 2 while COMP3927 students should do Problems 1, 2, and 3.

Background. Space is big.  Mostly empty, quite cold, but crucially very, very big. Which is a bit of a problem for you, since, as a space warlord with limited resources, it’s a painto keep track of your empire of, wait, oh many? Wow, n planets already. Good on you!

You’re a very organised space warlord though, and have established space routes between each of these planets, taking into account the risk of space dingos, the re- fuelling capabilities, and the areas where you just don’t want to fly through (the comets are not worth it and the view is truly lame). So you have a nice holomap of these n planets of yours, along with m directional wormlinks that connect them through  some  elaborate,  yet incredibly functional network  of space routes.   A holomap, or, as your annoying lieutenant calls it, “a directed graph G  =  (V, E)

with n vertices and m edges.”

Problem 1. (30 points)

Anyways, space is big, troops are not cheap and you would like to figure out if instead of having a small army on every planet, you could not just have a few space soldiers in a small number of selected planets (space bases!), able to easily keep peace and order in your space warlord empire: that is, find the minimum number b of your planets on which to establish a base, such that every planet is reachable from a base in one wormlink hop. Formally: “find the minimum integer b such that there exists B 己 V of size |B|  = b satisfying:  for every v ∈ V / B, there is a base u ∈ B such that (u, v) ∈ E.”

That’s really a mouthful.  Unfortunately, since you just threw your lieutenant into space for being a tad too annoying, you have to do it yourself. . . his last words before being sent towards a space crocodile? “This is hopeless, it’s NP-aaaarg.”

Your task is to show he was right.

a) Describe a polynomial-time reduction from the above problem to the decision problem: “given an integer b, decide whether there exists B 己 V of size |B| = b satisfying: for every v ∈ V / B, there is a base u ∈ B such that (u, v) ∈ E.”

b) Briefly argue the correctness of this reduction and analyse its running time. c) Show this decision problem is in NP.

d) Show this decision problem is NP-Complete.

e) Conclude the original problem is NP-Hard. Is it NP-Complete?

Problem 2. (70 points for COMP3027 (40 points for COMP3927)) This was a bum- mer, especially since that lieutenant could have been helpful for this nextstep. Oh well. Along with the rest of your space advisors, you have identified k space quad- rants Q1, . . . , Qk partitioning your space empire in strategic ways, and have decided to establish one space base in each of these space quadrants, to secure your space empire. (You really love space, don’t you?)

Quadrant i contains |Qi| of your n planets, and planet ℓ ∈ Qi  has “total space distance” δℓ  ≥ 0 to the rest of the planets in disjoint quadrant Qi, as well a base- building cost cℓ. Everything is a (non-negative) integer. You’re a rich space warlord, but not so rich that you can simply build all of them, unfortunately, so you can only spend a total of D space dollars to establish your k bases. You’d like to do this while getting the most strategic value possible! That is, given n as well as all the Qi’s, δℓ’s, cℓ’s,and D (where cℓ ≤ D for every ℓ), your goal is to identify one planet ℓi  ∈ Qi for each quadrant Qi, such that 1 cℓi   ≤ D while minimising 1 δℓi .

a) What is (a reasonable upper bound on) the size of the input to the problem, represented in bits, as a function of n, k, D, Δ := max1≤i≤k maxℓ∈|Qi|δℓ?

(You can upper bound the number of ways to partition a set of size n into k sets by the (loose, but OK) bound kn .)

b) Define the decision version of the above search problem.

c) Prove that this decision version is in NP.

d) Prove that this decision version is NP-Complete.

e) Conclude that the search problem is NP-Hard. (But there’s nobody to send to the space crocodiles anymore!)

This is annoying. And yet, you’re not going to let NP-Hardness get in the way of your space bases!  Let’s design an algorithm to solve our problem and place our k bases. As long as it runs in time polynomial in n and D, you’ll be happy... of course, the faster running time, the better.

f)  Describe the algorithm in plain English.

g) Prove its correctness.

h) Establish its time complexity.

Problem 3. (30 points) (COMP3927 only) You got the planets.  You got the bases. You got the space empire! But now you’re a little worried. You’ve realised that your whole directional wormlink system (which was quite cheap, in hindsight) might actually fail catastrophically and destroy your space ships if used while 3 or more of the wormlinks are crossing. (Don’t cross the streams, they said!)

Which could happen if any 3 of your n connected planets were to align while your wormlink system is used.  So you need a way to quickly check, on any day, if there is an alignment of 3 of your planets.  For this, you can assume each planet is only specified by 2 coordinates, so that planet i corresponds to a point (xi, yi). You want an algorithm to solve this problem running in time at most quadratic,i.e., O(n2 ).