COMP3027 & COMP3927 Algorithm Design Assignment 4

This assignment is due on May 15 and should be submitted on Gradescope.   All submitted work must be done individually without consulting someone else’s solutions 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. Wow!  Go-karting sure was fun.  However, you had an unfortunate encounter with Truck-kun and find yourself isekai-ed into Dune, of all places. Luckily, you’re at least a mid-ranking official in the Arrakis administration so your new life isn’t too bad.  You get to work in plotting to depose your rivals in power.

Problem 1. (40 points for COMP3027, 30 points for COMP3927)

One of your rivals is an official managing spice mining. In this version of Arrakis, spice is mined from deposits and transported in pipelines. To get rid of your rival and take over the area under their control, you’ve obtained control of a space laser and want to find out how much damage we can possibly do to their pipelines.  However, the controls of the laser are a bit hard to use, and you can only program it to draw a loop around nodes in the transport network. Furthermore, the laser manual warns you that if you blow up an odd number of pipelines, this will anger the sandworms and they’ll go berserk, destroying everything on Arrakis.

Formally, the problem is that there’s an undirected network (V, E) of n nodes, where each undi- rected edge has an integer weight w (u, v) = w (v, u) > 0 (and if there is no edge between u, v then w (u, v) = 0).  We want to choose a cut such that the nodes are divided into sets S, T, where the capacity of the cut Σu ∈S,v ∈Tw(u, v) is maximised, with the further condition that the number of S-T edges (u, v) ∈ E (where u ∈ S, v ∈ T) is even.

a)  Define the decision version of this problem.

b)  Prove that this decision problem is in NP.

c)  Prove that this decision problem is NP-Complete.

d) Conclude that the original search problem is NP-Hard.

Problem 2. (60 points for COMP3027, COMP3927)

You’ve successfully removed your opposition and are now the pipeline manager for Arrakis. You think there is a new opportunity for efficiency by combining the spice distribution network and the water distribution network. Of course, you can’t transport both water and spice in the same pipeline, so this might limit your efficiency gains. How much more efficiency can we gain from this change?

Formally, we have a directed network (V, E) on n nodes, including two sources and one sink, s1, s2, t ∈ V. Each directed edge (u, v) has a capacity c (u, v) ∈ Z ≥0, and we have two flows f , g : V × V → Z ≥0. We have the usual flow conservation and capacity constraints for f  and g individually, with the additional constraint that for each edge, at least one off(u, v) and g(u, v) is 0. Furthermore, for all vertices v  ∈ V \ {s1, s2}, g(s1, v)  = f(s2, v)  = 0, i.e.  s1  only supplies f-flow and s2  only supplies g-flow. Finally, we want to maximise the combined flow into t, i.e. Σv ∈V(f(v, t) + g(v, t)) is maximised.

a)  Define the decision version of this problem.

b)  Prove that this decision problem is in NP.

c)  Prove that this decision problem is NP-Complete. Hint: 3-SAT might give a good reduction here. d) Conclude that the original search problem is NP-Hard.

Problem 3. (10 points) (COMP3927 only)

NP-hardness can’t stop you!  If only half the maximum possible flow gets through at any time, that’s good enough for you.  (You don’t need to be the best at your job, you only need to remove anyone who could possibly take over.) Come up with an algorithm that saves you some effort.

Formally, again we have a directed network (V, E) on n nodes, including two sources and one sink, s1, s2, t ∈ V. Each directed edge (u, v) still has a capacity c (u, v) ∈ Z ≥0, and we still have two flows f , g : V × V → Z ≥0. We again have the usual flow conservation and capacity constraints for f and g individually, with the additional constraint that for each edge, at least one off(u, v), g(u, v) is 0. Furthermore, for all vertices v ∈ V \ {s1, s2}, g(s1, v) = f(s2, v) = 0, i.e. s1  only supplies f-flow and s2 only supplies g-flow. Maximise the combined flow into t, i.e. Σv ∈V(f(v, t) + g(v, t)).

a)  Develop an algorithm that is a 1/2-approximation to this optimisation problem.

Hint: Don’t overthink this.

b)  Prove its correctness.

c)  Analyse its running time.