Ch.11
P, NP and Decision Problems
Problem Examples Continued (again)

1. show that the problem is in NP (L₂ NP)
2. show that a known NP-Complete problem can be reduced to this problem

Known L₁ NP-Complete.       If L₁ L₂     and L₂ NP       L₂ NP-Complete

Again, why is the reduction in this direction?

Be careful. To reduce L₂ L₁ would achieve nothing; it would merely show that L₂ could be solved by using L₁ ( a problem that can be solved no faster than any other NP-complete problem). Perhaps L₂ could be solved in polynomial time - showing it could be solved using a known NP-complete problem does not say too much. But saying that I could solve L₁ (a known NP-Complete problem) if I could solve L₂, tells me that they are equally tough.

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

Suppose F is an instance of Satisfiability

Construct directed graph G such that F is satisfiable iff G has a DHC.

n variables 2n columns (one for each literal)
r clauses r rows

This graph would correspond to the formula:
F = (x₁ V ¯x¯₂ V ¯x¯₃) (¯x¯₁ V x₂ V x₃) (x₁ V x₂ V ¯x¯₃)

If F is satisfiable make circuit pass through 'true' column of each variable.
This is nice, it shows we can achieve a Satisfiablity solution with the graph.

Some solutions would be {T, T, T}, {T, F, T}, {F, F, F}, {T, T, ?}, {T, ? , T}, { ? , T, F}

Consider {T, F, T} - take False literals left out of circuit.

But this only includes the literals that were true in our circuit. We need the hamiltonian circuit to include all nodes. So we need a way to include the false literals. (Remember, we are reducing Sat to DHC and a DHC must go through all nodes.)

We will gather all the false literals in the separate clauses. We need the option to bypass each literal in c_i

Since not all literals can be false in a given clause -- (otherwise Hamiltonian Circuit   F is Satisfiable)

                            clause i

Here, Literal i₆ is the only true literal (must have one)

So, we need a way to get in (and out) at any place in this loop so that we can capture only the false literals

This // lines shows such a path (missing some nodes - those that would be true)

Hamiltonian circuit once path leaves A_i, must pass through all 's before reaching B_i (we need to hit all nodes for a DHC)
So, we need to pick up the ones for the T literals

Hamiltonian circuit must pass through either vertically or horizontally

use proper structure to be able to rebuild true and false nodes/literals from path given (i.e, to get solution back to SAT)

C_i

Hamiltonian circuit must enter and leave through adjacent 's.
At least one left out of 'false' path.

And, if you thought this was confusing, see the book! (page 523)

Traveling salesperson problem

DHC Traveling salesperson problem

Directed graph G= (V,E)

Costs on edges

Hamiltonian circuit of cost < M ?

Given an instance of DHC construct complete graph G-> = (V,E->) Costs:

Hamiltonian circuit in G iff tour of cost < | V |.

Can you conclude from DHC that finding a Hamiltonian circuit in an undirected graph is, NP-complete?

INDEPENDENT SET, VERTEX COVER and CLIQUE

Remember Node Cover

From Garey and Johnson,

Despite the fact that VERTEX COVER and CLIQUE are independently useful for proving NP-Completeness results, they are really just different ways of looking at the same problem. To see this, it is convenient to consider them in conjunction with a third problem, called INDEPENDENT SET.

An independent set in a graph G = (V, E) is a subset V' V such that for all u, v V', the edge {u,v} is not in E. The INDEPENDENT SET problem asks, for a given graph G= (V, E) and a positive integer J < |V|, whether G contains an Independent set V' having |V'| > J. The following relationships between independent sets, cliques, and vertex covers are easy to verify.

Lemma 3.1. For any graph G= (V, E) and subset V' contained in V, the following statements are equivalent:

1. V' is a vertex cover for G
2. V - V' is an independent set for G
3. V - V' is a clique in the compliment G^c of G, where G^c = (V, E^c) with E^c = {{u,v}: u,v V and {u,v} not E}

Other sources:
Def: In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V' (a subset of V) such that for every two vertices in V', there is no edge connecting the two. In other words, each edge in the graph is incident to at most one vertex in the set. The size of an independent set is the number of vertices it contains.

in NP-complete (goodness! Wikipedia has proofs of NP-Complete!). Another (reduction from Clique), or reduction from SAT