Every young wizard learns the classic NP-complete problem of determining whether some unweighted, undirected graph G = (V, E) contains a simple path of length at least k (where both G and k are part of the input to the problem), known as the Longest Path Problem. Recall that a simple path is a path (v1, v2, . . . , vl) where each (vi,vi+1) in the path is an edge, and all the vi are distinct; its length is l?1 (=the number of edges in the path). The following figure illustrates a graph and a Hamiltonian cycle on it (see Chapter 35.5.3 in CLRS for a proof of NP-completeness).

(b) For the final exam in Ginnys class, each student must visit the Oracles Well in the Forbidden Forest. For every bronze Knut a young wizard tosses into the Well, the Oracle will give a yes or no response as to whether, given an arbitrary graph G and an integer k, G contains a simple path of length ? k. Ginny is given an arbitrary graph G and must find the longest simple path in G.

First, she realizes it would be useful to determine the length of the longest simple path. Describe an algorithm that will allow Ginny to use the Oracle to find the length of the longest simple path in G by asking it a series of questions, each in- volving a modified version of the original graph G and a number k. Her solution must not cost more Knuts than a number that grows polynomially as a function of the number of vertices in G. (Hence, prove that if we can solve the Longest Path decision problem in polynomial time, we can solve its optimization problem as well.)