Cómo probar NP-integridad de la ruta más larga entre dos vértices que confían en Hamilton NP-DURO problema

Question

Tengo esta pregunta: Tengo un gráfico GRÁFICO G (V, E) (donde v= conjunto de vértices, E= conjunto de bordes).Considere la ruta máxima entre dos vértices S y T:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

Un camino simple es un camino sin ningún vértice repetido, es decir, cada vértice se puede visitar solo una vez.La longitud de la ruta se administra desde los bordes de los cuales está compuesto.

Entonces, ¿cómo puedo mostrar que LPATH es un problema de NP-completo utilizando el problema de la ruta de Hamilton como un problema de NP-DURS como referencia?

Answer 1

¡Bienvenido al sitio! Deje que $ g= (v, e) $ sea un gráfico no dirigido. Si $ g $ es hamiltoniano, entonces existe un ciclo simple $ c $ en $ g $ que contiene cada vértice, es decir, la longitud de $ c $ es $ | V | $ . Tenga en cuenta que si elimina cualquier borde $ vw $ de $ C $ , terminas con un camino de longitud $ | v | - 1 $ entre $ v $ y $ w $ . A la inversa, si encuentra un camino simple $ p $ de longitud $ | - 1 $ entre dos vértices $ V, w $ conectado por un borde, puede agregar el borde $ VW $ a $ p $ para obtener un ciclo hamiltoniano (como $ p $ no puede contener $ VW $ debido a ser un camino simple). También observe que la elección de $ v $ y $ w $ es arbitrario siempre que estén conectados por un borde.

para que podamos obtener la siguiente reducción: A partir de algunos gráficos $ g= (v, e) $ , elija un poco de borde $ vw \ in e $ y elimínelo para obtener un nuevo gráfico $ g '= (v, e \ setminus \ {vw \}) $ . Usando las observaciones que hicimos, se deduce que $ g '$ tiene una ruta $ p $ entre $ v $ y $ w $ de longitud $ | - 1 $ Si y solo si agrega $ vw $ a $ p $ produce un hamiltoniano Ciclo en el gráfico original $ g $ . Como $ g '$ se puede calcular desde $ g $ en tiempo polinomial, tenemos una reducción polinomial < Span Class="Math-contenedor"> $ \ mathrm {ciclo hamiltoniano} \ leq_ \ mathsf {p} \ mathrm {largo camino} $ , mostrando así su problema es $ \ mathsf {np} $ -hard (porque $ \ mathrm {ciclo hamiltoniano} $ es $ \ mathsf {np} $ -hard ya).

para mostrar que $ \ mathrm {largo camino} $ está en $ \ mathsf {np} $ Notamos que una ruta en un gráfico se puede codificar de manera eficiente como una lista de sus bordes y verificar que una cadena realmente codifica una ruta en el gráfico y luego contando el número de bordes para determinar si se puede hacer lo suficiente en polinomio. tiempo.

Por lo tanto, encontramos que $ \ mathrm {largo camino} $ es $ \ mathsf {np} $ -Complete.