The Longest Cycle problem (LONG-CYCLE) accepts a vertex v in graph G, along with a length k, and returns whether the graph contains a cycle of length k or more that includes v.

The Longest Path problem (LONG-PATH) accepts two vertices u and v in a graph G and a distance k, and it returns whether G contains a path of length k or longer between u and v.

1. If LONG-CYCLE NP-Hard and LONG-PATH NP, which of the reductions below would be used to prove that LONG-PATH NP-Complete? You may assume that both reductions are correct.

2. What is the worst-case time complexity of your chosen reduction? You may use LP to represent the time required to solve LONG-PATH and LC to represent the time required to solve LONG-CYCLE.

3. Use your answer to the previous question and the assumptions that LONG-CYCLE NP-Hard and LONG-PATH NP to prove LONG-PATH NP-Complete.

Input: G V, E graph with n vertices and m edges Input n, m order and size of G Input v: vertex of G Input: k: cycle length Output LONG-CYCLE(G, v, k): whether v is part of a cycle of length k or greater in G 1 Algorithm: ReductionOne 2 for u EN(v) do 3 G.Remove Edge(u, v) 4 if LONG-PATH (G, u, v, k -1) then return true; end 7 G.Add Edge (u, v) 8 end 9 return false