1. The transitive reduction of a directed graph G = (V;E) is a graph G0 = (V;E0)
on the same set of vertices, such that u and v are connected by a path in G if and
only if u and v are also connected by a path in G0, and no edge can be removed
from G0 while preserving this property. Show how to compute the transitive reduc-
tion of a graph G in polynomial time. Can you also compute the number of distinct
transitive reductions in polynomial time? (15 pts.)
2. Show that a graph G has treewidth 1 if and only if it is a disjoint union of trees.
(10 pts.)
3. Suppose that you have a graph G and a tree decomposition of G of width k contai-
ning n bags. Design an algorithm to convert it into a nice tree decomposition with
O(nk) bags in time polynomial in k and n. [Recall that a nice tree decomposition
has 4 types of bags: leaves, with a single node in the bag and no children; introduce
and forget nodes, with a single child and bags di ering from their bag by a single
element; and join nodes, with two children and bags identical to their children]. De-
monstrate your algorithm on the tree decomposition of the \square inside a square"
graph seen in class. (15 pts.)
4. Describe an algorithm for computing the size of the maximum independent set of
a graph G using a nice tree decomposition of G. Be careful with distinguishing
between leaf nodes, introduce nodes, forget nodes and join nodes. Illustrate your
algorithm on the nice tree decomposition from the previous problem. Hint: when
you have a nice tree decomposition, you only need to calculate A(S;i), not B(S;i;j).
(15 pts.)
5. (29.1-9 in CLRS) Give an example of linear program for which the feasible region
is not bounded, but the optimal objective value is nite. (15 pts.)
6. (29.2-6 in CLRS) Write down a linear program that, given a bipartite graph G =
(V;E), solves the maximum bipartite matching problem. (10 pts.)
7. Prove or disprove the claim that the constraint matrix in the previous problem is
totally unimodular for any bipartite graph G. (30 pts.)