```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

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