AlgorithmDesign Assignment4 s12024

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“AcademicDishonestyandPlagiarism”policies.

Asafirststepgotothelastpageandreadthesection: “Adviceonhowtodotheassignment”.

Important: ThisassignmentisforallCOMP3x27students. COMP3027studentsshoulddoProblems1and

2whileCOMP3927studentsshoulddoProblems1,2,and3.

Background. Wow! Go-karting sure was fun. However, you had an unfortunate encounter with

Truck-kunandfindyourselfisekai-edintoDune,ofallplaces. Luckily,you’reatleastamid-ranking

official in the Arrakis administration so your new life isn’t too bad. You get to work in plotting to

deposeyourrivalsinpower.

Problem 1. (40pointsforCOMP3027,30pointsforCOMP3927)

Oneofyourrivalsisanofficialmanagingspicemining. InthisversionofArrakis,spiceismined

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

andthey’llgoberserk,destroyingeverythingonArrakis.

Formally,theproblemisthatthere’sanundirectednetwork (V,E) of n nodes,whereeachundi-

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 ∑ w(u,v) is maximised, with the further condition that the number of S-T

u∈S,v∈T

edges (u,v) ∈ E (where u ∈ S,v ∈ T)iseven.

a) Definethedecisionversionofthisproblem.

b) ProvethatthisdecisionproblemisinNP.

c) ProvethatthisdecisionproblemisNP-Complete.

d) ConcludethattheoriginalsearchproblemisNP-Hard.

Problem 2. (60pointsforCOMP3027,COMP3927)

You’vesuccessfullyremovedyouroppositionandarenowthepipelinemanagerforArrakis. You

thinkthereisanewopportunityforefficiencybycombiningthespicedistributionnetworkandthe

waterdistributionnetwork. Ofcourse,youcan’ttransportbothwaterandspiceinthesamepipeline,

sothismightlimityourefficiencygains. Howmuchmoreefficiencycanwegainfromthischange?

Formally, we have a directed network (V,E) on n nodes, including two sources and one sink,

s 1,s 2,t ∈V. Eachdirectededge(u,v)hasacapacityc(u,v) ∈Z ≥0,andwehavetwoflows f,g :V×

V → Z ≥0. We have the usual flow conservation and capacity constraints for f and g individually,

withtheadditionalconstraintthatforeachedge,atleastoneof f(u,v)andg(u,v)is0. Furthermore,

for all vertices v ∈ V\{s ,s }, g(s ,v) = f(s ,v) = 0, i.e. s only supplies f-flow and s only

1 2 1 2 1 2

supplies g-flow. Finally, we want to maximise the combined flow into t, i.e. ∑ (f(v,t)+g(v,t))

v∈V

ismaximised.

a) Definethedecisionversionofthisproblem.

b) ProvethatthisdecisionproblemisinNP.

c) ProvethatthisdecisionproblemisNP-Complete. Hint: 3-SATmightgiveagoodreductionhere.

d) ConcludethattheoriginalsearchproblemisNP-Hard.

1

AlgorithmDesign Assignment4 s12024

Problem 3. (10points)(COMP3927only)

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

anyonewhocouldpossiblytakeover.) Comeupwithanalgorithmthatsavesyousomeeffort.

Formally, again we have a directed network (V,E) on n nodes, including two sources and one

sink, s 1,s 2,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. Weagainhavetheusualflowconservationandcapacityconstraintsfor f

and g individually, with the additional constraint that for each edge, at least one of f(u,v), g(u,v)

is0. Furthermore,forallvertices v ∈V\{s ,s }, g(s ,v) = f(s ,v) =0,i.e. s onlysupplies f-flow

1 2 1 2 1

and s onlysupplies g-flow. Maximisethecombinedflowinto t,i.e. ∑ (f(v,t)+g(v,t)).

2 v∈V

a) Developanalgorithmthatisa1/2-approximationtothisoptimisationproblem.

Hint: Don’toverthinkthis.

b) Proveitscorrectness.

c) Analyseitsrunningtime.

2

AlgorithmDesign Assignment4 s12024

Advice on how to do the assignment

• Assignments should be typed and submitted as pdf (no pdf containing text as images, no

handwriting).

• Start by typing your student ID at the top of the first page of your submission. Do not type

yourname.

• Submitonlyyouranswerstothequestions. Donotcopythequestions.

• When asked to give a plain English description, describe your algorithm as you would to a

friendoverthephone,suchthatyoucompletelyandunambiguouslydescribeyouralgorithm,

including all the important (i.e., non-trivial) details. It often helps to give a very short (1-2

sentence) description of the overall idea, then to describe each step in detail. At the end you

canalsoincludepseudocode,butthisisoptional.

• Inparticular,whendesigninganalgorithmordatastructure,itmighthelpyou(andus)ifyou

briefly describe your general idea, and after that you might want to develop and elaborate on

details. Ifwedon’tsee/understandyourgeneralidea,wecannotgiveyoumarksforit.

• Be careful with giving multiple or alternative answers. If you give multiple answers, then we

will give you marks only for "your worst answer", as this indicates how well you understood

thequestion.

• Some of the questions are very easy (with the help of the slides or book). You can use the

material presented in the lecture or book without proving it. You do not need to write more

thannecessary(seecommentabove).

• Whengivinganswerstoquestions,alwaysprove/explain/motivateyouranswers.

• When giving an algorithm as an answer, the algorithm does not have to be given as (pseudo-

)code.

• If you do give (pseudo-)code, then you still have to explain your code and your ideas in plain

English.

• Unless otherwise stated, we always ask about worst-case analysis, worst case running times,

etc.

• As done in the lecture, and as it is typical for an algorithms course, we are interested in the

mostefficientalgorithmsanddatastructures.

• Ifyouusefurtherresources(books,scientificpapers,theinternet,...) toformulateyouranswers,

then add references to your sources and explain it in your own words. Only citing a source

doesn’tshowyourunderstandingandwillthusgetyouveryfew(ifany)marks. Copyingfrom

anysourcewithoutreferenceisconsideredplagiarism.

3