Hamiltonian Path (HAM)

Problème de trouver un chemin passant par tous les sommets exactement une fois.

Définition

Un chemin hamiltonien dans $G=(V,E)$ est un chemin qui visite chaque sommet exactement une fois.

Problème de décision

• Instance : Graphe $G=(V,E)$
• Question : $G$ possède-t-il un chemin hamiltonien ?

Complexité

HAM est NP-complet.

Certificat

• Certificat de verification : Permutation $P$ de $V$
• Vérification :

Pour i = 2 à n:
	si P[i-1]P[i] ∉ E alors retourner faux
retourner vrai

• Complexité de vérification : $O(n)$

Variante : Cycle Hamiltonien (HC)

HAM ${\ll }_P$​ HC

Transformation :

$G=(V,E)\to G^{\prime }=(V\cup \{z\},E\cup \{zv\mid v\in V\})$

$G^{\prime }$ est le graphe $G$ avec un sommet universel $z$ connecté à tous les sommets.

Preuve :

• Si $G$ a un chemin hamiltonien, alors $G^{\prime }$ a un cycle hamiltonien (passer par $z$ pour fermer le cycle)
• Si $G^{\prime }$ a un cycle hamiltonien, retirer $z$ donne un chemin hamiltonien dans $G$

Application : Minimum Leaf Spanning Tree (MLST)

HAM ${\ll }_P$ MLST

Transformation : $⟨G=(V,E)⟩\to ⟨G^{\prime }=(V,E),k=2⟩$

Un arbre couvrant avec 2 feuilles est exactement un chemin hamiltonien.

Donc MLST est NP-difficile (même pour $k=2$ fixé).

Self-réductibilité

HAM est self-réductible : on peut retirer progressivement les arêtes tout en vérifiant l’existence d’un chemin hamiltonien.