From the book:
Pages 693--695, Problems 2b,d,f, 10a, 18
Pages 708--710, Problem 8
A graph G= (V,E) has a Hamiltonian path iff there is a path that visits each vertex exactly once. It has a Hamiltonian cycle iff there is a cycle that visits each vertex exactly once. Note that if a graph has a Hamiltonian cycle, it has a Hamiltonian graph, but not necessarily vice-versa.
Show that Hamiltonian Path is is polynomial-time reducible to Hamiltonian Cycle. In other words, give an algorithm that takes as input G= (V,E) and outputs G'= (V',E') so that G has a Hamiltonian path iff G' has a Hamiltonian cycle. (This is the opposite direction to the reduction done in class on Tuesday, and is quite different from that reduction.) Give a one-sentence argument that your algorithm runs in time polynomial in the size of G= (V,E).
From the book:
Pages 693--695, Problems 2a,c,e, 10c, 16, 20, 22, 28
Pages 708--710, Problem 6
Let G= (V,E) be a graph and k be a natural number. Then G= (V,E),k is in IndependentSet if there are k vertices in V such that there are no edges in E between any of the k vertices.
G= (V,E),k is in Clique if there are k vertices in V that form a clique, i.e., all those vertices are connected by edges in E.
Show that IndependentSet is polynomial-time reducible to Clique. In other words, give an algorithm that takes as input G= (V,E),k and outputs G'= (V',E'),k' such that G= (V,E),k is in IndependentSet iff G'= (V',E'),k' is in Clique. Give a one-sentence argument that your algorithm runs in time polynomial in the size of G= (V,E),k.
Hint: Consider the complement graph to G= (V,E),k consistenting of the same vertex set V but the "opposite" edges, i.e., the complement graph has an edge (u,v) iff (u,v) is not in E.
Please include, at the end of the assignment, an estimate of how long you spent on the assignment. (Your answer will not affect your grade.)