Introduction to Algorithms Homework 8

CS 577: Introduction to Algorithms Homework 8

Ground Rules
• The homework is worth 5 points (out of a total of 100 points you can accumulate in this course).
• The homework is to be done and submitted in pairs. You can partner with someone from either section.
• The homework is due at the beginning of either lecture on the due date. No extensions to the due date will be
given under any circumstances.
• Turn in your solution to each problem on a separate sheet of paper (or sheets stapled together), with your names
clearly written on top.
Note
• When we ask for an efficient algorithm, it means that the running time for the algorithm should be some polynomial in the size of the problem. For graph problems, the size is |V | + |E| = n + m = O(n2), so we require
an algorithm with running time O(nc) for some constant c.
• When we ask you to analyze an algorithm, provide a proof of correctness as well as an analysis of running time.
Problems
1. (Worth: 2 points. Page limit: 1 sheet; 2 sides)
A given flow network G may have more than one minimum (s, t)-cut. While all minimum (s, t)-cuts will have
the same capacity, they may have different numbers of edges directed from the s side to the t side. Let us define
the best minimum (s, t)-cut to be any minimum cut with the smallest number of edges crossing the cut directed
from the s side to the t side of the cut. (When the minimum cut is unique, by default it is also the best.)
Describe and analyze an efficient algorithm to find the best minimum (s, t)-cut in a given flow network with
integral capacities. (You may use as a subroutine an efficient max-flow algorithm without describing it in detail.)
2. (Worth: 3 points. Page limit: 1 sheet; 2 sides)
(a) For the network G below determine the max s-t flow, f ∗, the residual network Gf ∗ , and a minimum s-t
cut.
(b) An edge in a flow network is called upper-binding if increasing its capacity by one unit increases the
maximum flow in the network. Similarly, an edge in a flow network is called lower-binding if reducing its
capacity by one unit decreases the maximum flow in the network. Identify all of the upper-binding and all
of the lower-binding edges in the above flow network.
(c) Describe and analyze an algorithm for finding all of the upper-binding edges in a flow network G when
given a maximum flow f ∗ in G. Your algorithm should run in time O(n + m), where n is the number of
nodes and m is the number of edges.
1