Homework 4 Node-capacitated networks

You are strongly encouraged, but not required, to format your problem solutions in LATEX. Template HW files and other LATEXresources are posted on the course webpage. LATEXis a free, open-source
scientific document preparation system. Most technical publications in CS are prepared using this tool.
You might want to acquire a LATEX manual or find a good online source for LATEX documentation.

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.
You may use algorithms from class as subroutines. You may also use any facts that we proved in class.
You should be as clear and concise as possible in your write-up of solutions. Understandability of
your answer is as desirable as correctness, because communication of technical material is an important
skill. A simple, direct analysis is worth more points than a convoluted one, both because it is simpler
and less prone to error and because it is easier to read and understand. Points might be subtracted
for illegible handwriting and for solutions that are too long. Incorrect solutions will get from 0 to 30%
of the grade, depending on how far they are from a working solution. Correct solutions with possibly
minor flaws will get 70 to 100%, depending on the flaws and clarity of the write up.
Assigned Problems
Exercises (Do not hand in) Chapter 4: 3,4 and 6, Chapter 5:1-3.
Following are the problems to be handed in, 25 points each. Maximum score for this
homework is 100 points. We will take your best four attempted problems.
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.
To organize your answer better break it into parts as follows:
(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 G0 = (V
0
, E0
)) of the original graph G, in which each vertex in V corresponds
to two vertices (call them vin and vout) in V
0
. The graph G0
should have an edge e
0
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.
2
(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.
2. (Cycle cover 2-page limit – your solutions should fit on two sides of 1 page) Your task is to
give an algorithm which finds a cycle cover for a given graph or correctly reports that no cycle
cover exists. An analysis of correctness along with the time and space complexity should also be
included in your solution. You should base your algorithm on a reduction to bipartite matching.
( A cycle cover of a given directed graph G = (V, E) is a set of vertex-disjoint cycles that cover
all the vertices. )
3. (Flow decomposition 2-page limit – your solutions should fit on two sides of 1 page) A flow f
is acyclic if there are no directed cycles in the subgraph of edges with positive flow.
(a) Prove that every flow f has at least one corresponding acyclic flow that has the same value.
(In other words, for every graph, at least one maximum flow is acyclic.)
(b) A path flow is a flow that gives positive values to a simple, directed path from source to
sink. Prove that every acyclic flow is a finite combination of path flows.
(c) Some flows for a directed graph are not a combination of path flows. Give an example of
one.