November 26


*  Reduction


   Here is a famous reduction graph


      SATISFIABILITY
	    |
	    |
	    |
	    v
	   3SAT
	  /    \
	 /      \
	/        \
        v        v
       3DM     CLIQUE
        |        /\
        |       /  \
        |      /    \
        v      v    v
    PARTITION HC    VC
	       |
	       |
	       |
	       v
	      TSP


*  HC is polynomial-time reducible <=P to TSP

   Given graph G = (V,E)

   Transformation f outputs complete graph with vertices V.

   Weights of edges = 1         if e in E
		      |v| + 1   if e not in E

   Function also outputs number |v|.

   There exists a TSP tour in this complete graph of size <= |v| iff
   there exists HC in original graph.

   The function f is clearly implementable in polynomial time.


*  Cook's Theorem

   Cook's theorem states and proves that any NP problem can be
   polynomial-time reduced to a SAT problem.

   This SAT is NP-Complete
      SAT is in NP
      All problems in NP can be polynomial-time reduced to SAT


*  Proving that problems are in NP-Complete

   Because we know that there are some problems to which all problems in NP can
   be reduced in polynomial time, we do not have to show this for each new
   problem we want to show is NP-Complete.

   Procedure for problem Q:
       1) Show Q is in NP
       2) Select known NPC problem Q'
       3) Construct a function f:Q'->Q
       4) Show f is polynomial

   For example, we know every problem in NP <=P SAT.
   If we show SAT <=P 3SAT, then by transitivity of <=P,
      every problem in NP <=P 3SAT

   There are many known NP-complete problems.
   See Garey and Johnson.
   Until proven, many people have been frustrated trying to design algorithms to
      solve these problems.


* Examples


  - CLIQUE is NP-Complete

    Given graph G = (V,E), find largest subset V' <= V s.t.
    forall u,v in V', (u,v) in E

    CLIQUE = {: G is a graph with a clique of size k}



    Show sample page 188

    1) To show CLIQUE in NP, we use set V' of vertices as a certificate.
       Verifying is polynomial time, check whether for every pair u,v in V',
       the edge is in E (|V'|^2 pairs).

    2) 3SAT <=P CLIQUE

    Start with instance of 3SAT.

    Let f = C1 & C2 & ... & Ck be 3CNF with k clauses.
    For r = 1,2,...,k, each clauses has three distinct literals
    l1^r, l2^r, l3^r.

    Construct a graph G s.t. f is satisfiable iff G has a clique of size k.

    For each Cr in f, put triple of vertices v1^r, v2^r, v3^r in V.
    Add edge (vi^r vj^s) if
       (1) vi^r and rj^s are in different triples (r neq s), and
       (2) their corresponding literals are consistent (li^r is not the
	   negation of lj^s).

    This graph is constructed in polynomial time.

    If f = (x1 v -x2 v -x3) ^ (-x1 v x2 v x3) ^ (x1 v x2 v x3)

    then graph G is
    show picture page 948 of CLR.

    Is this a reduction?
    Suppose f has a satisfying assignment.  Then each clause Cr contains
    at least on eliteral li^r that is assigned 1, and each such literals
    cooresponds to a vertex vi^r.

    Picking one such "true" literal from each clause yields a set V' of
    k vertices.

    Is V' a clique?  For any two vertices vi^r, vj^s, r neq s, the corresponding
    literals are mapped to 1 by the satisfying assignment and thus the literals
    cannot be complements.  By the construct of G, the edge (vi^r vj^s) belongs
    in E.

    Proving the other direction, if G has a clique V' of size k, no edges in G
    connect vertices in the same tripe, so V' contains exactly one vertex
    per triple.  Assign to each literal li^r s.t. vi^r in V' without fear of
    assignment 1 to a literal and its complement.  Each clause is satisfied, and
    f is satisfied.


    -  VERTEX COVER is NP-Complete

    VC:  Given graph G = (V,E), find the smallest subset V' <= V s.t. each edge
    used in G is incident to some vertex in V'.

    VC = {, k}:  G = (V,E) is a graph, and there exists a subset V' <= V s.t.
	  |V'| <= k and forall e in E, e contains some element of V' as one of
	  its endpoints.}

    Show picture on page 186.

    1) Given graph G = (V,E) and an integer k, witness is vertex cover V'.
       Verify that |V'| = k (1 step) and then check for each edge (u,v) in E,
       whether u in V' or v in V' (linear in number of edges).

    2) CLIQUE <=P VC.
    Given G = (V,E), define "complement" of G as G com = (V, E com), where
    E com = {(u,v): (u,v) not in E).

    The reduction algorithm computes complement of G in polynomial time.
    The output is the instance  of VC.

    G has a clique of size k iff G com has a vertex cover of size |V| - k.

    If G has clique V' <= V, |V'| = k, let (u,v) be any edge in E com.
    Then (u,v) not in E, so at least one of u or v does not belong to V'.
    Equivalently, at least one of u or v is in V - V', which means (u,v) is
    covered by V - V'.  Every edge of E com is thus covered by a vertex in
    V - V', so V - V' is a vertex cover for G com.

    Proving the other direction, suppose that G com has VC V' <= V,
    |V'| = |V|-k.  Forall u,v in V, if (u,v) in E com, then u in V' or v in V'
    or both.  Thus forall u,v in V, if u not in V' and v not in V', then
    (u,v) in E.  Thus V - V' is a clique and has size |V| - |V'| = k.


   - PARTITION is NP-complete
     Skip proof for now.

     Given a finite set A and a "size" s(a) in N+ for each a in A, find a subset
     A' <= A s.t.

	sum over a in A' of s(a) = sum over a in A-A' of s(a)

     PARTITION = {, s(a)): there exists subset A' of A such that the sum of
	the two subsets is equal}

     For example, if A = {a=1,b=2,c=3,d=4,e=5,f=7,g=8}, then one possible subset
     is A' = {a,b,c,d,e} and A - A' = {f,g}.


   - KNAPSACK is NP-Complete

     Given a finite set U, a "size" s(u) in N+ and a "value" v(u) in N+ for each
     u in U, a size constraint B in N+, and a value goal K in Z+, is there a
     subset U' <= U s.t.

	sum of sizes in U' is <=B and sum of values in U' is >=K?

     This can be seen as a knapsack, which has a size limit for the objects.

     The goal is to pick a collection of objects that will fit in the knapsack
     and whose total value is at least K (K is input).

     KNAPSACK = {(U,s,v,B,K):  there exists subset U' of U s.t. the sum of s
	values is at most B, and the sum of v values is at least K}

     1) KNAPSACK in NP
	Given a subset, in linear time compute sum of sizes and in linear time
	compute sum of value.  In constant time see if sums fit limits.

     2) PARTITION <=P KNAPSACK

	This is a different and value approach.
	We restrict KNAPSACK in a way that makes it polynomial-time reducible
	(in fact equal) to PARTITION.  We are still showing KNAPSACK is at least
	as hard as PARTITION, which is our goal.

	We can restrict KNAPSACK to equal PARTITION by only allowing instances
	in which
	s(u) = v(u) for all u in U and B = K = 1/2*(sum over u in U of s(u)).