TD d’algorithmique numéro 11 Yves Robert et Daniel Hirschkoff semaine du 12 au 17 décembre 1999

Question 1 ⋆ Couverture des sommets d’un graphe ⋆

On couvre un graphe non orienté G = (S, A) en se donnant S′ ⊆ S vérifiant la propriété suivante: pour toute arête a de A, au moins l’un des sommets reliés par a est dans S′. La taille de la couverture S′ est alors définie comme le nombre d’éléments de cet ensemble. On cherche une couverture de taille minimale.

Question 1.1

Exprimer le problème sous forme d’un problème de décision. Montrer que ce problème appartient à NP.

Question 1.2

Montrer, en raisonnant avec la notion de complément d’un graphe non orienté (le graphe comportant les arêtes non présentes dans le graphe de départ), que Clique ≤_{P} Couverture.

Question 2 ⋆ 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 2.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.

Dire 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’instance 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 2.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 2.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 \frac{d}{dn}(1−ϵ)^{n}n > 0; que peut-on en déduire? En déduire que le résultat de l’approximation n’est pas inférieur de plus de 1 − ϵ par rapport à y^{∗}.

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

Question 3 ⋆ 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.