(Due at the beginning of
class on 11/16/11)
This problem set will be graded out of 50 points. It
will count for 20% of your final grade.
1) Network Flow
a) You are given an undirected
graph. Give a polynomial-time algorithm for finding an orientation of the edges
which minimizes the maximum in-degree of any node. [3]
b) You are given an n x n 0-1
matrix, M. You are allowed to interchange pairs of adjacent rows. You are
allowed to interchange pairs of adjacent columns. Give an algorithm to find the
sequence of interchange operations that maximizes the number of 1s on the
diagonal. (Hint: view M as a bipartite graph and consider matchings)
[4]
c) There are n men, n women and
m marriage brokers in a city. Each broker has some subset of the men and women
as his clients and can arrange marriage between his clients but broker i can arrange no more than bi unions. Give an algorithm to find the largest
number of marriages that can be arranged. [3]
2) Network Flow - II
a) Prove Dilworth’s Theorem
assuming the max-flow min-cut theorem. [4]
b) Implement your own version
of the Dinitz-Edmonds-Karp shortest-path-augmenting
max-flow algorithm. Submit source code. [4]
c) Compare the performance of
your code against the cs2 program (http://www.igsystems.com/cs2/index.html)
on randomly generated flow networks of size
ranging from 10 to 1000 nodes. Plot performance on a graph. [2]
3) Matching
a) Give an efficient algorithm
to find the smallest set of nodes in a bipartite graph such that every edge is
adjacent to some node in the set. [2]
b) There are n men and n women.
Every man-woman pair is characterized by a number that captures the intensity
of their mutual dislike. Give an algorithm to find the minimum intensity number
such that all the men and women can be paired, with the intensity of no pair
exceeding this number. What is the complexity of your algorithm? [4]
c) There are n men and n women.
Each man likes d women and each woman likes d men (“like” is mutual). A round
of dance requires a pairing of all the men and women such that the persons in
every pair like each other. Prove that it is possible to conduct d rounds of
dances such that no pair is repeated. [4]
4) Minimum path cover.
A path cover of a (directed)
graph is a set of vertex-disjoint paths such that every vertex is included in
exactly one (directed) path. The size of the path cover is the number of paths
in it.
a) Given a directed acyclic
graph explain how the problem of finding a minimum path cover can be reduced to
the problem of finding a feasible circulation. (Hint: See Circulations and
Airline Scheduling examples from Kleinberg-Tardos.) [4]
b) Given a directed acyclic
graph G = (V, E), V = (1, 2…n), construct a directed graph G’ = (V’, E’) as
follows: V’ = p0, p1, p2…pn, q1, q2…qn, q0. E’ = {(p0, pi)| i in V} U {(qi, q0)| I in V} U {(pi, qj)| (i, j) in E}. Prove that a
max-flow on G’ yields a minimum path cover on G. [4]
c) Given a directed graph find
a subgraph with the largest number of edges such that each node in the subgraph
has indegree a most 1 and outdegree at most 1. [2]
5) Miscellaneous
a) You are given a directed
graph (not necessarily acyclic) with profit values pv attached to each node v
(pv can be positive or
negative). There are no capacity limits on the (directed) edges. Find a subset
of nodes with the largest sum of profit values and with no edge coming in.
(Hint: consider the example of Project Selection from Kleinberg-Tardos.) [4]
b) Through a series of steps we
will solve the following: given an undirected graph find a subset, S, of the
nodes that maximizes the ratio E(S)/|S|, where E(S) is the number of edges
between the nodes of S, and |S| is the size of S. (This problem is an important
subroutine in certain clustering schemes; the ratio measures the cohesiveness
of the cluster.)
i)
First, solve the following auxiliary problem: given a directed graph
with node values nv (nv can be positive or negative), and edge values e(u,v), find a subset of nodes, S, that maximizes ∑(v in S) nv - ∑(v in S, w not in S)e(v,w). (Hint: Project Selection.) [2]
ii) Second, consider the problem
of finding whether in an undirected graph there exists a subset, S, for which
the ratio (∑(v in S) dv)/|S| exceeds Δ (here,
dv is the degree of node v). (Hint: Reduce to 5) b) i) by setting nv = dv - Δ and e(u, v) = 1
for all edges (u, v).) [2]
iii) Third, show that you need only consider a polynomial
number of different rational Δs to find the maximum attainable value for the ratio E(S)/|S|.
[2]