ANLY550–Spring, 2017 Homework 4 Out: April 7, 2017 Due: April 25, 2017
1. Recall that a hash family H of hash functions mapping [n] → [r] is pairwise independent if for every 2 distinct values x1,x2 ∈ [n] = {1,…,n}, and any y1,y2 ∈ [r],
Pr [h(x1) = y1 and h(x2) = y2] = 1/r2. h←H
Also, recall that H is universal if for every pair of distinct values x1,x2 ∈ [n], Pr [h(x1) = h(x2)] ≤ 1/r.
h←H
Construct a specific family H that is universal, but not pairwise independent, and justify your answer. Write down the family as a table, with one column per input to the hash function (i.e., one column for each number in [n]), and one row per hash function. Try to make |H |, n, and r as small as possible! (There is a way to accomplish this with all of these quantities equal to 2).
2. You are given a bag of n balls, with at least 10% of the balls being blue, at least 5% of the balls being yellow, and no more than 80% of the balls being red. Asymptotically, as n grows, how many balls do you have to draw at random from the bag to see a blue ball with probability at least 2/3? (Assume that the balls are drawn with replacement, meaning that as soon as a ball is drawn, it is placed back in the bag before the next draw.)
3. Let A be a randomized algorithm for a decision problem (where the correct output is always YES or NO). Suppose that on YES instances the algorithm is always correct, but on NO instances the algorithm outputs YES with probability at most 1/2. Derive a new algorithm B that is always correct on YES instances, and on NO instances outputs YES with probability at most 2−100. How much slower is Algorithm B than Algorithm A?
4. Sometimes for special classes of inputs, NP-hard problems are solvable in polynomial time. For example, we have seen on an earlier problem set that computing the size of a maximal independent set in a tree can be done in polynomial time. Here, we will consider counting the number of independent sets in even more specialized graphs.
Consider a graph that is a line on n vertices. (That is, the vertices are labelled 1 to n, and there is an edge from 1 to 2, 2 to 3, etc.) How many independent sets are there on a line graph?
Similarly, describe how you could quickly compute the number of independent sets on a complete binary tree. (Here, just explain how to compute this number.) Calculate the number of independent sets on a complete binary tree with 127 nodes.
5. RecallthatacliqueinagraphGisacollectionofmutuallyadjacentvertices.Thedecisionversionoftheclique problem is to take a graph G and an integer k and decide if G has a clique of size k or not. The optimization version of the problem takes a graph G, and returns a largest clique in G. Show that if the decision problem has a polynomial time algorithm, then the optimization problem also has a polynomial time algorithm.
6. Consider the following problem, called 2Clique: INPUT: A undirected graph G and an integer k.
1
OUTPUT: 1 if G has two vertex disjoint cliques of size k, and 0 otherwise. (Two cliques are vertex disjoint if they do not share any vertices in common).
Show that this problem is NP-hard. Use the fact that the decision version of the clique problem in NP- complete.
7. WeknowthatthatallofNP-completereducetoeachother.Itwouldbeniceifthismeantthatanapproximation for one NP-hard problem would lead to another. But this is not the case.
Given a graph G, the Minimum Vertex Cover problem is to find the smallest set of vertices such that each edge of the graph is incident to at least one vertex of the set. Minimum Vertex Cover has a polynomial 2- approximation algorithm; that is, the algorithm always outputs a vertex cover whose size is within a factor of 2 of the optimal solution. The algorithm is to repeatedly choose an edge, add both of its endpoints into the cover, throw the vertices and its adjacent edges out of the graph, and continue. It is a 2-approximation algorithm because each edge that gets chosen during the course of the algorithm must have one of its endpoints in the cover; hence we have merely always thrown two vertices in where we might have gotten away with throwing in 1.
We know (from the NP-completeness notes, which you may want to check) that C is a cover in a graph G = (V, E ) if and only if V − C is an independent set in V . Explain why this does not yield an approximation algorithm that is within a constant factor of optimal for Maximum Independent Set. That is, show that for any constant c, there exists a graph for which even if we obtain a 2-approximation of the Minimum Vertex Cover, the corresponding independent set is not within a factor of c of the Maximum Independent Set.
The Maximum Independent Set problem and the Maximum Clique problem are related in the following way: an independent set of a graph G is a clique in the complement of G. (The complement of G is the graph that contains exactly the edges that are not in G.) Does an approximation algorithm (that is, an algorithm within a constant factor of the optimal) for the Maximum Clique problem yield an approximation algorithm (within a constant factor of optimal) for Maximum Independent Set?
2