and L₂ NP   

Proof:

Claim: Need to show that if proc L₂ runs in det polynomial time, then P = NP. (Cook's Theorem: Satisfiability is in P iff P = NP, and subsequent definition of NP-Complete) Note, a proof of the lemma would be more straight-forward simply using the transitive property of reduction .
The proof below (of the claim) is to make you think about Cook's theorem and its implications.

If proc L₂ runs in det. poly. time then so does proc. L₁.
But L₁ is NP-complete.
Therefore P = NP.

Satisfiability clique decision problem (CDP)

Ex: F = (x₁ V x₂ V x₃) (¯x¯₁ V ¯x¯₂ V ¯x¯₃)

The graph contains 6 cliques of size 2. Consider the clique with vertices { x₁, ¯x¯₂ }. By setting x₁ = true and ¯x¯₂ = true (i.e., x₂ = false), F is satisfied. The x₃ can be either true or false

another example

G can be constructed from F in deterministic polynomial time

Claim: F is satisfiable iff G has a clique of size at least k

Proof: ==> Suppose F is satisfiable.

Consider any truth assignment for literals which satisfies F.
Then at least one true literal in each clause

Let S = {< x, i > | x is true in c_i} be a set containing exactly one true literal from clause i

S is a subset of nodes in G.
Let < x, i > and < y, j > belong to S.

Since S contains only one literal from each clause, i j
Also, if x = ¯y¯, both x and ¯y¯ cannot be true.
Therefore x ¯y¯

Since i j and x ¯y¯, there exists an edge in G (< x, i >, < y, j >) This is true for all pairs of nodes in S.
Moreover, |s| = k

Therefore S is a clique in G of size k.

Let S be the set of nodes in the clique.

Since S cannot contain more than one node which came from the same clause in F, |S| = k.

S = { < x, i > | < x, i > a node in clique}.

S' = {x | < x, i > S }

If < x, i > and < y, j > are nodes in S then x ¯y¯ and i j (otherwise there would be no edge in G between <x,i> and <y,j> )

Therefore, assigning x = 'true' for all x S' satisfies F

Node cover

|V'| = size of node cover

Node cover decision problem:

Given G = (V,E) and k, does G contain a node cover of size at most k?

Maximization - at least (maybe more but at least...) - no less than - so often want big for "best" (like glb)
    A graph with a clique of size at least 3 may also have one of 4
Minimization - at most - (maybe less but no more than...)- so want small for "best" at most (like lub)
     A graph with a node cover of size 4 might also have one of size 2

Clique (CDP) node cover (NCDP)

G' = (V,E')
Where E' = {(u,v) | (u,v) E}       (basically we are looking at the complement) (the example above is not the complete complement or we would have a complete mess in the drawing - each node in the V_C would connect to the nodes to which it is not originally connected - in this particular case to each of those in V_N.)

Claim: G has a clique of size at least | V_C | iff G' has a node cover of size at most | V_N |     (could be less, but cannot be more - since any more would start needing nodes of the clique to cover)

| V | = n, | V_C | = k , | V_N |= n-k         i.e., k is the clique size of G and n-k is the node cover size of G'

Ok, since there are no edges in E' connecting 2 vertices in V_C (i.e., no edges in the clique (with V_C vertices) are in the compliment by our partition of G) , the remaining n-k vertices in V_N must cover all edges in E' (a graph and its compliment will be all possible edges between all vertices).
More specifically: example 11.13 in text

The figure shows a graph G and its complement G'. In this figure G' has a node cover of {4,5}, since every edge of G' is incident either on the node 4 or on the node 5. Thus, G has a clique of size 5-2=3 consisting of nodes 1,2,3.

Try the reduction on these graphs (clique size given)

Satisfiability clique decision problem (CDP)       ;       Clique node cover decision problem (NCDP)

Therefore Satisfiability node cover       and hence, the node cover decision problem is NP-Hard (what to do for NP-Complete?)
See for more

Directed Hamiltonian Cycle (DHC)

G = (V, E) - directed graph

Hamiltonian cycle: cycle passing through all nodes in V.

    No H.C.

DHC NP

Recall (we did): Non-deterministic polynomial time algorithm

Satisfiability DHC

Proof next time