CompSci 163/265, Spring 2015, Homework 2

1. Describe a linear time algorithm that takes as input a directed graph and partitions its edges into two subsets such that each of the two subsets forms a directed acyclic graph.

2. Suppose that $G$ is a directed acyclic graph with $n$ vertices, with the special property that there is only one way to place the vertices of $G$ into a topological order.

1. How many edges can the transitive closure of $G$ have, as a function of $n$?

2. How many edges can the transitive reduction of $G$ have, as a function of $n$?

3. (For 163 students:) If $G$ is a directed acyclic graph without any redundant edges (it is its own transitive reduction), is it always possible to assign the vertices to layers in such a way that each edge goes downwards from one layer to the next consecutive layer? For this problem, there is no limit on the number of vertices per layer. If the answer is yes, explain why. If the answer is no, find a counterexample.

(For 265 students:) Find an example of a directed acyclic graph for which the Coffman–Graham algorithm, with three vertices per layer, can use more layers than the optimum layering. Show both the optimum layering and the layering found by the algorithm.

4. Suppose we are given as input a directed graph (not necessarily acyclic) and we want to add one edge to the graph so that the augmented graph is strongly connected. Describe a linear time algorithm for finding such an edge, if it exists. (Hint: use the condensation, and look at the numbers of incoming and outgoing edges of the nodes in the condensation.)