===========================================================================
CSC 363H                Lecture Summary for Week 11             Summer 2007
===========================================================================

Template for proofs of NP-completeness:  To show A is NPc, prove that
    A in NP: Describe a polytime verifier for A.
        "Given <x,c>, check c has right format and properties..."
        Argue that verifier runs in polytime and that
        x in A iff verifier accepts <x,c> for some c.
    A is NP-hard: Show B <=p A for some NP-hard B.
        "Given y, construct x as follows: ..."
        Argue that construction can be carried out in polytime
        and that y in B iff x in A
        (often by showing y in B -> x in A and x in A -> y in B).

Examples:

    INDEPENDENT-SET = { <G,k> | G is an undirected graph that contains
            an independent set of size k -- a subset of vertices with NO
            edge between any two of them }

 -  INDEPENDENT-SET (IS) is NPc:
     .  in NP: certificate = independent set
     .  NP-hard: VC <=p IS:  Given <G,k>, construct <G',k'> as
        follows: G' = G, k' = n-k.  Clearly this can be done in polytime.
        Also, if G contains a vertex cover of size k, the vertices outside
        the cover form an independent set of size n-k.  Finally, if G'
        contains an independent set of size n-k, the vertices outside the
        independent set form a vertex cover of size k.

     .  another solution: CLIQUE <=p IS:
        Given <G,k>, construct <G',k'> as follows:
        G' = G^c, the edge-complement graph of G (there is an edge (u,v)
        in G' iff the same edge is not in G); and k' = k.
        The proof works because a clique C in G is an independent set in G'.


SET-COVER = { <S, k> : S is a collection of m sets S_1, .., S_m,
      and we can select a subcollection S' of k sets from S such that
      the union of the sets in S' contains every element
      in the union of the sets in S }

SET-COVER is in NP: certificate = S'

SET-COVER is NP-hard: VERTEX-COVER <=p SET-COVER

On input <G,k>, we construct <S,k'> as follows.
Here is the analogy between the two problems:

                         VC         SC
objects being selected   vertices   sets
objects being covered    edges      elements of the universe

We maintain this analogy in our reduction as follows.
For every edge e, we add an element to the universe, call it x_e.
For every vertex v, we add to S a set S_v that contains all edges
that have v as an endpoint.
Finally, we set k' = k.

To see that the construction works, it is enough to point out that
C subset of V is a vertex cover in G IFF S_C = { S_v : v in C }
is a set cover of S.