# 1.( Node-capacitated networks 2-page limit – your solutions should fit on two sides of 1 page)

1.( Node-capacitated networks 2-page limit – your solutions should fit on two sides of 1 page)

A zombie infestation on earth is threatening the population of all our cities. The virus originated mysteriously at a site located at s ∈ V and a medical facility at t ∈ V is working on a cure at the moment. You have to stop the virus from spreading across a network of cities, represented by a directed graph G = (V,E), between s and t because the facility at t is your only chance at saving the planet. The cost of cutting off all possible transportation out of a single city v ∈ V, which can be thought of as a node capacity of that city, is cv ≥ 0. You can define a flow f in this network, given that the flow though a node v is defined as fin(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and also the following constraints: fin(v) ≤ cv for all nodes. You have to find an s-t maximum flow through this network, cutting which will solve your problem in polynomial time. Define an s-t cut for such a network, and show that the analogue of the Max-Flow Min-Cut Theorem holds true.

(a) Give an algorithm for maximum flows in node-capacitated networks of this kind. Pay close attention to the argument of correctness of your algorithm.
[Hint: One way to give an algorithm for this problem is to run Ford-Fulkerson on a modified version (say G′ = (V ′, E′)) of the original graph G, in which each vertex in V corresponds to two vertices (call them vin and vout) in V ′. The graph G′ should have an edge e′ for every edge e in E along with some additional edges.]

(b) Define an analogue of an s-t cut in a node-capacitated network, and define the “capacity” of your object.

(c) Explain why the max-flow min-cut theorem holds for your analogue.
If it is easier, you may want to prove correctness of your algorithm at the same time as you prove your max-flow/min-cut theorem.

Solution guidelines For problems that require you to provide an algorithm, you must give the following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

1.

Maxflow:

Main idea: find valid flow paths until there is none left, and add them up.

Proof:

• Take a maximum flow f ⋆ and “subtract” our flow f. It is a valid flow of positive total flow. By the flow decomposition, it can be decomposed into flow paths and circulations. flow paths must have been found by Contradiction of Ford-Fulkerson.
• We don’t need to maintain the amount of flow on each edge but work with capacity values directly
• If f amount of flow goes through u → v, then: – Decrease c(u → v) by f – Increase c(v → u) by f
• Set ftotal = 0
• Repeat until there is no path from s to t: – Run DFS from s to find a flow path to t – Let f be the minimum capacity value on the path – Add f to ftotal – For each edge u → v on the path: ◮ Decrease c(u → v) by f Increase c(v → u) by f

Analysis:

• Assumption: capacities are integer-valued
• Finding a flow path takes Θ(n + m) time
• We send at least 1 unit of flow through the path
• If the max-flow is f ⋆ , the time complexity is O((n + m)f ⋆ ) – “Bad” in that it depends on the output of the algorithm

2.

s-t cut value is an upper bound on v(f). Given a network N, the max-flow problem is to find a feasible flow with the maximum possible value.

max f f easible v(f) ≤ min (A,B) c(A, B). We will show that equality is in fact attained by the max-flow and min-cut values.

3.

We construct a new graph H where for every vertex v in G, we have two vertices vi and vo. There is an edge from vi to vo of capacity cv. If the graph G has an edge (u, v), then we add an edge (uo, vi) in H of infinite capacity. Now notice that any flow in H entering vi must go through the edge (vi , vo) and so the total amount of flow entering vi (or leaving vo) cannot exceed cv. Now it is easy to check that a flow of value v in G results in a flow of the same value in H and vice-versa

Pages (550 words)
Approximate price: -

Help Me Write My Essay - Reasons:

Best Online Essay Writing Service

We strive to give our customers the best online essay writing experience. We Make sure essays are submitted on time and all the instructions are followed.

Our Writers are Experienced and Professional

Our essay writing service is founded on professional writers who are on stand by to help you any time.

Free Revision Fo all Essays

Sometimes you may require our writers to add on a point to make your essay as customised as possible, we will give you unlimited times to do this. And we will do it for free.

Timely Essay(s)

We understand the frustrations that comes with late essays and our writers are extra careful to not violate this term. Our support team is always engauging our writers to help you have your essay ahead of time.

Customised Essays &100% Confidential

Our Online writing Service has zero torelance for plagiarised papers. We have plagiarism checking tool that generate plagiarism reports just to make sure you are satisfied.

Try it now!

## Calculate the price of your order

Total price:
\$0.00

How it works?

Fill in the order form and provide all details of your assignment.

Proceed with the payment

Choose the payment system that suits you most.

HOW OUR ONLINE ESSAY WRITING SERVICE WORKS

Let us write that nagging essay.

By clicking on the "PLACE ORDER" button, tell us your requires. Be precise for an accurate customised essay. You may also upload any reading materials where applicable.

Pick A & Writer

Our ordering form will provide you with a list of writers and their feedbacks. At step 2, its time select a writer. Our online agents are on stand by to help you just in case.

Editing (OUR PART)

At this stage, our editor will go through your essay and make sure your writer did meet all the instructions.