===========================================================================
CSC 363                     Homework Exercise 5                   Fall 2008
===========================================================================

Due: by 2pm on Wed 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.  (a) Prove that P is closed under intersection, i.e., for all languages
        A,B (- P, A n B (- P.

    (b) 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 }

    (a) 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?

    (b) 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.