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.

Hi, I’m not sure if you have announced yet, but when is the second exam going to be?

It’s on Feb 16, see the Schedules page.

For number one, are we assuming the graph is of constant weight, because otherwise it will take $V^3$ time

Yes, the graph is an unweighted, undirected graph.

For bonus points, you can solve (1) when edges have weights, and the length of a path is the sum of the weights of edges on the path. Your time bounds should be the same as in the unweighted case.

Are biconnected components equivalent to 2-edge-connected or 2-vertex connected components? There is a reference to this problem in the textbook and the definition is not clear.

Biconnected component means 2 vertex connected and not 2 edge connected.

For 4b, what happens in the case that one of the vertices has multiple unmatched neighbors? Does the algorithm take the higher of the two potential edges or does the algorithm only replace the edge if each vertex in the edge has exactly one unmatched neighbor?

For 3, are we maximizing the weight of each of the k trees (k largest trees), or maximizing the total weight of the forest?

For 1 are we guaranteed that it is a connected tree?

A tree is connected by definition. If a graph is not connected, the diameter should be reported as .

For question 1, to make it simple when I prove, can I assume that the diameter of the tree is unique?

There can be multiple pairs of vertices achieving the diameter.

For second question in question 1, “Suppose we add an edge to T to get a graph G”, does it mean we know the diameter of previous tree T already?

No, you just know that G is formed by adding an edge to a tree.

So it is possible that the graph G has cycle?

For question 3, is there a speed limit, other than being a polynomial time algorithm?

No

For question 1, do we know which edge T was the one that was added to the graph?

No, you just know that it is a tree with an extra edge.

No. You are given all the vertices and edges of the graph, in the standard format of a list of edges adjacent to each vertex. Note that the edge “added” to a tree is not unique, i.e., there could be many edges so that removing any one leaves a tree.

For 3, do 2 verteces next to each other count as a 2 vertex connected component? If so, does it matter how we divide like 3 vertices in a line or 5 vertices?

For #3, do we need to return lists of all the nodes in the 2 vertex-connected components? Or would identifying the split nodes be enough?

The algorithm should output a partition of all vertices, with each part being vertices of a single 2-vertex-connected component.

A 2-vertex connected component has the property that after removing any single vertex, there is still a path between any pair of vertices. A graph with two vertices connected by a single edge is not 2-vertex connected.

Is 2-edge connected component and 2-vertex connected component graphically (visual representation) same? I am having hard time finding an image of 2-vertex connected component. I will appreciate if someone can share a link of the image.

Also, is FFT on the exam?

Is there going to be a curve on either the exam or the hw?