CSC373H Lecture 9
Dan Zingaro
November 14, 2016
Vertex Cover
A vertex cover of undirected graph G = (V,E) is a set of vertices X such that, for any edge (u,v) in E, u ∈ X or v∈X
That is, it’s a set of vertices such that each edge has at least one of its endpoints in the set
The size of a vertex cover is the number of vertices in it
The vertex cover problem is to find a vertex cover of minimum size
Vertex Cover: Examples
1. What is the minimum vertex cover of this graph?
a
bcdef
2. A clique is a graph that has an edge connecting every pair of vertices. What is the minimum vertex cover in the n-node clique?
NP-Complete Problems
Unfortunately, vertex cover is what is known as an NP-complete problem
NP-complete problems are problems for which no exact polynomial-time algorithm is known
Many believe that no polynomial-time algorithm will ever be found for these problems
So, rather than search for an implausible exact, polynomial algorithm, one approach is to study approximation algorithms
…andwecanuseourexistingalgorithmdesigntechniquesto design these approximation algorithms!
Approximation Ratios
Let C be the solution returned by our algorithm and C∗ be the optimal solution
Vertex cover is a minimization problem: we want to minimize a quantity (number of vertices)
We say that an algorithm for a minimization problem has approximation ratio r if |C|/|C∗| ≤ r
We can do analogously for a maximization problem, where the goal is to maximize a quantity
Greedy Algorithm for Vertex Cover
The algorithm is fast. But how good is it?
C = {} # vertex cover F=E
while F != {}:
let (u, v) be some edge in F
C = C + {u, v}
remove from F any edge incident to u or v
return C
Greedy Algorithm: Approximation Ratio Proof
Theorem: the greedy algorithm is a 2-approximation algorithm for vertex cover.
C is a vertex cover, because the algorithm removes only covered edges from F until F is empty
Let A denote the edges (u,v) chosen by the algorithm
Let C∗ be an optimal vertex cover
Any vertex cover, including C∗, must include at least one endpoint of each edge in A
No two edges in A share an endpoint
Therefore, number of vertices in C∗ must be ≥ number of edges in A
Greedy Algorithm: Approximation Ratio Proof…
From previous slide, we have |C∗| ≥ |A|
As each edge in A results in two vertices added to C, we also have |C| = 2|A|
|C| = 2|A| ≤ 2|C∗|
Back to Knapsack
Recall the 0-1 knapsack problem that we studied
We gave a dynamic-programming algorithm whose runtime was O(nW), where n is the number of items and W is the knapsack weight
Unfortunately, this is not a polynomial-time algorithm
We want a big-oh bound in terms of the size of the input
However, W is not the size of the integer W
Instead, log2 W is the size of integer W (number of bits required to represent W )
Back to Knapsack…
Letx=log2W bethesizeofW
Then,W=2x
So, our algorithm is O(n2x), which is not polynomial in x
In fact, 0-1 knapsack is NP-complete, so we suspect that there is no polynomial-time exact algorithm
Buttherearepolynomial-timeapproximationalgorithms…
Greedy Algorithm for Knapsack
The algorithm is fast. But how good is it?
sort the items by decreasing v_i/w_i
for each item:
if the item fits in the knapsack, add it
otherwise, stop the algorithm
Greedy Algorithm: Arbitrarily Bad
Knapsack is an example of a maximization problem
The given greedy algorithm has no finite approximation ratio
That is, we can make the approximation ratio arbitrarily bad
e.g. considerW =1000,w1 =2,v1 =2,w2 =1000, v2 = 999
The greedy algorithm yields only 2/1000 of the optimal value!
The algorithm is therefore not useful as-is