TD d’algorithmique numéro 12 Olivier Bodini et Natacha Portier

lundi 10 décembre 2001

Question 1 ⋆ Somme d’un sous-ensemble ⋆

On se donne un ensemble fini E ⊆ ℕ et une valeur cible t ∈ ℕ, et on cherche un ensemble E′ ⊆ E tel que la somme des éléments de E′ soit égale à t.

Question 1,1 ⋆ NP complétude ⋆

On veut montrer que le problème de la somme d’un sous-ensemble est NP-complet en le réduisant à la couverture des sommets d’un graphe G.

Montrer que le problème appartient à NP.

On se donne, pour montrer que Couverture Sommets ≤_{P} Somme Sous Ensemble, un graphe non orienté G = (S, A) (avec S = {v_{0}, v_{1}, …, v_{|S|−1}} et A = {e_{0}, e_{1}, …, e_{|A|−1}}), que l’on représente par une matrice d’incidence B = b_{ij} définie de la manière suivante :

b_{ij} = \{ \begin{matrix}1 & si l’arête e_{j} arrive au sommet v_{i} \\ 0 & sinon. \end{matrix}

On part également d’un entier k correspondant à l’entrée du problème de couverture du graphe sur laquelle on travaille (i.e. on cherche une couverture de taille k).

L’idée est de construire un ensemble E d’entiers qui représentent le graphe. Ces entiers seront écrits en base 4 modifiée (b4m), ce qui signifie la chose suivante : les |A| chiffres moins significatifs d’un nombre sont exprimés en base 4, et le chiffre le plus significatif prend une valeur comprise (au sens large entre) zéro et k. On définit ensuite E de la manière suivante :

– pour chaque sommet v_{i}, on crée un entier positif x_{i} dont la représentation b4m est constituée d’un 1 suivi de |A| chiffres ; ces derniers correspondent à la ligne de v_{i} dans B. Autrement dit, on a :

x_{i} = 4^{|A|} + ∑_{0≤j≤|A|−1} b_{ij}4^{j} .

– Pour chaque arête e_{j} ∈ A, on crée un entier positif y_{j} représentant une ligne de la matrice identité, i.e.

y_{j} = 4^{j} .

On se donne ensuite t en posant :

t = k4^{|A|} + ∑_{0≤j≤|A|−1} 2. 4^{j} .

1. Supposons que le graphe G possède une couverture de sommets S′ ⊆ S de taille k, avec S′ = {v_{i_{1}}, v_{i_{2}}, …, v_{i_{k}}}. On lui associe

E′ = {x_{i_{1}}, x_{i_{2}}, …, x_{i_{k}}} ∪
{y_{j}| e_{j} est incidente à un seul sommet de S′} .

Montrer que ∑_{s∈E′} s = t.

2. Réciproquement, soit E′ ⊆ E un ensemble dont la somme des éléments vaut t; on écrit E′ = {x_{i_{1}}, x_{i_{2}}, …, x_{i_{m}}} ∪ {y_{j_{1}}, y_{j_{2}}, …, y_{j_{p}}}. Montrer que m = k et que S′ = {v_{i_{1}}, v_{i_{2}}, …, v_{i_{m}}} est une couverture de sommets de G.

3. Conclure.

Question 1,2 ⋆ Algorithme en temps exponentiel ⋆

On va définir une solution optimale avec un algorithme en temps exponentiel. On écrit l’algorithme suivant (on suppose disposer d’une fonction Fusionner de fusion de listes) :

Somme Exacte(S,t):= n:=S L_{0}:=[0]

pour i de 1 à n faire

L_{i}:= Fusionner(L_{i−1}, L_{i−1} + x_{i}) supprimer de L_{i} les éléments supérieurs à t

finpour

Retourner le max de L_{n}

Dans l’algorithme ci-dessus, L_{i−1} + x_{i} désigne la liste d’entiers résultant de L_{i−1} en ajoutant x_{i} à tous les éléments de la liste.

1. Soit P_{i} l’ensemble des valeurs obtenues en effectuant les sommes de tous les sousensembles de x_{1}, …, x_{i}. Montrer que

P_{i} = P_{i−1} ∪ (P_{i−1} + x_{i}) .

Montrer que L_{i} est une liste triée des éléments de P_{i} de valeur inférieure à t.

2. Quelle est la taille maximale de L_{i}? Qu’en déduit-on eu égard au temps d’exécution de l’algorithme?

Question 1,3 ⋆ Schéma d’approximation en temps entièrement polynomial ⋆

On s’attache à présent à limiter la taille de L_{i}, pour obtenir un schéma d’approximation en temps entièrement polynomial. On va pour ce faire introduire une notion de seuil, qui va être un réel δ appartenant à ]0; 1]. À ce seuil correspond une transformation d’une liste L en L′ selon le principe suivant :

y ∈ L ∧ y ∉ L′ ⇔ ∃z ∈ L′. z ≤ y ∨ \frac{(y − z)}{y} ≤ δ

(NB : la condition ci-dessus peut aussi s’écrire (1 − δ)y ≤ z ≤ y). L’idée est d’écrêter L en L′.

1. Écrire l’algorithme de seuil, qui transforme une liste L en une liste écrêtée L′; quelle en est la complexité?

2. Adapter l’algorithme exponentiel ; le retour de l’algorithme ainsi obtenu est-il la somme d’un sous-ensemble de S?

Soit maintenant y^{∗} ∈ P_{n} une solution optimale.

3. Montrer que le résultat de l’approximation n’est pas inférieur de plus de 1−ϵ par rapport à y^{∗}. On pourra commencer par montrer que pour tout i et pour tout y ∈ P_{i} au plus égal à t il y a un z dans L_{i} tel que (1 − \frac{ϵ}{n})^{i}y ≤ z ≤ y.

4. Établir une borne sur la longueur de L_{i} en fonction de n et t; qu’en déduit-on?

Question 2 ⋆ Partition ⋆

Le problème de la partition consiste, étant donnés un ensemble fini A et une fonction s : A → ℕ, à chercher un ensemble A′ ⊆ A t.q.

∑_{a∈A′} s(a) = ∑_{a∈A\A′} s(a) .

Montrer que ce problème est NP complet en utilisant ce qui précède..

Question 3 ⋆ La philanthropie de l’ouvrier charpentier ⋆

Montrer que le problème suivant est NP-complet : On se donne une suite de barres rigides, de longueurs éventuellement différentes et entières, reliées bord-à-bord par des ressorts. Peut-on la plier de manière à ce que la taille obtenue soit au plus k?