CSCC63 Assignment 3 Due 11:59pm, April 12 Warning: Your electronic submission of a PDF to Crowdmark affirms that this assignment is your own work and no one else’s, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCC63. Note that using Google or any other online resource is considered plagiarism. We have stated in class that a number of languages are NP-complete: these include 3SAT, Clique, 3COL, VC, Subset-Sum, and Ham-Path. You may assume that these languages are NP-complete here. You may also refer to the fact that 2SAT and 2COL are in P. 1. (15 marks) Consider the language Contains-Subgraph: INPUT: Two graphs G and H. QUESTION: Does G contain H as a subgraph? Show that Contains-Subgraph is NP-complete. 2. (15 marks) Consider the language 1-2-3-Subset: INPUT: A finite multiset S of integers. QUESTION: Can S be partitioned into three disjoint sets A, B, and C such that ∑ x∈C x = 3 (∑ x∈A x ) and ∑ x∈B = 2 (∑ x∈A ) ? Show that 1-2-3-Subset is NP-complete. 3. (15 marks) Consider the language Many-Paths: INPUT: A directed graph G, two vertices s and t, and a number k. QUESTION: Are there at least k disjoint paths from s to t, all of which have different lengths? By disjoint paths, we mean that the only vertices any two of the paths share are s and t. Show that Many-Paths is NP-complete. 4. (15 marks) Consider the language Choice-Set: INPUT: A finite set S of integers, an integer k, and a finite collection of sets X1, X2, . . . Xm such that for every i, |Xi| ≥ 3 and Xi ⊆ S. QUESTION: Is there a size k subset T ⊆ S such that for every i, T ∩Xi 6= ∅? Show that Choice-Set is NP-complete. 5. (10 marks) Consider the following function: Longest: INPUT: A directed graph G and two nodes s and t. OUTPUT: The length of the longest s to t path in G. It is possible to show that unless P = NP, there is no way of approximating this function with an approximation ratio of better than 1/2. Strengthen this result to show that there is no way to approximate this function with any approximation ratio better than 1/4. 1 6. (10 marks) We’ve argued that 2SAT and 2COL are both in P. Here’s another problem in P: DAG-HAM-PATH INPUT: A DAG (directed acyclic graph) G, and two nodes s and t. QUESTION: Does G have a Hamiltonian path from s to t? Write an algorithm to prove that DAG-HAM-PATH is in P. 7. (10 marks) Consider the following problem: Test-3COL: INPUT: A graph G and a subset S ⊆ V of vertices. QUESTION: Is there an assignment of the colours {red, blue, green} to the vertices in S that does not match any valid 3-colouring on all of G? Show that Test-3COL is in PSPACE. 8. (10 marks) Show that #3COL is #P-complete by finding a parsimonious reduction from #3SAT. 9. Bonus (10 marks — your mark will be rounded to the nearest multiple of 2.5) Show that #HAM- PATH is #P-complete by finding a parsimonious reduction from #3SAT. Note: For problems 8 and 9, you may find the “Polytime Reductions” handout useful as a starting point. 2
欢迎咨询51作业君