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.

27 Comments

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

    Reply

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

    Reply

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

    Reply

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

    Reply

    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.

      Reply

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

    Reply

    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.

      Reply

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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s