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