Due: Monday, March 21
Face-to-face students: Submit in class.
Online students: submit a scanned or typed homework by email, as an attachment.
Two graphs G and H are isomorphic if it possible to assign numbers to the vertices of G and H so that G and H become identical.
For example, suppose that G has vertices {1,2,3,4} and edges {1,2}, {2,3}, {3,4}, {1,3} and H has vertices {1,2,3,4} and edges {1,2}, {2,3}, {3,4}, {2,4}. Then G and H are isomorphic. Just renumber the vertices of H according to the following table.
| Old number | New number |
|---|---|
| 1 | 4 |
| 2 | 3 |
| 3 | 2 |
| 4 | 1 |
After the renumbering, the edges of H are: {4,3}, {3,2}, {2,1}, {3,1}, and those are exactly the edges of G.
The Graph Isomorphism Problem (GI) is as follows.
Input. Two undirected graphs G and H.
Question. Are G and H isomorphic?
Show that GI is in NP.
"Jailbird notation" is a notation where you represent a number n by a sequence of n marks. For example, 5 would be represented as 11111.
Show that the subset sum problem is in P when all numbers are written in jailbird notation.
The CYCLE problem is as follows.
Input. An undirected graph G and a positive integer K.
Question. Does G have a simple cycle of length exactly k?
Show that CYCLE is NP-complete.
Sipser, page 325, exercise 7.29. (Prove that 3-Color is NP-complete.)
Hints
The variable gadget simulates a variable. How does it do that?
The "OR-gadget" is intended to simulate an or-gate, with two inputs at the bottom and output at the top. Show how to use it to encode a clausal formula as a graph coloring problem.
Give a polynomial-time reduction from the Partition Problem to the Subset Sum problem.
Give a polynomial-time reduction from 3-colorability to 4-colorability for general graphs.
Prove that, for every language S, S is NP-complete if and only
if