Homework #1 in Design and Analysis of Algorithms
Question 1
A clique in a graph G = (V,E) is a subset C ⊆ V such that there is an edge between every pair of
vertices in C. A maximum clique is a clique with a maximum number of vertices.
(a) Show that the minimum vertex-cover problem and the maximum clique problem have the same
complexity up to polynomial factors. That is: If you had an algorithm for solving the minimum
vertex-cover problem in time T (n) (where n = |V |) then you would have an algorithm for solving
the maximum clique problem in time T (n) + poly(n) (where poly(n) denotes some polynomial
in n), and that the reverse statement also holds.
Hint: think of the complementary graph (that is, in which non-edges are replaced by edges and
edges by non-edges).
(b) Given that we have an approximation algorithm for the minimum vertex-cover with approxima-
tion factor 2, does this imply, given the above item, that we have approximation algorithm for
the maximum clique problem?
Question 2
Let G = (V,E) be a graph such that every vertex in the graph has degree at most d. Show that the
minimum vertex cover of G is of size at least m
2d−1 (where m = |E|). (Think of the approximation
algorithm described in class and the relation between the number of edges that are included in the
maximal matching that the algorithm determines compared to the number of edges that not included
in the matching.)
Question 3
Let G = (V,E) be a connected graph (that is, there is a path between every pair of vertices), where
n = |V | ≥ 2. Recall that a Depth First Search (DFS ) in a graph is a procedure for visiting all vertices
in the graph (assuming it is connected), in the following manner. Starting from an arbitrary initial
vertex v0, at each step, if the current vertex has some neighbors that have not yet been visited, then
we continue to one of those neighbors. Otherwise, we return back to the previous vertex. The search
ends when we have returned to v0 for the last time (and can’t continue since all its neighbors have
already been vi