CS 573: Algorithms, Fall 2013

CS 573: Algorithms, Fall 2013
Homework 2 solution Version 1.0

1. Greedy algorithm do not work. (40 pts.)
A natural algorithm, GreedyIndep, for computing maximum independent set in a graph, is to repeatedly
remove the vertex of lowest degree in the graph, and add it to the independent set, and remove all its
neighbors.
(A) (5 pts.) Show an example, where this algorithm fails to output the optimal solution.

Solution:
Consider the example depicted below. The algorithm would choose the vertex 1 and one vertex out of
4, 5, 6, or 7. Namely, generating an independent set of size two. However, the maximal independent
set has size three; namely, {2, 3, 7}.
2 5




m
er as
4




co
eH w
1 7




o.
rs e
ou urc
3 6

(B) (5 pts.) Let G be a (k, k + 1)-uniform graph (this is a graph where every vertex has degree either k
o

or k + 1). Show that the above algorithm outputs an independent set of size Ω(n/k), where n is the
aC s


number of vertices in G.
vi y re



Solution:
Since G is (k, k + 1)-uniform, at most k + 2 vertices are removed from the graph on each iteration of
n
the algorithm. Therefore, it takes at least k+2 to all vertices to be removed from the graph. This
ed d




means that the algorithm outputs an independent set of size Ω(n/k).
ar stu




This argument implies a more general result. If the maximum degree in the graph G is ∆, then there
is an independent set in G of size |V(G)| /(∆ + 1).
(C) (5 pts.) Let G be a graph with average degree δ (i.e., δ = 2 |E(G)| / |V (G)|). Prove that the above
sh is




algorithm outputs an independent set of size Ω(n/δ).
Th




Solution:
Form a new graph G′ by removing all vertices in G that have degree greater than 10δ. Let U be the
number of vertices in G that are of degree larger than 10δ. Clearly, 10δ · U ≤ 2|E(G)| ≤ nδ, which
implies that U ≤ n/10. Thus, at most n/10 vertices are removed from G when creating G′ .
Now, an independent set in G′ will be an independent set in G. Since all vertices in G′ have degree
at most 10δ, the same argument as in part (B) can be used to show that our algorithm outputs an
independent set for G′ of size
( ) ( ) ( )
|V (G′ )| 0.9n n
Ω =Ω =Ω .
10δ 10δ δ
Since this independent set is an independent set for G, we are done.


1
https://www.coursehero.com/file/10913885/HW2Solutions/

, (D) (5 pts.) For any integer k, present an example of a graph Gk , such that GreedyIndep outputs an
independent set of size ≤ |OP T (Gk )| /k, where OP T (Gk ) is the largest independent set in Gk . How
many vertices and edges does Gk has? What it the average degree of Gk ?
Solution:
Consider the following graph G:
1

2



K2k+1
0


2k




m
Our algorithm would choose vertex 0, removing vertices 1 through 2k. Then, only the clique K2k+2




er as
will remain. Then, a vertex from this clique will be chosen, deleting the entire graph. This yields an




co
independent set of size 2. However the maximal independent set actually has size 2k and contains




eH w
the vertices 1 through 2k. Therefore, the greedy algorithm outputs an independent set of size 2,




o.
k = |Opt(G)|/k.
which is ≤ 2k

rs e
(E) (20 pts.) Coloring. Let G be a graph defined over n vertices, and let the vertices be ordered: v1 , . . . , vn .
ou urc
Let Gi be the induced subgraph of G on v1 , . . . , vi . Formally, Gi = (Vi , Ei ), where Vi = {v1 , . . . , vi }
and { }
Ei = uv ∈ E u, v ∈ Vi and uv ∈ E(G) .
o
aC s

The greedy coloring algorithm, colors the vertices, one by one, according to their ordering. Let ki
vi y re


denote the number of colors the algorithm uses to color the first i vertices.
In the ith iteration, the algorithm considers vi in the graph Gi . If all the neighbors of vi in Gi are
using all the ki−1 colors used to color Gi−1 , the algorithm introduces a new color (i.e., ki = ki−1 + 1)
and assigns it to vi . Otherwise, it assign vi one of the colors 1, . . . , ki−1 (i.e., ki = ki−1 ).
ed d




Give an example of a graph G with n vertices, and an ordering of its vertices, such that even if G can
ar stu




be colored using O(1) (in fact, it is possible to do this with two) colors, the greedy algorithm would
color it with Ω(n) colors. (Hint: consider an ordering where the first two vertices are not connected.)
Solution:
sh is




x1 1 1 y1
Consider the bipartite graph G ={(X, Y, E), where } X = {x1 , . . . , xn },
Th




Y = {y1 , . . . , yn }, and E = (xi , yj ) i ̸= j and the ordering
x2 2 2 y2
x1 , y1 , x2 , y2 , . . . , xn , yn . Then, using our greedy algorithm, the ver- x3 3 3 y3
tices x1 , . . . , xn will be colored using n distinct colors. Thus, using a
total Θ(n) colors. But it is possible to color the graph using only 2 x4 4 4 y4
colors, since it is a bipartite graph. See figure on the right.
x5 5 5 y5




2
https://www.coursehero.com/file/10913885/HW2Solutions/