Description
-
State the following optimization problems as decision problems:
Vertex Cover
Independent Set Knapsack
Longest Increasing Subsequence Coin Row
-
Fill in the reduction diagram explicitly for the following reductions. You should include what a specific instance and solution looks like for each problem in the reduction.
Vertex Cover ! Independent Set Clique ! Independent Set
3SAT ! Stingy SAT (see problem 6)
Vertex Cover ! Set Cover (see problem 8)
Clique ! Subgraph Isomorphism (see problem 7)
-
Consider the Clique problem restricted to graphs in which every vertex has degree at most 3. Prove that this problem is in NP.
-
Suppose that Vertex Cover is NP-Complete (it is), use that fact to show that Independent Set is NP-Complete.
-
Suppose that Clique is NP-Complete (it is), use that fact to show that Independent Set is NP-Complete.
-
Stingy SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k variables are true, if such an assignment exists.
Prove that Stingy SAT is NP-complete. (Hint: Use 3SAT)
-
In the Subgraph Isomorphism problem we are given as input two undirected graphs G and H, we wish to determine whether G is a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V (H).
Prove that Subgraph Isomorphism is NP-complete. (Hint: Use Clique)
-
In the Set Cover problem, we are given a set (“universe”) of elements: f1; 2; : : : mg and a set S of n sets whose union is the universe. The goal is to find a subset of S of size y whose union equals the universe. Note that this is the decision version of the Set Cover problem stated above.
Prove that Set Cover is NP-complete. (Hint: Use Vertex Cover)
-
Design an approximation algorithm for the Set Cover Problem: Given a universe U of n elements, and
a collection of subsets of U say S = fS1; S2; : : : ; Smg where every subset Si has an associated cost,
c(Si). Find a minimum cost subcollection of S that covers all elements of U. (Hint: Greedily choose the set whose cost effectiveness is best – the ratio of cost to newly added elements is minimum.)
-
Given an undirected graph G = (V; E) in which each vertex has degree d, show how to efficiently find an independent set whose size is at least 1=(d+ 1) times that of the largest independent set. (Hint: Consider the basic greedy algorithm of choosing the vertex of minimum degree.)
-
In the Minimum Steiner Tree problem, the input consists of:
A complete graph G = (V; E)
Distances duv between all pairs of vertices and A distinguished set of terminal nodes V 0 V
The goal is to find a minimum cost tree that includes the vertices V 0 . This tree may or may not include vertices in V n V 0 . Suppose the distances in the input are metric:
d(x; y) 0 for all x and y.
d(x; y) = 0 if and only if x = y.
d(x; y) = d(y; x).
d(x; y) d(x; z) + d(z; y)
Show that an efficient 2-approximation algorithm for Minimum Steiner Tree can be obtained by ignoring the nonterminal vertices and simply returning the minimum spanning tree on V 0 . (Hint: Recall our approximation algorithm for the TSP.)
2 of 2