HW 2

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 $u, v$ in a graph, let $l(u, v)$ denote the length of the shortest path from $u$ to $v$ in $G$. The diameter of a graph $G$ is defined as:

$d(G) := \max_{u,v \in V(G)} l(u, v)$

• Give an algorithm to find the diameter of a tree $T$ in linear time, i.e., in time $O(|V| + |E|)$.
• Suppose we add an edge to $T$ to get a graph $G$. Give the fastest algorithm you can to find the diameter of $G$.

2. Give an algorithm to find all the $2$-vertex-connected components of an undirected graph using a single DFS.

3. Given an undirected graph with integer edge weights and a positive integer $k$, find a forest with $k$ 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 $(u,v), (v,x), (x,z)$ where $(v,x)$ is matched and vertices $u, z$ are not matched, and $w(u,v)+w(x,z) > w(v,x)$; replace $(v,x)$ with $(u,v)$ and $(x,z)$ in the matching. Repeat as long as possible. Show that the matching found has weight at least $2/3$ 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.

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

2. 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.

3. 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.

4. 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?

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

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

6. 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?

1. 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.

7. 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?

8. 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?

1. 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.

9. 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.