NP-complétude du Cycle Hamiltonien et Extensions avec Contraintes
Définitions de Base
Cycle Hamiltonien (CH): Étant donné un graphe G = (V, E), existe-t-il un cycle passant par chaque sommet exactement une fois et revenant au point de départ ?
3‑SAT: Problème consistant à vérifier si une formule booléenne sous forme normale conjonctive avec trois littéraux par clause est satisfaisable.
1. Preuve de NP‑complétude du Cycle Hamiltonien (sans contraintes)
Étape 1 : CH ∈ NP
Un certificat est un cycle passant par tous les sommets. La vérification consiste à s'assurer que chaque sommet apparaît exactement une fois et que le cycle est fermé. Ceci peut être effectué en temps polynomial.
Étape 2 : NP‑difficulté par réduction de 3‑SAT
Soit φ une instance de 3‑SAT composée de n variables et m clauses.
Objectif : Construire un graphe G(φ) tel que φ est satisfaisable si et seulement si G(φ) possède un cycle Hamiltonien.
Construction :
Gadget variable : Pour chaque variable x, on crée une structure dont le cycle peut être parcouru de deux manières distinctes. L'une correspond à l'affectation x = vrai, l'autre à x = faux.
Gadget clause : Pour chaque clause (l₁ ∨ l₂ ∨ l₃), on crée un gadget qui est connecté aux gadgets de variables associés aux littéraux l₁, l₂ et l₃. Ces connexions sont telles que le cycle complet n'existe que si au moins l'un des littéraux satisfait la clause.
Enfin, les gadgets sont reliés entre eux de façon à forcer le passage par chaque gadget variable et clause exactement une fois.
Réduction de 3-SAT vers Cycle Hamiltonien
La construction assure que si φ est satisfaisable, alors il existe un chemin qui, en choisissant la branche correspondant à l'affectation vraie ou fausse pour chaque variable, permettra de couvrir tous les gadgets et ainsi former un cycle Hamiltonien. Inversement, l'existence d'un cycle Hamiltonien induit une affectation vérifiant φ.
Cette réduction est effectuée en temps polynomial par rapport à la taille de φ.
Conclusion :
Le Cycle Hamiltonien est NP‑complet puisque (i) il est dans NP et (ii) tout problème de 3‑SAT se réduit en temps polynomial au CH.
2. Extension aux Contraintes Supplémentaires
2.1 Cycle Hamiltonien Pondéré (CHP)
Définition: Donné G = (V, E) muni d'une fonction de poids w : E → ℝ⁺, existe-t-il un cycle hamiltonien de poids minimal ?
CHP ∈ NP : Pour un certificat (le cycle), on vérifie en temps polynomial que la somme des poids est conforme au critère d'optimalité ou simplement que le cycle existe.
Réduction : La réduction est directe : en affectant w(e) = 1 pour chaque arête, le problème devient équivalent au Cycle Hamiltonien classique. Ainsi, CH se réduit en temps polynomial à CHP.
CHP: Cycle hamiltonien de poids total 20
2.2 Cycle Hamiltonien avec Contrainte d'Autonomie (CHA)
Définition : Pour un graphe G = (V, E) muni d'un sous-ensemble R ⊆ V représentant des stations de recharge et une autonomie k ∈ ℕ, on exige que tout chemin continu de plus de k arêtes contienne au moins un sommet dans R.
CHA ∈ NP : Un certificat (le cycle) peut être vérifié en temps polynomial en contrôlant l'ordre de passage des sommets et la présence régulière d'un sommet de recharge.
Réduction : La réduction se fait en partant du Cycle Hamiltonien classique. On affecte :
Soit R = V (c'est-à-dire, tous les sommets sont des stations), ou
fixez k ≥ |V| afin que la contrainte d'autonomie soit triviale.
Ainsi, toute instance de CH se réduit immédiatement à une instance de CHA. Par conséquent, CHA est NP‑difficile.
CHA: autonomie k=2, cycle valide A→B→C→F→E→D→A
2.3 Combinaison : Cycle Hamiltonien avec Pondération et Contrainte d'Autonomie (CHPA)
Pour un problème combiné, les arguments précédents se recoupent :
En fixant les poids à 1, on retrouve le cas CHA, déjà NP‑complet.
La vérification d'un certificat et la construction de la réduction se font en temps polynomial.
Ainsi, CHPA est NP‑complet.
CHPA: Cycle valide avec poids minimal et respect de l'autonomie k=2
3. Remarques et Applications
3.1 Planification d'itinéraires pour véhicules électriques
• Les sommets représentent des villes à visiter
• Les poids sont les distances ou coûts de trajet
• Les stations de recharge sont un sous-ensemble des villes
• L'autonomie correspond à la distance maximale entre recharges
3.2 Approches de résolution
Méthodes exactes:
• Programmation par contraintes
• Branch-and-cut avec solveurs PLNE
Heuristiques:
• Algorithmes génétiques avec pénalités pour violations d'autonomie
• Recherche locale avec contraintes (2-opt modifié)
• Optimisation par colonies de fourmis avec phéromones guidant vers les stations
Application à la planification d'itinéraire pour véhicule électrique