Exemple

Montrons que le problème $HC$ (cycle hamiltonien) est moins difficile que $TSP$ (voyageur de commerce). Pour cela, construisons une fonction $f$ prenant en paramètre une instance du problème $HC$, et créant une instance $I$ du problème $TSP$. Il est très important de déterminer $f$ de sorte que $I$ soit à réponse oui si et seulement si $f(I)$ est à réponse oui. Rappelons la définition de $HC$ dans un graphe non orienté :

• Données : un graphe $G$ non orienté
• Question : existe-t-il un cycle hamiltonien dans $G$ ?

Ainsi que la définition de $TSP$,

• Données : un graphe $G^\prime$ non orienté muni d'une valuation $c$, une constante $K$
• Question : existe-t-il dans un $G$ un cycle hamiltonien de longueur inférieure ou égale à $K$ ?

Nous définissons $f$ de la sorte, $f$ prend en paramètre les données de $HC$, à savoir le graphe $G = (S, A)$, on définit l'instance $f(I)$ de la sorte

• $G^\prime = (S, A^\prime)$, $A^\prime$ contient toutes les paires de sommets qu'il est possible de former avec les sommets de $G$. Autrement dit, $G^\prime$ est un graphe complet.
• $c(e) = 1$ si $e \in A$, $c(e) = 2$ si $e \not \in A$. Autrement dit, les arêtes de $A^\prime$ ont la valeur $1$ si elle se trouvaient dans $A$, et toutes les arêtes qui ont été ajoutées pour obtenir un graphe complet ont la valeur $2$.
• $K = \vert S\vert$.

Il est maintenant nécessaire de montrer que $I$ est une instance à réponse oui si et seulement si $f(I)$ est une instance à réponse oui.

• Soit $I$ une instance de $HC$ à réponse oui. Alors il existe un cycle hamiltonien dans $G$. La longueur de ce cycle dans $G$ est $\vert S\vert$, à savoir le nombre de sommets. La longueur de ce cycle est aussi $\vert S\vert$ dans $G^\prime$, car les arêtes empruntées dans $G^\prime$ étaient toutes de valuation $1$.
• Soit $I$ une instance de $HC$ telle que $f(I)$ est à réponse oui. Comme $f(I)$ est à réponse oui, alors il existe un cycle hamiltonien de longueur $K = \vert S\vert$. Comme ce cycle passe par $\vert S\vert$ arêtes, et que toutes les arêtes de $G^\prime$ sont de valuation $1$ ou $2$, alors ce cycle n'emprunte que des arêtes de valuation $1$. Comme les arêtes de valuation $1$ de $G^\prime$ sont aussi des arêtes de $G$, alors il existe un cycle hamiltonien dans $G$.