Comment prouver NP-Complétude du chemin le plus long entre deux sommets qui s'appliquent à un problème de Hamilton NP-dur

Question

J'ai cette question: j'ai un graphique non dirigé g (v, e) (où v= ensemble de sommets, e= ensemble d'arêtes).Considérons le chemin maximum entre deux sommets S et T:

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

Un chemin simple est un chemin sans vertice répétée, c'est-à-dire que chaque vertice peut être visité juste une fois.La longueur du chemin est donnée des bords dont il est composé.

Alors, comment puis-je montrer que LPATH est un problème NP-complet à l'aide du problème de chemin Hamilton en tant que problème de NP-dur comme référence?

Answer 1

Bienvenue sur le site! Laissez $ g= (v, e) $ être un graphique non dirigé. Si $ G $ est hamiltonien, il existe alors un cycle simple $ C $ in $ G $ contenant chaque sommet, c'est-à-dire la longueur de $ C $ est $ | $ | V | $ . Notez que si vous supprimez tout bord $ VW $ de $ C $ , vous vous retrouvez avec un chemin de Longueur $ | V | - 1 $ entre $ V $ et $ w $ . Inversement, si vous trouvez un chemin simple $ p $ de longueur $ | v | - 1 $ entre deux sommets $ v, w $ connecté par un bord, vous pouvez ajouter le bord $ VW $ à $ p $ pour obtenir un cycle hamiltonien (comme $ p $ ne peut pas contenir $ VW $ en raison d'être un chemin simple). Observez également que le choix de $ V $ et $ w $ est arbitraire tant qu'ils sont connectés par un bord.

Nous pouvons donc obtenir la réduction suivante: À partir d'un graphique $ g= (v, e) $ , choisissez un bord $ vw \ in e $ et supprimez-le pour obtenir un nouveau graphique $ g '= (v, e \ seminus \ {vw \}) $ . Utilisation des observations que nous avons fabriquées, il suit que $ g '$ a un chemin $ p $ entre $ v $ et $ w $ de longueur $ | v | - 1 $ si et seulement si ajouter $ vw $ to $ p $ donne un hamiltonien Cycle dans le graphique d'origine $ g $ . Comme $ g '$ peut être calculé à partir de $ g $ en temps polynomial, nous avons une réduction polynomiale < SPAN CLASS="MATH-CONTAINER"> $ \ MATHRM {HAMILTONIAN CYCLE} \ LEQ_ \ MATHSF {P} \ MATHRM {PATH LONG PATH} $ , montrant ainsi que votre problème est $ \ mathsf {np} $ -hard (parce que $ \ mathrm {cycle hamiltonien} $ est $ \ mathsf {np} $ -hard déjà).

montrer que $ \ mathrm {path long} $ est dans $ \ mathsf {np} $ Nous notons qu'un chemin dans un graphique peut être codé efficacement sous forme de liste de ses bords et de vérifier qu'une chaîne code en fait un chemin dans le graphique, puis en comptant le nombre d'arêtes pour déterminer s'il est suffisamment long en polynôme. temps.

Nous trouvons donc que $ \ mathrm {chemin long} $ est $ \ mathsf {np} $ -Compléte.