NP-complétude de HAM-PATH
Léo Gayral
2017-2018
ref : Carton – Langages formels, Calculabilité et complexité – p.207
Lemme 1. On considère HAM-PATH le problème de la recherche d’un che-
min hamiltonien – passant une seule fois par chaque sommet – au sein d’un
graphe orienté. Ce problème est dans NP.
Démonstration.
Pour ce problème, un vérificateur convenable est un chemin w sur le graphe
G = (S, A), un mot de S ∗ . En effet, on peut en temps polynômial par rapport
à |G| vérifier qu’un tel chemin contient une unique fois chaque sommet de S
et que chaque transition du chemin correspond bien à une arrête de A.
Théorème 1. On a une réduction polynômiale de SAT sous FNC vers HAM-
PATH.
Démonstration. n m
Wi
ti,j et ti,j ∈
V
On considère la formule F = Ci , avec les clauses Ci =
i=0 j=1
{x0 , ¬x0 , . . . , xr , ¬xr } des termes.
On peut faire un prétraitement de F , en éliminant les clauses qui seront
toujours vérifiées parce qu’elles contiennent x et ¬x pour une certaine variable
x, et en éliminant les doublons dans les clauses restantes. On peut donc
supposer par la suite que chaque variable apparaît au plus une seule fois
dans chaque clause.
On associe le gadget suivant à chaque variable xk :
1
k
k, 0 k, 1 [· · · ] k, 2n k, 2n + 1
k+1
On considère alors le graphe G = (S, A) formé par l’union des gadgets
associés à chacune des variables xk de F , des sommets Ci , et des arrêtes
suivantes :
— Si xk est un terme de Ci , alors (k, 2i) → Ci , Ci → (k, 2i + 1) ∈ A,
— Si ¬xk est un terme de Ci , alors (k, 2i + 1) → Ci , Ci → (k, 2i) ∈ A.
Considérons un chemin hamiltonien au sein de ce graphe. Il part néces-
sairement de 0 qui n’a pas de prédécesseur, et termine nécessairement sur
k + 1 qui n’a pas de successeur. Par construction de G, ce chemin ne peut
pas changer de gadget lors du passage sur un sommet Ci . En effet, si c’était
le cas – disons par exemple qu’on a les transitions (k, 2i) → Ci → (l, 2i) –
alors lorsque le chemin passe en (k, 2i + 1), son seul successeur possible est
(k, 2i) – en raison du prétraitement de F – qui est déjà visité à un autre
moment.
Si on excepte les éventuels détours ponctuels sur un Ci , le chemin consi-
déré parcourt chaque gadget d’une seule traite, l’un après l’autre. Le sens de
parcours du gadget de xk , ou de façon équivalente le choix du successeur au
sommet k, permet alors de définir une valuation pour xk . Si un gadget est
parcouru de gauche à droite, on pose ν (xk ) = 1. Si il est parcouru de droite
à gauche, on pose ν (xk ) = 0.
Supposons que le chemin faut un crochet par Ci en parcourant le gadget de
xk de gauche à droite. D’une part, ν (xk ) = 1. D’autre part, par construction
du graphe, on a les transitions (k, 2i) → Ci → (k, 2i + 1), ce qui signifie que
xk est un terme de Ci par construction de G, donc ν (Ci ) = 1. On en déduit
que tout chemin hamiltonien induit ν telle que ν(F ) = 1.
2
Réciproquement, toute valuation ν telle que ν(F ) = 1 induit des chemins
hamiltoniens. On n’a pas de choix naturel dans ce sens car lorsque plusieurs
termes d’une clause sont vérifiés, il faut choisir un seul des gadgets associés au
sein duquel le chemin hamiltonien fera un crochet par la clause en question.
Autrement dit, l’existence d’un chemin hamiltonien dans G est équiva-
lente à la satisfiabilité de F . On a bien réduit SAT à HAM-PATH. Cette ré-
duction est bien polynômiale car G a (r+2)+2(r+1)(n+1)+(n+1) = O (|F |2 )
sommets, et de même pour les arrêtes.