CS577-Homework 7 Solved

1.    Suppose we are given an integer k, together with a flow network N = (V,E,c) in which every edge has capacity 1. Design an algorithm to identify k edges in N such that after deleting those k edges, the maximum value of a flow in the remaining network is as small as possible. Your algorithm should run in time polynomial in n and m.

2.    Given a flow network N = (V,E,c) with source s and sink t, we say that a node v ∈ V is upstream if, for all minimum s-t cuts (S,T) of G, v ∈ S. In other words, v lies on the s-side of every minimum s-t cut. Analogously, we say that v is downstream if v ∈ T for every minimum s-t cut (S,T) of G. We call v central if it is neither upstream nor downstream.

Design an algorithm that takes N and a flow f of maximum value in N, and classifies each of the nodes of N as being upstream, downstream, or central. Your algorithm should run in linear time.

Regular problems
3.    A given network G with integer capacities may have more than one minimum s-t cut. Define the densest minimum s-t cut to be any minimum s-t cut (S,T) of G with the greatest number of edges crossing from S to T.

(a)    Suppose we have access to a black box called MaxFlow. MaxFlow takes as input a network N and outputs a flow of maximum value for N. Design an algorithm to find a densest minimum s-t cut of G using at most one call to MaxFlow. Outside of MaxFlow, your algorithm should run in linear time. You may assume that standard arithmetic operations can be done in constant time.

(b)   Design an algorithm to determine whether G contains a unique densest minimum s-t cut. Once again, you can make at most one call to MaxFlow. Outside of MaxFlow, your algorithm should run in linear time. You may assume that standard arithmetic operations can be done in constant time.

4.    Consider a network with integer capacities. An edge is called upper-binding if increasing its capacity by one unit increases the maximum flow value in the network. An edge is called lower-binding if reducing its capacity by one unit decreases the maximum flow value in the network.

1

(a)    For the network G below determine a maximum flow f∗, the residual network Gf∗, and a minimum cut. Also identify all of the upper-binding edges and all of the lower-binding edges.

 

(b)   Develop an algorithm for finding all the upper-binding edges in a network G when given G and a maximum flow f∗ in G. Your algorithm should run in linear time.

(c)    Develop an algorithm for finding all the lower-binding edges in a network G when given G and an integer maximum flow f∗ in G. Your algorithm should run in time polynomial in n and m. Can you make it run in linear time?

5.    A given network can have many minimum st-cuts.

(a)    Determine precisely how large the number of minimum st-cuts in a graph can be as a function of n.

(b)   Show that if (S1,T1) and (S2,T2) are both minimum st-cuts in a given network, then so is (S1∪ S2,T1∩ T2). How does this generalize to more than 2 st-cuts?

(c)    Design an algorithm that, given a network, generates a collection of minimum st-cuts

(S1,T1),(S2,T2),... such that every minimum cut of the network can be written as

(∪i∈ISi,∩i∈ITi)

for some subset I of indices. Your algorithm should run in time polynomial in n and m.

Challenge problem
6. Problem J from the 2007 ACM-ICPC World Finals (see next page). Your algorithm should

.

run in time polynomial in n = R + T.

Programming problem
7. SPOJ problem Potholers (problem code POTHOLE).