Homework Exercise 5

Due: by 2pm on Web 12 Nov
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

    1. Prove that P is closed under intersection, i.e., for all languages A,B ∈ P, A ∩ B ∈ P.

    2. Prove that NP is closed under the star operation, i.e., for all languages A ∈ NP, A* ∈ NP.

  2. Consider the following languages:

    VC (VERTEX-COVER) = { <G,k> : G = (V,E) is an undirected graph and k is a positive integer such that G contains some vertex cover of size k, i.e., a subset of k vertices C ⊆ V such that for every edge (u,v) ∈ E, u ∈ C or v ∈ C or both }

    IS (INDEPENDENT-SET) = { <G,k> : G = (V,E) is an undirected graph and k is a positive integer such that G contains some independent set of size k, i.e., a subset of k vertices S ⊆ V such that there is no edge between any two vertices in S }

    1. Consider the graph G = (V,E) with V = {a,b,c,d,e,A,B,C,D,E} and E = { (a,b), (b,c), (c,d), (d,e), (e,a), (A,C), (C,E), (E,B), (B,D), (D,A), (a,A), (b,B), (c,C), (d,D), (e,E) }.
      Give a vertex cover of G of size six. What can you say about the vertices outside of your vertex cover?

    2. Give a detailed proof that VC ≤p IS — i.e., carefully justify every assertion you need about the properties of vertex covers and independent sets.