Corrigé CCINP 2026 Informatique MPI — Partie I (I.1 à I.3) (Q1 à Q11) : Voyageur de commerce : NP-complétude par réductions

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

$G = (S, A)$ est un graphe non orienté, $n = ∣ S ∣$ ; muni d'un coût $c : S \times S \to N$ ( $+ \infty$ hors arête), on note $G = (S, A, c)$ . Un cycle hamiltonien passe une fois par chaque sommet et revient au départ. Problèmes de décision : cycle-hamiltonien (CH) : $G$ a-t-il un cycle hamiltonien ? couverture-sommet (CS) : pour $G$ et $m \in N$ , existe-t-il $S_{c} \subseteq S$ , $∣ S_{c} ∣ ⩽ m$ , touchant chaque arête ? tsp : pour $G = (S, A, c)$ et $k \in N$ , existe-t-il un cycle hamiltonien de coût $⩽ k$ ? On admet que CS est NP-complet.

Q1. Montrer que tsp est dans NP.

I.1. De CH vers tsp : à $G$ on associe $G^{'}$ complet sur $S$ , une arête coûtant $1$ si elle est dans $A$ et $2$ sinon, et le seuil $k = ∣ S ∣$ .
Q2. Montrer que CH est dans NP.
Q3. La construction de $G^{'}$ est polynomiale en la taille de $G$ .
Q4. Si $G$ est une instance positive de CH, $(G^{'}, k)$ en est une de tsp.
Q5. Réciproque.

I.2. De CS vers CH : à $(G, m)$ , $m ⩽ ∣ S ∣$ , on associe $G^{'}$ ayant un cycle hamiltonien si et seulement si $G$ a une couverture de taille au plus $m$ (équivalence admise). Pour Q6 à Q9, $G$ est :

Q6. CS répond-il Vrai pour $m = 2$ ? $m = 3$ ? Donner $S_{c}$ le cas échéant.

Construction de $G^{'}$ : (i) $m$ sommets $a_{1}, \dots, a_{m}$ ; (ii) pour $e = (s, t) \in A$ , un gadget $G_{e}$ de sommets $s_{i} (e), t_{i} (e)$ , $i \in [[1, 6]]$ , et de $14$ arêtes : les chaînes $s_{i} (e) s_{i + 1} (e)$ et $t_{i} (e) t_{i + 1} (e)$ ( $i ⩽ 5$ ), plus $s_{3} (e) t_{1} (e)$ , $t_{3} (e) s_{1} (e)$ , $s_{6} (e) t_{4} (e)$ , $t_{6} (e) s_{4} (e)$ ; (iii) pour $e_{s [1]}, \dots, e_{s [d (s)]}$ les arêtes incidentes à $s$ , $A_{s} = {{s_{6} (e_{s [j]}), s_{1} (e_{s [j + 1]})}, j \in [[1, d (s) - 1]]}$ ; (iv) les arêtes ${a_{i}, s_{1} (e_{s [1]})}$ et ${a_{i}, s_{6} (e_{s [d (s)]})}$ pour tous $i$ et $s$ . Seuls $s_{1}, t_{1}, s_{6}, t_{6}$ ont des voisins hors de $G_{e}$ .

Q7. Dessiner le gadget de $e_{2} = (β, δ)$ , $β_{i} (e_{2})$ au-dessus de $δ_{i} (e_{2})$ .
Q8. Donner les trois traversées possibles de $G_{e}$ par un cycle hamiltonien de $G^{'}$ .
Q9. Donner $A_{γ}$ et $A_{δ}$ .
Q10. $G^{'}$ se construit en temps polynomial à partir de $G$ et $m$ .
Q11. En déduire que tsp est NP-complet.

Corrigé

On rappelle la définition du cours : un problème de décision est dans NP si toute instance positive admet un certificat de taille polynomiale en celle de l'instance, vérifiable en temps polynomial. On suppose $n ⩾ 3$ , pour qu'un cycle hamiltonien ait exactement $n$ arêtes distinctes.

Q1. Certificat : la liste $(v_{1}, \dots, v_{n})$ des sommets dans l'ordre du cycle, de taille $O (n lo g n)$ bits, polynomiale en la taille de l'instance $(G, k)$ , qui contient au moins les $n$ sommets. Vérification : (a) la liste a $n$ éléments et chaque sommet y figure une fois (un tableau de booléens indexé par les sommets, $O (n)$ ) ; (b) pour $1 ⩽ i ⩽ n$ , ${v_{i}, v_{i + 1}}$ (avec $v_{n + 1} = v_{1}$ ) est une arête, c'est-à-dire $c (v_{i}, v_{i + 1}) < + \infty$ ; (c) $\sum_{i = 1}^{n} c (v_{i}, v_{i + 1}) ⩽ k$ . Ce sont $n$ lectures de coûts et $n$ additions d'entiers de la taille de l'entrée : temps polynomial. Le vérificateur accepte si et seulement si la liste est un cycle hamiltonien de coût au plus $k$ : une instance est positive si et seulement s'il existe un certificat accepté. Donc $t s p \in NP$ .

Q2. Même certificat (l'ordre des sommets), mêmes vérifications (a) et (b), sans la somme : $O (n)$ tests d'appartenance d'une arête ( $O (1)$ chacun en matrice d'adjacence, $O (n)$ en listes), donc temps polynomial. CH est dans NP.

Q3. $G^{'}$ a $n$ sommets et $\frac{n ( n - 1 )}{2}$ arêtes ; pour chacune on teste si ${s, t} \in A$ . En représentant $G$ par une matrice d'adjacence (construite en $O (n^{2})$ au besoin à partir de listes d'adjacence), chaque test coûte $O (1)$ ; les coûts $1$ ou $2$ sont de taille constante et le seuil $k = n$ s'écrit sur $O (lo g n)$ bits. Total : $O (n^{2})$ , polynomial en la taille de $G$ (qui est au moins $n$ ). Ce que le correcteur attend : $G^{'}$ est complet, donc on paie $n^{2}$ et non $n + ∣ A ∣$ .

Q4. Soit $H$ un cycle hamiltonien de $G$ . Ses $n$ arêtes sont dans $A$ , donc coûtent $1$ dans $G^{'}$ ; comme $S^{'} = S$ , $H$ est un cycle hamiltonien de $G^{'}$ , de coût $n = k$ . Donc $(G^{'}, k)$ est une instance positive de tsp.

Q5. Soit $H^{'}$ un cycle hamiltonien de $G^{'}$ de coût $⩽ k = n$ . Il a $n$ arêtes, chacune de coût $⩾ 1$ : son coût est $⩾ n$ , donc égal à $n$ , et chaque arête coûte exactement $1$ , c'est-à-dire appartient à $A$ . $H^{'}$ est donc un cycle hamiltonien de $G$ , et CH répond Vrai sur $G$ . Avec Q3 et Q4, $G \mapsto (G^{'}, ∣ S ∣)$ est une réduction polynomiale : $CH ⩽_{p} t s p$ .

Q6. Les arêtes $e_{1}, e_{2}, e_{3}, e_{4}$ relient $δ$ à quatre sommets distincts $α, β, γ, ϵ$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →