Due date: Friday, Feb 13, at the start of class.
Submissions: Please submit your printed or hand written solutions in class. If you have a compelling reason for not being able to attend that particular class, please email your submissions to the instructor or the TA.
Policy: Write your own solutions independently; include the names of anyone you discussed the problems with.
1. For any pair of vertices in a graph, let denote the length of the shortest path from to in . The diameter of a graph is defined as:
- Give an algorithm to find the diameter of a tree in linear time, i.e., in time .
- Suppose we add an edge to to get a graph . Give the fastest algorithm you can to find the diameter of .
2. Give an algorithm to find all the -vertex-connected components of an undirected graph using a single DFS.
3. Given an undirected graph with integer edge weights and a positive integer , find a forest with trees of maximum total weight.
4. Given an undirected graph with integer edge weights, the greedy algorithm for finding a maximum weight matching is the following: pick the highest weight edge, then the next highest that maintains a matching, repeat till no more edges can be added.
(a) Show that this greedy algorithm finds a matching of weight at least half the maximum possible. Give an example where the algorithm only gets half.
(b) [Bonus] Now consider the following modification for an unweighted graph: after finishing the greedy algorithm, find any matched edge with two unmatched neighboring vertices, i.e., edges where is matched and vertices are not matched, and ; replace with and in the matching. Repeat as long as possible. Show that the matching found has weight at least of that of the maximum weight matching.
5. (No credit, for practice only). Consider the following variant of Greedy to find a maximum matching in an undirected, edge-weighted graph. At each step, consider any edge with both ends unmatched, or any 3-length path of the type described in 4(b). Of all these possibilities, choose the one that increases the weight of the matching the most. Repeat. Show that this algorithm finds a matching whose weight is at least 2/3 of that of the maximum weight matching.