Réduction de Karp

La réduction de Karp est le type de Réduction polynomiale standard utilisé pour comparer la difficulté des problèmes.

Définition

Soient $Q_1$, $Q_2$​ deux problèmes de décision. $Q_1$​ est réductible à $Q_2$ par réduction de Karp (noté $Q_1{\ll }_P{Q}_2$​) s’il existe une fonction $f$ calculable en temps polynomial telle que :

$$f:I(Q1)\to I(Q2)$$

et

$$i\in L(Q_1)⟺f(i)\in L(Q_2)$$

Propriétés

1. Si $Q_1{\ll }_P{Q}_2$

Alors

$$Q_2\in P⟹Q_1\in P$$

2. Contraposée

$$Q_1\notin P⟹Q_2\notin P$$

3. Transitivité

Si $Q_1{\ll }_P{Q}_2$​ et $Q_2{\ll }_P{Q}_3$​ alors $Q_1{\ll }_P{Q}_3$

Preuve : Composer les transformations $g\circ f:I(Q_1)\to I(Q_3)$

Exemples classiques

Clique ${\ll }_P$ Stable maximum (MIS)

$$f:⟨G,k⟩\to ⟨\overline{G},k⟩$$

Stable maximum (MIS) ${\ll }_P$ Vertex Cover (VC)

$$f:⟨G,k⟩\to ⟨G,n-k⟩$$

Par transitivité

Clique ${\ll }_P$​ Vertex Cover (VC) via :

$$⟨G,k⟩\stackrel{f}{\to }⟨\overline{G},k⟩\stackrel{g}{\to }⟨\overline{G},n-k⟩$$