DM Complexité : 1_3_SAT, VECSUBSETSUM, WEIGHTEDPATH

DM de Complexité

Énoncé

http://younesse.net/Calculabilite/DM_Complexite/

Younesse Kaddar

EX 1

Q1

\[Prop = \lbrace p \rbrace\]

\[𝜓 ≝ p ∨ p ∨ p\]

est positive pour $\textsf{3_SAT}$ (avec $v(p) = True$), et négative pour $\textsf{UNIQ_SAT}$ (les valuations $p \mapsto True$ et $p \mapsto False$ ne valident pas “un et un seul littéral” dans la clause).

Q2

$\textsf{UNIQ_SAT}$ est dans $\textsf{NP}$

La machine de Turing non déterministe devine une valuation $v : Prop ⟶ Bool$ en temps linéaire, et n’accepte que si un et un seul littéral dans chaque clause est validé par $v$, rejette sinon : cela prend un temps linéaire, donc polynomial.

Algorithme que suit la machine non déterministe :

ValideUniqSAT(v, 𝜓) :
  Si 𝜓 est de la forme :
    C_1 ∧ ⋯ ∧ C_n :
        retourne ValideUniqSAT(v, C_1) ∧ ⋯ ∧ ValideUniqSAT(v, C_n)
    a ∨ b ∨ c :
        Si v(a) ∧ ¬v(b) ∧ ¬v(c)  OU  v(b) ∧ ¬v(a) ∧ ¬v(c)  OU  v(c) ∧ ¬v(b) ∧ ¬v(a) :
            retourne Vrai
        Sinon :
            retourne Faux

Devine une valuation v
Si ValideUniqSAT(v, 𝜓) :
    Accepte
Sinon :
    Rejette

$\textsf{UNIQ_SAT}$ est $\textsf{NP}$-difficile

Il suffit de réduire $\textsf{3_SAT}$ à $\textsf{UNIQ_SAT}$, puisque $\textsf{3_SAT}$ est $\textsf{NP}$-difficile.

Montrons que \(\textsf{3_SAT} ≼_{\textsf{LOGSPACE}} \textsf{UNIQ_SAT}\)

Soit $𝜓 ≝ C_1 ∧ ⋯ ∧ Cm$ une instance de $\textsf{3_SAT}$, c’est-à-dire une formule propositionnelle sous forme normale conjonctive, où

• chaque clause $C_i$ est de la forme $l_{i,1} ∨ l_{i,2} ∨ l_{i,3}$

• chaque $l_{i,j}$ est de la forme \(\underbrace{𝜀_{i,j}}_{∈\lbrace +, -\rbrace} p_{i,j}\)

  • où $p_{i,j}$ est une variable propositionnelle : $p_{i,j} ∈ Prop$

Montrons qu’il existe une fonction calculable $r: \textsf{3_SAT} ⟶ \textsf{UNIQ_SAT}$ telle que :

• il existe une valuation qui valide $𝜓$ si, et seulement si il existe une valuation qui valide un et un seul littéral dans chaque clause de $r(𝜓)$
• la réduction $r$ est en $\textsf{LOGSPACE}$

En effet :

À toute clause $C_i ≝ l_{i,1} ∨ l_{i,2} ∨ l_{i,3}$, on associe trois clauses

\[\underbrace{-l_{i,1} ∨ x_i ∨ y_i}_{≝ \, C_{i,1}} \, ∧ \, \underbrace{y_i ∨ l_{i,2} ∨ z_i}_{≝ \, C_{i,2}} \, ∧ \, \underbrace{z_i ∨ t_i ∨ -l_{i,3}}_{≝ \, C_{i,3}}\]

où $x_i, y_i, z_i, t_i$ sont de nouvelles variables propositionnelles.

Pour toute valuation $v: Prop ⟶ Bool$, il vient que :

• Si $v$ valide $C_i$ :

  • Cas 1 : Si $v(l_{i,2})=True$ : on peut choisir

    \[\begin{cases} v(y_i) = v(z_i) = False \\ v(x_i) = v(l_{i,1}) \\ v(t_i) = v(l_{i,3}) \end{cases}\]

  • Cas 2 : Sinon si $v(l_{i,1})= v(l_{i,3}) = True$ : on peut choisir

    \[\begin{cases} v(x_i) = v(l_{i,1}) = True \\ v(y_i) = False \\ v(z_i) = True \\ v(t_i) = v(-l_{i,3}) = False \\ \end{cases}\]

  • Cas 3 : Sinon si $v(l_{i,1}) = True, v(l_{i,3}) = False$ : on peut choisir

    \[\begin{cases} v(x_i) = v(l_{i,1}) = True \\ v(y_i) = False \\ v(z_i) = True \\ v(t_i) = v(l_{i,3}) = False \\ \end{cases}\]

  • Cas 4 : Sinon si $v(l_{i,1}) = False, v(l_{i,3}) = True$ (cas symétrique au précédent) : on peut choisir

    \[\begin{cases} v(x_i) = v(l_{i,1}) = False \\ v(y_i) = True \\ v(z_i) = False \\ v(t_i) = v(l_{i,3}) = True \\ \end{cases}\]

    dans tous les cas : on vérifie aisément que $v$ valide un et un seul littéral dans $C_{i,1}, C_{i,2}$ et $C_{i,3}$.

• Réciproquement, si $v$ valide un et un seul littéral dans $C_{i,1}, C_{i,2}$ et $C_{i,3}$ :

  • Cas 1 : Si $v(l_{i,2})=True$ : alors $v$ valide $C_i$

  • Cas 2 : Sinon : alors nécessairement

    • Sous-Cas 1 : $v(y_i)= True, v(z_i)= False$ : et, par suite, dans $C_{i,1}$ :

      \[v(-l_{i,1}) = False \, \, (= v(x_i))\]

      d’où $v(l_{i,1}) = True$, et $v$ valide $C_i$

    • Sous-Cas 2 : $v(y_i)= False, v(z_i)= True$ : de même (par symétrie), on montre que $v(l_{i,3}) = True$, et $v$ valide $C_i$

  dans tous les cas : $v$ valide $C_i$.

On a donc montré que :

$v$ valide $C_i$ si, et seulement si $v$ valide un et un seul littéral dans $C_{i,1}, C_{i,2}$ et $C_{i,3}$

Par suite :

\[\begin{align*} \text{$v$ valide $𝜓$} \, \, \, \textit{si, et seulement si } \, \,& \text{$v$ valide $C_1$ et $C_2$, $\ldots$, et $C_m$} \\ \textit{si, et seulement si } \, \, & \text{$v$ valide un et un seul littéral dans $C_{1,1}, C_{1,2}$, $C_{1,3}$, $\ldots$, et dans $C_{m,1}, C_{m,2}$, $C_{m,3}$} \\ \textit{si, et seulement si } \, \, & \text{$v$ valide un et un seul littéral dans chaque clause de $\underbrace{\bigwedge\limits_{i=1}^m C_{i,1} ∧ C_{i,2} ∧ C_{i,3}}_{ ≝ \, r(𝜓)}$} \\ \end{align*}\]

Par ailleurs, la réduction est en $\textsf{LOGSPACE}$ puisqu’on n’ajoute que 4 nouvelles variables propositionnelles par clause, si bien que pour toute clause $C_i$, les trois nouvelles clauses $C_{i,1}, C_{i,2}, C_{i,3}$ peuvent être écrites “à la volée” sur le ruban de sortie, utilisant ainsi un espace logarithmique sur le ruban de travail.

On a donc montré que :

$\textsf{UNIQ_SAT}$ est $\textsf{NP}$-complet

EX 2

Q1

$\textsf{VECSUBSETSUM_unary}$ est $\textsf{NP}$-difficile

Il suffit de réduire $\textsf{UNIQ_SAT}$ à $\textsf{VECSUBSETSUM_unary}$, puisque $\textsf{UNIQ_SAT}$ est $\textsf{NP}$-difficile.

Montrons que $\textsf{UNIQ_SAT} ≼_{\textsf{LOGSPACE}} \textsf{VECSUBSETSUM_unary}$

On utilise les mêmes notations que précédemment.

Soit

\[𝜓 ≝ C_1 ∧ ⋯ ∧ Cm ≝ \bigwedge\limits_{i=1}^m \bigvee\limits_{j=1}^3 \underbrace{l_{i,j}}_{ \, ≝ \, \underbrace{𝜀_{i,j}}_{∈\lbrace +, -\rbrace} \underbrace{p_{i,j}}_{∈Prop}}\]

une instance de $\textsf{UNIQ_SAT}$.

Montrons qu’il existe une fonction calculable $r: \textsf{UNIQ_SAT} ⟶ \textsf{VECSUBSETSUM_unary}$ telle que :

• il existe une valuation qui valide un et un seul littéral dans chaque clause de $𝜓$ si, et seulement si

  \[r(𝜓) ≝ \left\langle \underbrace{1 ⋯ 1}_{d \text{ fois}} \, , \underbrace{v_1, \ldots, v_r, \, w}_{∈ ℕ^d \text{ donnés en unaire}} \right\rangle\]

  est tel que

  \[∃I⊆⟦1,r⟧; \, \, w = \sum\limits_{i∈I} v_i\]

• la réduction $r$ est en $\textsf{LOGSPACE}$

En effet :

Soit $v: Prop ⟶ Bool$ une valuation. On note $p_1, \ldots, p_n$ les variables propositionnelles de $𝜓$.

En s’inspirant de la démonstration du caractère $\textsf{NP}$-difficile de $\textsf{SUBSETSUM}$, on va construire un ensemble de $E ≝ \lbrace v_i \rbrace_{i∈⟦1, 2n⟧}$ de $2n$ vecteurs de $ℕ^{n+m}$ donnés en base $1$ tel que :

$v$ valide un et un seul littéral dans chaque clause de $𝜓$ si, et seulement si \(∃I⊆⟦1,2n⟧; \, \, w = \sum\limits_{i∈I} v_i\)

Pour tout $i∈⟦1,n⟧$ :

• \[∀j∈⟦1, n⟧, \, \, \, v_{2i-1}[j] = v_{2i}[j] = \begin{cases} 1 \text{ si } j=i \\ 0 \text{ sinon} \end{cases}\]
• \[∀j∈⟦n+1, n+m⟧, \\ \, \, \, v_{2i-1}[j] = \begin{cases} 1 \text{ si } p_i \text{ apparaît dans } C_{j-n}\\ 0 \text{ sinon} \end{cases} \\ \, \, \, v_{2i}[j] = \begin{cases} 1 \text{ si } -p_i \text{ apparaît dans } C_{j-n}\\ 0 \text{ sinon} \end{cases}\]

Si par exemple $p_i$ apparaît positivement dans $C_k$, négativement dans $C_l$ et $C_r$, la situation est résumée par le tableau suivant :

Coordonnée	Correspond à	$v_{2i-1}$	$v_{2i}$
$1$	$p_1$	$0$	$0$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$i-1$	$p_{i-1}$	$0$	$0$
$i$	$p_i$	$1$	$1$
$i+1$	$p_{i+1}$	$0$	$0$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n$	$p_{n}$	$0$	$0$
$n+1$	$C_1$	$0$	$0$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n+r$	$C_r$	$0$	$1$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n+k$	$C_k$	$1$	$0$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n+l$	$C_l$	$0$	$1$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$n+m$	$C_m$	$0$	$0$

On note $w ≝ {}^t(1 ⋯ 1)$ le vecteur de $ℕ^{n+m}$ dont chacune des coordonnées vaut $1$.

Dans la suite, les opérations seront effectuées en base unaire.

• Si $v$ valide un et un seul littéral dans chaque clause de $𝜓$ :

  Alors en notant $I$ l’ensemble

  \[I≝ \lbrace (2i-1) \times \mathbf{1}_{v(p_i) = True} + 2i \times \mathbf{1}_{v(p_i) = False}\rbrace_{i∈⟦1,n⟧}\]

  il vient que :

  \[w = \sum\limits_{i∈I} v_i\]

  puisque

  • $∀i∈⟦1,n⟧$ :

    \[v_{2i-1} ∈ I ⟺ v_{2i} ∉ I\]

    donc la coordonnée $i$ de $\sum\limits_{l∈I} v_l$ vaut $1$

  • $∀j∈⟦n+1,n+m⟧$ : $v$ valide un et seul littéral dans $C_{j-n} ≝ l_{j-n, 1} ∨ l_{j-n, 2} ∨ l_{j-n, 3}$.

    Sans perte de généralité : si c’est $l_{j-n, 2}$ :

    • Si $l_{j-n, 2}$ est de la forme $+p_k$ (où $p_k∈Prop$) :

      alors, par définition de $I$, $2k-1∈I$, et $v_{2k-1}[j]=1$

    • Si $l_{j-n, 2}$ est de la forme $-p_k$ (où $p_k∈Prop$) :

      alors, par définition de $I$, $2k∈I$, et $v_{2k}[j]=1$

      comme $v$ ne valide aucun autre littéral de $C_{j-n}$, aucun autre vecteur n’a de $1$ sur sa $(j-n)$-ième coordonnée.

      Donc la coordonnée $j$ de $\sum\limits_{l∈I} v_l$ vaut $1$

• Réciproquement, si $∃I⊆⟦1,2n⟧; \, \, w = \sum\limits_{i∈I} v_i$ :

  Pour tout $i∈⟦1,n⟧$, $I$ contient $2i-1$ ou (exclusif) $2i$

  • car si $I$ contenait les deux, la $i$-ème coordonnée de $w$ vaudrait $11$ (base unaire)

  Pour tout $i∈⟦1,n⟧$, on pose

  \[\begin{cases} v(p_i) ≝ True \text{ si } 2i−1∈I \\ v(p_i) ≝ False \text{ sinon} \end{cases}\]

  Pour tout $j∈⟦n+1, n+m⟧$, comme la $j$-ième coordonnée de $w = \sum\limits_{l∈I} v_l$ vaut $1$, il existe un unique vecteur $v_i$ dont la $j$-ième coordonnée vaut $1$, ce implique qu’un et un seul littéral associé à la clause $C_{j-n}$ a pour valuation $True$.

On a donc montré que :

$v$ valide un et un seul littéral dans chaque clause de $𝜓$ si, et seulement si \(∃I⊆⟦1,2n⟧; \, \, w = \sum\limits_{i∈I} v_i\)

---

Par ailleurs, la réduction peut être effectuée en $\textsf{LOGSPACE}$.

En effet :

Il suffit que la machine de Turing effectuant la réduction procède comme suit :

• Étape 1 : la machine parcourt $𝜓$ pour compter les nombres $m$ de clauses et $n$ de variables propositionnelles de $𝜓$ : pour chaque nouvelle clause (resp. variable propositionnelle), la machine écrit un $1$ sur le ruban de sortie, en incrémente un compteur (en binaire) de clauses (resp. de variables propositionnelles) sur le ruban de travail.
  • Reconnaître une nouvelle clause est immédiat (puisque chaque clause contient exactement 3 littéraux), mais pour reconnaître une nouvelle variable, la machine la comparera avec tous les littéraux précédents, pour établir si elle est déjà apparue avant ou non.

  À la fin de cette étape, la dimension $d=n+m$ aura été écrite sur le ruban de sortie, et les nombres $n$ et $m$ seront stockés (en binaire) sur le ruban de travail.

• Étape 2 : la machine fait deux copies des compteurs présents sur le ruban de travail :

  • une copie servira à mémoriser l’indice $i∈⟦1,2n⟧$ du vecteur en cours d’écriture sur le ruban de sortie
  • une autre à mémoriser l’indice $j∈⟦1,n+m⟧$ de la coordonnée du vecteur en cours d’écriture sur le ruban de sortie
  • la version originale servira à réinitialiser le compteur de coordonnée, au vecteur suivant
• Étape 3 : pour construire chacun des $v_i$, la machine utilise (en les décrémentant) les compteurs précédents pour calculer “à la volée” et écrire sur le ruban de sortie la coordonnée courante du vecteur courant.

---

On a donc montré que :

$\textsf{VECSUBSETSUM_unary}$ est $\textsf{NP}$-difficile.

Problème

Pour tout chemin $𝜌∈E^+$, on notera $\vert 𝜌 \vert$ la longueur de $𝜌$.

Q1

Soit $𝜌 ≝ e_1 ⋯ e_l ∈E^+$ un chemin de poids $a$ allant de $u = {}^\bullet e_1$ à $v = {e_l} ^\bullet$ et de longueur minimale (un tel chemin existe puisqu’il existe un chemin de poids $a$ allant de $u$ à $v$).

On note $V_𝜌$ l’ensemble des sommets apparaissant dans $𝜌$ :

\[V_𝜌 ≝ \lbrace x∈V \, \mid \, ∃i∈⟦1, l⟧; x = {e_i}^\bullet \rbrace\]

On pose

\[𝜑 ≝ \begin{cases} ⟦1,l⟧ ⟶ ⟦0,a⟧ \times V \\ i \mapsto \left(p(e_1 ⋯ e_i), {e_i}^\bullet\right) \end{cases}\]

$𝜑$ est bien définie :

En effet :

Il suffit de montrer que :

\[∀i∈⟦1,l⟧, 0 ≤ p(e_1 ⋯ e_i) ≤ a\]

• Pour tout $i∈⟦1,l⟧$, la positivité de $p(e_1 ⋯ e_i)$ est évidente, puisque $p$ est à valeurs dans $ℕ$

• S’il existait un indice $i∈⟦1,l⟧$ tel que $p(e_1 ⋯ e_i) > a$ : alors on aurait

  \[p(𝜌) = p(e_1 ⋯ e_i) + \underbrace{p\Big(\underbrace{e_{i+1}⋯e_l}_{= 𝜀 \text{ si } i=l}\Big)}_{≥0} > a\]

  ce qui est absurde.

$𝜑$ est injective :

Par l’absurde :

Si il existait $i<j∈⟦1,l⟧$ tels que

\[\left(p(e_1 ⋯ e_i), {e_i}^\bullet\right) = \left(p(e_1 ⋯ e_j), {e_j}^\bullet\right)\]

alors

\[p(e_1 ⋯ e_j) = p(e_1 ⋯ e_i) + p(e_i ⋯ e_j)\]

d’où

\[p(e_i ⋯ e_j) = p(e_1 ⋯ e_j) - p(e_1 ⋯ e_i) = 0\]

et comme ${e_i}^\bullet = {e_j}^\bullet$ :

\[𝜌' ≝ e_1 ⋯ e_i e_{j+1} ⋯ e_l\]

• serait de longueur strictement inférieure à celle de $𝜌$
• resterait de poids $a$ puisque $p(e_i ⋯ e_j)$

• relierait encore $u$ à $v$, puisque

  • ${e_i}^\bullet = \underbrace{ {e_j}^\bullet = {}^\bullet{e_{j+1}}}_{\text{puisque } 𝜌 \text{ est un chemin}}$
  • $𝜌$ relie $u$ à $v$

c’est absurde, par minimalité de $𝜌$.

---

Donc, par injectivité de $𝜑$ :

\[long(𝜌) = l = \vert ⟦1,l⟧ \vert ≤ \vert ⟦0,a⟧ \times V \vert = (a+1)V\]

On a donc montré que :

S’il existe un chemin de poids $a$ allant de $u$ à $v$ alors il existe en particulier un tel chemin de longueur au plus $(a + 1)|V |$

Q 2

---

Scolie : Pour tout cycle $c ≝ e_1 ⋯ e_l ∈E^+$, il existe un cycle élémentaire $𝜎$ facteur de $c$.

Démonstration :

Par récurrence sur $\vert c \vert$.

• Initialisation : Si $\vert c \vert=1$ : le résultat est immédiat.

• Hérédité : Supposons le résultat acquis pour tout cycle de longueur strictement inférieure.

  • Cas 1 : Si $c$ est élémentaire : alors le résultat est acquis.

  • Cas 2 : Sinon : alors il existe $i<j∈⟦1,l⟧$ tels que ${}^\bullet{e_i} = {}^\bullet{e_j} = {e_{j-1}}^\bullet$, et en appliquant l’hypothèse de récurrence à $e_i ⋯ e_{j-1}$, le résultat est acquis.

---

Montrons que tout chemin $𝜌∈E^+$ admet une factorisation en cycles, par récurrence sur $\vert 𝜌 \vert$

• Initialisation : Si $\vert 𝜌 \vert=1$ : le résultat est immédiat.

• Hérédité : Supposons le résultat acquis pour tout chemin de longueur strictement inférieure.

  • Cas 1 : Si $𝜌$ n’a aucun facteur qui soit un cycle : alors $𝜌 ≝ 𝜌_0$, et le résultat est acquis.

  • Cas 2 : Sinon : alors il existe $i<j∈⟦1,l⟧$ tels que ${}^\bullet{e_i} = {e_{j}}^\bullet$, et :

    • Sous-Cas 1 : soit $𝜌$ est un cycle élémentaire : alors $𝜌 ≝ 𝜀 𝜌^1$, et le résultat est acquis

    • Sous-Cas 2 : soit $𝜌$ contient a pour facteur strict un cycle élémentaire $𝜎$, d’après la scolie :

      \[𝜌 ≝ 𝜌' 𝜎 𝜌''\]

      et en appliquant l’hypothèse de récurrence à $𝜌’$ et $𝜌’’$,

      \[𝜌 ≝ 𝜌'_0 𝜎_{1,1}^{k_1'} 𝜌'_1 ⋯ 𝜎_{1,r'}^{k_{r'}'} 𝜌'_{r'} \, \, 𝜎 \, \, ρ''_0 σ_{2,1}^{k_1''} 𝜌''_1 ⋯ σ_{2,r''}^{k_{r''}''} 𝜌''_{r''}\]

      et $𝜌$ admet bien une factorisation en cycles.

On a donc montré que :

Tout chemin $𝜌∈E^+$ admet une factorisation en cycles.

3.

---

NB : on utilisera les notations de l’énoncé pour la factorisation en cycles : quand on posera $𝜌 ≝ 𝜌_0 𝜎_{1}^{k_1} 𝜌_1 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r} ∈E^+$, il sera sous-entendu que $𝜌_0 𝜎_{1}^{k_1} 𝜌_1 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r}$ est une factorisation en cycles de $𝜌$, dont l’existence a été démontrée dans la question précédente.

---

Pour tout chemin $𝜌 ≝ 𝜌_0 𝜎_{1}^{k_1} 𝜌_1 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r} ∈E^+$, on note $v(𝜌)$ le nombre d’arêtes n’appartenant pas à un cycle élémentaire + le nombre de cycles élémentaires dans toute factorisation en cycles de $𝜌$ :

\[v(𝜌) ≝ \vert \lbrace e_i ∈ 𝜌 \, \mid \, \text{tout facteur de } 𝜌 \text{ contenant $e_i$ n'est pas un cycle élémentaire} \rbrace \vert + r \\ = \sum_{j=0}^r \vert 𝜌_j \vert + r\]

NB :

• on dira abusivement qu’une arête $e_i$ “appartient à” un chemin $𝜌$ si elle est un facteur de $𝜌$
• “$v$” pour “variant”

Notons que $v(𝜌)$ est bien défini, car

• on peut partitionner l’ensemble des arêtes appartenant à $𝜌$ en celles qui n’appartiennent à aucun cycle élémentaire et celles qui appartiennent à un cycle élémentaire
• deux factorisations en cycles d’un même chemin $𝜌$ ne peuvent avoir un nombre différent de cycles élémentaires, car sinon, par égalité des deux factorisations, celle qui en a strictement plus impose à un facteur $𝜌_i$ (n’ayant aucun cycle élémentaire en facteur, par définition) de l’autre de contenir un cycle élémentaire, ce qui est absurde.

---

Supposons que $G$ admet un chemin $𝜌$ de poids $a$ allant de $s$ à $t$.

Montrons qu’il existe en particulier un tel chemin avec une factorisation en cycles dont les cycles élémentaires ont tous des poids différents.

Par récurrence sur $v(𝜌)$.

• Initialisation : Si $v(𝜌)=1$ : le résultat est immédiat, puisque $𝜌$ est alors une arête.

• Hérédité : Supposons le résultat acquis pour tout cycle dont l’image par $v$ est strictement inférieure.

  Par l’absurde : si tout chemin de poids $a$ et allant de $s$ à $t$ admet une factorisation en cycles dont deux cycles élémentaires ont des poids identiques, alors c’est en particulier le cas pour $𝜌 ≝ 𝜌_0 𝜎_{1}^{k_1} 𝜌_1 𝜎_{2}^{k_2} 𝜌_2 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r} ∈E^+$, et supposons, sans perte de généralité, que

  \[p(𝜎_1) = p(𝜎_2)\]

  Alors

  \[𝜌' ≝ 𝜌_0 𝜎_{1}^{k_1+k_2} 𝜌_1 𝜌_2 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r}\]

  est toujours un chemin de poids $a$ allant de $s$ à $t$, mais

  \[v(𝜌') < v(𝜌)\]

  car

  • Cas 1 : Si $𝜌_1 𝜌_2$ ne contient aucun cycle :

    alors dans $𝜌’$ : le nombre d’arêtes n’appartenant pas à un cycle élémentaire est toujours le même, mais le nombre de cycles élémentaires a diminué strictement

  • Cas 2 : Sinon :

    alors comme toute factorisation en cycles de $𝜌_1 𝜌_2$ contient au plus un cycle élémentaire (sinon, $𝜌_1$ ou $𝜌_2$ a un cycle en facteur), toute factorisation en cycles de $𝜌_1 𝜌_2$ contient exactement un cycle élémentaire, et, dans $𝜌’$ : le nombre de cycles élémentaires est toujours le même, mais le nombre d’arêtes n’appartenant pas à un cycle élémentaire a diminué strictement (puisque certaines arêtes de $𝜌_1 𝜌_2$ appartiennent maintenant à un cycle élémentaire).

  Donc en appliquant l’hypothèse de récurrence, il existe un chemin de poids $a$ allant de $s$ à $t$ avec une factorisation en cycles dont les cycles élémentaires ont tous des poids différents : c’est absurde.

On a donc montré que :

Si que $G$ admet un chemin $𝜌$ de poids $a$ allant de $s$ à $t$, alors il existe en particulier un tel chemin avec une factorisation en cycles dont les cycles élémentaires ont tous des poids différents.

Q4

Supposons que $G$ a un chemin de poids $a$ reliant $u$ à $v$.

Montrons qu’il existe un tel chemin de longueur bornée par $Q(k, m, P, a)$, où $Q$ est un polynôme à 4 variables.

Commençons par remarquer que les résultats de Q2 et Q3 sont encore valables, puisqu’on n’a pas utilisé, dans leur démonstration, le fait que $p$ soit à valeurs dans $ℕ$.

Pour tout chemin $𝜌 ≝ 𝜌_0 𝜎_{1}^{k_1} 𝜌_1 ⋯ 𝜎_{r}^{k_{r}} 𝜌_{r} ∈E^+$ de poids $a$ reliant $u$ à $v$ dont les cycles élémentaires ont des poids différents (l’existence d’un tel chemin est assurée par Q4) :

\[\begin{cases} \vert 𝜌 \vert = \sum\limits_{j=0}^r \vert 𝜌_j \vert + \sum\limits_{j=1}^r k_j \vert 𝜎_j \vert \\ a = p(𝜌) = \sum\limits_{j=0}^r p(𝜌_j) + \sum\limits_{j=1}^r k_j p(𝜎_j) \end{cases}\]

Or, le nombre $r$ de cycles élémentaires $𝜎_i$ est majoré par $2P+1 = \vert ⟦-P, P⟧ \vert$

• en effet : les poids de $𝜎_i$ sont tous distincts et à valeurs dans $⟦-P, P⟧$ : la fonction $𝜑 : \lbrace 𝜎_i \rbrace_{i∈⟦1,r⟧} ⟶ ⟦-P, P⟧, 𝜎_i \mapsto p(𝜎_i)$ est donc injective, et

  \[r = \vert ⟦1,r⟧ \vert ≤ 2P+1 = \vert ⟦-P, P⟧ \vert\]

Donc comme : $∀j∈⟦0,r⟧$

\[\begin{cases} \vert p_j \vert ≤ n \\ \vert 𝜎_j \vert ≤ n \\ \end{cases}\]

(les sommets y apparaissant sont distincts, sauf éventuellement le premier et le dernier)

alors :

\[\vert 𝜌 \vert ≤ (r+1) n + n \sum\limits_{j=1}^r k_j \\ ≤ (2P+2) n + n \sum\limits_{j=1}^r k_j\]

et

\[a = \sum\limits_{j=0}^r \underbrace{p(𝜌_j)}_{≥(-P) \times \vert 𝜌 \vert = -nP} + \sum\limits_{j=1}^r k_j p(𝜎_j) \\ ≥ -nP(2P+2) + \sum\limits_{j=1}^r k_j p(𝜎_j)\]

d’où

\[\sum\limits_{j=1}^r k_j p(𝜎_j) ≤ a + nP(2P+2)\]

De plus, comme

\[a = \sum\limits_{j=0}^r \underbrace{p(𝜌_j)}_{≤pm \times \vert 𝜌 \vert = -nP} + \sum\limits_{j=1}^r k_j p(𝜎_j) \\ ≤ nP(2P+2) + \sum\limits_{j=1}^r k_j\]

D’où, enfin :

\[a - nP(2P+2) ≤ \sum\limits_{j=1}^r k_j \underbrace{p(𝜎_j)}_{∈⟦-P,P⟧} ≤ a + nP(2P+2)\]

il reste à majorer les $k_i$, mais je manque de temps pour le faire.

Q5

Le caractère $\textsf{NP}$-difficile est clair, en réduisant le problème précédent (qui est un cas particulier pour $p$ à valeurs dans $ℕ$) à celui-là.

Pour montrer que $\textsf{WEIGHTEDPATH}$ avec des poids entiers relatifs est dans $\textsf{NP}$, on procède exactement de la même manière que dans le cours, avec le lemme d’Euler, en devinant un vecteur d’occurrences d’arcs dont les composantes bornées par $Q(k, m, P, a)$ (donc de taille polynomiale).

Comme les vérifications faites (pour vérifier les hypothèses du lemme d’Euler et calculer le poids du chemin) n’exigent que

• d’utiliser des compteurs
• de stocker des nombres (en binaire)
• faire des additions avec ces nombres

la réduction s’effectue en $\textsf{LOGSPACE}$.