Problem Set - IV 10/31/11

(Due at the beginning of class on 11/16/11)


CS G713U Advanced Algorithms

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 Dilworths 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 ( 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, 2n), construct a directed graph G = (V, E) as follows: V = p0, p1, p2pn, q1, q2qn, 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]