msge.us

The next few posts will be simple reductions listed in a graduate level algorithms course. I expect them to cover the following problems: vertex cover, independent set, and clique, hamiltonian cycle, hamiltonian path, hamiltonian with specified edge, hamiltonian path from A to B. Also, the reductions will follow the same template, detailed as follows:

Show that if R is NP-Hard, then Q is NP-Hard.

This statement is asking us to show that . This can also be phrased as, “reduce R to Q”.

1. Specify a transformation  (using pseudocode) of an instance of problem to an instance of problem .
2. Show that the transformation is deterministic in polynomial time (i.e. give an upper bound for a reasonable implementation of the transformation in Big-O notation)
3. Prove the claim: if is a “yes” instance for problem , then is a “yes” instance for problem .
4. Prove the claim: if is a “yes” instance for problem , then is a “yes” instance of problem .

We note that by proving the claims of step 3 and step 4, we prove that a “yes” instance to problem will be transformed deterministically in polynomial time by transformation to a “yes” instance to problem . Likewise, a “no” instance to problem will be transformed deterministically in polynomial time by transformation to a “no” instance to problem .