Come dimostrare NP-Completezza del percorso più lungo tra due vertici che si affidano a Hamilton NP-Hard problema

Question

Ho questa domanda: Ho un grafico non irritato G (V, E) (dove V= Set di vertici, E= Set di bordi).Considera il percorso massimo tra due vertici S e T:

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

.

Un percorso semplice è un percorso senza alcun vertice ripetuto, cioè ogni vertice può essere visitata solo una volta.La lunghezza del percorso è data dai bordi di cui è composto.

Allora, come posso dimostrare che LPRAX è un problema completo di NP usando il problema del percorso Hamilton come un problema NP-HARD come riferimento?

Answer 1

Benvenuti nel sito! Let $ G= (v, e) $ Sii un grafico non rilevato. Se $ G $ è hamiltoniano, quindi esiste un semplice ciclo $ c $ in $ G $ contenente ogni vertice, ovvero la lunghezza della $ c $ è $ | V | $ . Si noti che se si elimina qualsiasi Edge $ VW $ da $ c $ , finisci con un percorso di Lunghezza $ | V | - 1 $ tra $ V $ e $ W $ . Viceversa, se trovi un semplice percorso $ p $ di lunghezza $ | V | - 1 $ tra due vertici $ V, W $ collegato da un bordo, è possibile aggiungere il bordo $ VW $ a $ P $ per ottenere un ciclo hamiltoniano (come $ p $ non può contenere $ VW $ a causa di essere un percorso semplice). Osservare anche che la scelta di $ V $ e $ W $ è arbitrario finché sono collegati da un bordo.

Quindi possiamo ottenere la seguente riduzione: A partire da un grafico $ g= (v, e) $ , scegli del bordo $ vw \ in e $ ed eliminarlo per ottenere un nuovo grafico $ g '= (v, e \ setminus \ {vw \}) $ . Utilizzando le osservazioni che abbiamo realizzato, segue che $ G '$ ha un percorso $ p $ tra $ V $ e $ W $ di lunghezza $ | V | - 1 $ se e solo se aggiungendo $ VW $ a $ P $ produce un hamiltoniano Ciclo nel grafico originale $ G $ . Come $ G '$ può essere calcolato da $ G $ in tempo polinomiale, abbiamo una riduzione polinomiale < Span Class="Math-Container"> $ \ Mathrm {hamiltonian ciclo} \ leq_ \ mathsf {p} \ mathrm {long path} $ , mostrando così che il tuo problema è $ \ mathsf {np} $ -Hard (perché $ \ mathrm {hamiltonian ciclo} $ è $ \ mathsf {np} $ -Hard GIÀ).

per mostrare che $ \ mathrm {long percorso} $ è in $ \ mathsf {np} $ Nota che un percorso in un grafico può essere codificato in modo efficiente come un elenco dei suoi bordi e controllare che una stringa in realtà codifica un percorso nel grafico e quindi contando il numero di bordi per determinare se è abbastanza lungo può essere fatto in polinomio tempo.

Quindi troviamo che $ \ mathrm {long percorso} $ è $ \ mathsf {np} $ -Complete.