Consider the following problems:

FULL CYCLE SEARCH VERSION (FCS):

Input: Graph G = (V, E)

Output: A cycle that goes through all the nodes of G exactly once. FULL CYCLE DECISION VERSION (FCD):

Input: Graph G = (V, E)

Output: If G has cycle that goes through all the nodes of G exactly once return YES, otherwise NO. FULL PATH DECISION VERSION (FPD):

Input: Graph G = (V, E) and two nodes s and t.

Output: If G has a path from s to t that goes through all the nodes of G exactly once return YES, otherwise NO.

a) (5 pts) Show that FCS reduces to FCD.

b) (5 pts) Show that FPD reduces to FCD.

c) (5 pts) Show that FCD reduces to FPD.

For full credit, when you reduce problem A to problem B, you should describe clearly how B can be used to solve A. You should also indicate the appropriate transformation, if any.

Problem 3 (15 points) Consider the following problems: FULL CYCLE - SEARCH VERSION (FCS): Input: Graph G -(VE) Output: A cycle that goes through all the nodes of G exactly once. FULL CYCLE DECISION VERSION (FCD): Input: Graph G - (VE) Output: If G has cycle that goes through all the nodes of G exactly once return YES, otherwise NO. FULL PATH - DECISION VERSION (FPD): Input: Graph G = (V. E) and two nodess and t. Output: If has a path from stor that goes through all the nodes of G exactly once return YES, otherwise NO. a) (5 pts) Show that FCS reduces to FCD. b) (5 pts) Show that FPD reduces to FCD. c) (5 pts) Show that FCD reduces to FPD. For full credit, when you reduce problem A to problem B, you should describe clearly how B can be used to solve A. You should also indicate the appropriate transformation, if any