1. A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs are stored in adjacency-list format; you must specify any additional data structures that are needed.

2. Give a polynomial-time algorithm that ?nds rV/21 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

3. Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-?rst search.

4. Let G be a directed graph with N vertices. A vertex s is called a sink if, for every v in V such that s /=v, there is an edge (v, s), and there are no edges of the form (s, v). Give an O(N) algorithm to determine whether or not G has a sink, assuming that G is given by its n × n adjacency matrix.