Define the optimization problem LONGEST-PATH-LENGTH as the relation thatassociates each instance of an undirected graph and two vertices with the num-ber of edges in a longest simple path between the two vertices. Define the de-cision problem LONGEST-PATH D fhG; u; ; ki W G D .V; E/ is an undi-rected graph, u;  2 V , k  0 is an integer, and there exists a simple pathfrom u to  in G consisting of at least k edgesg. Show that the optimization prob-lem LONGEST-PATH-LENGTH can be solved in polynomial time if and only ifLONGEST-PATH 2 P.

Para demostrar que el problema de optimización LONGEST-PATH-LENGTH puede resolverse en tiempo polinómico si y solo si LONGEST-PATH pertenece a P, sigamos los siguientes pasos:

1. Definiciones:

   • Problema de optimización LONGEST-PATH-LENGTH: Dado un grafo no dirigido $G = (V, E)$ y dos vértices $u, v \in V$, encontrar el número de aristas en el camino simple más largo entre $u$ y $v$.
   • Problema de decisión LONGEST-PATH: Dado un grafo no dirigido $G = (V, E)$, dos vértices $u, v \in V$ y un entero $k \geq 0$, determinar si existe un camino simple desde $u$ hasta $v$ en $G$ que consista en al menos $k$ aristas.

2. Demostración de que LONGEST-PATH-LENGTH puede resolverse en tiempo polinómico si LONGEST-PATH pertenece a P:

   • Supongamos que LONGEST-PATH pertenece a P, es decir, existe un algoritmo que puede decidir si hay un camino simple de al menos $k$ aristas entre $u$ y $v$ en tiempo polinómico.
   • Para resolver LONGEST-PATH-LENGTH, podemos usar una búsqueda binaria sobre el valor de $k$. El rango de $k$ va desde 0 hasta $|V| - 1$ (el número máximo de aristas en un camino simple en un grafo con $|V|$ vértices).
   • En cada paso de la búsqueda binaria, usamos el algoritmo de decisión de LONGEST-PATH para verificar si existe un camino simple de longitud al menos $k$.
   • La búsqueda binaria requiere $O(\log |V|)$ consultas al algoritmo de decisión, y cada consulta se resuelve en tiempo polinómico. Por lo tanto, el problema de optimización LONGEST-PATH-LENGTH se puede resolver en tiempo polinómico.

3. Demostración de que LONGEST-PATH pertenece a P si LONGEST-PATH-LENGTH puede resolverse en tiempo polinómico:

   • Supongamos que existe un algoritmo que resuelve LONGEST-PATH-LENGTH en tiempo polinómico.
   • Para resolver LONGEST-PATH, dado un grafo $G$, dos vértices $u$ y $v$, y un entero $k$, simplemente ejecutamos el algoritmo de LONGEST-PATH-LENGTH para encontrar la longitud del camino simple más largo entre $u$ y $v$.
   • Si la longitud del camino más largo es al menos $k$, entonces la respuesta a LONGEST-PATH es "sí". De lo contrario, la respuesta es "no".
   • Dado que el algoritmo de LONGEST-PATH-LENGTH se ejecuta en tiempo polinómico, esto implica que LONGEST-PATH también se puede resolver en tiempo polinómico.

Por lo tanto, hemos demostrado que el problema de optimización LONGEST-PATH-LENGTH puede resolverse en tiempo polinómico si y solo si LONGEST-PATH pertenece a P.