Design and Analysis of Algorithms  Homework 5

CS 535 Design and Analysis of Algorithms 
Homework 5

Problem 1 Let G = (V, E, c, s, t) be a flow network with integer capacities, and f be a feasible
flow with integer values. Suppose there is a edge e with head s and such that f(e) = 1. Describe
an O(|V |+ |E|) algorithm (An English explanation may be enough) that produces another feasible
flow f
′ with |f| ≤ |f
′
| and such that f
′
(e) = 0.
Be precise though: if you use an algorithm from the texbook, explain which graph is the input
of the algorithm. Justify the overall running time and correctness.
Problem 2 A multiple source-sink network is a tuple G = (V, E, c, S, T), where V is a set of
vertices, E is a set of directed edges (parallel edges are allowed), S ⊂ V is the set of sources, and
T ⊂ V is the set of sinks, c is a capacity function: c : E → Z+. Also, S ∩ T = ∅. That is, sources
are distinct from sinks.
A function f : E → R+ is called a flow if the following three conditions are satisfied:
1. conservation of flow at interior vertices: for all vertices u not in S ∪ T, X
e∈δ−(u)
f(e) = X
e∈δ+(u)
f(e) ;
2. capacity constraints: f ≤ c pointwise: i.e. for all e ∈ E,
f(e) ≤ c(e) .
Assume that non-negative quantities ps, for s ∈ S, and qt
, for t ∈ T, are given. The goal of this
problem is to determine if a valid flow exists such that for all s ∈ S:
X
e∈δ+(s)
f(e) −
X
e∈δ−(s)
f(e) = ps
and such that for all t ∈ T:
X
e∈δ−(t)
f(e) −
X
e∈δ+(t)
f(e) = qt
.
Use Network Flows to give a polynomial-time algorithm for this decision problem (the answer
is YES or NO). Hint: read chapter 26.1 of the textbook.
Problem 3 The edge connectivity of an undirected multigraph is the minimum number k of edges
that must be removed to disconnect the graph. For example, the edge connectivity of a tree is
1, and the edge connectivity of a cyclic chain of vertices is 2. Show how to determine the edge
connectivity of an undirected multigraph G = (V, E) by running a maximum-flow algorithm on at
most |V | flow networks, each having O(|V |) vertices and O(|E|) edges.
Argue correctness.
1