Prix de la Connexité pourle Problème de l’Ensemble

DominantMémoire réalisé par Églantine CAMBY

pour l’obtention du diplôme de Master en sciences mathématiques

Année académique 2009–2010

Directeurs : M. CARDINAL JeanM. MÉLOT Hadrien

Service d’Informatique Théorique • Faculté des SciencesUniversité de Mons • Place du Parc 20 • B-7000 Mons

Remerciements

Je tiens à remercier en premier lieu les Professeurs Jean Cardinal et Ha-drien Mélot, mes directeurs de mémoire, pour m'avoir accompagné et entourétout au long de ce travail. Leur disponibilité, leur aide et les nombreuses dis-cussions que nous avons pu partager ont grandement contribué à l'élaborationde ce mémoire.

Je remercie également les Professeurs Véronique Bruyère et Thomas Bri-haye d'avoir consacré du temps à la lecture et l'évalutation de cet écrit.

J'aimerais remercier les professeurs et assistants de l'Université de Monsde m'avoir encadré et instruit tout au long des mes études.

Cette dernière année d'étude m'a ouvert di�érentes portes auprès d'autresétablissements : la Faculté Polytechnique de Mons, l'Université Libre deBruxelles... Je souhaite inclure dans mes remerciements les professeurs etassistants que j'y ai rencontrés.

Je ne peux terminer ces remerciements sans y inclure ma famille et mesamis qui m'ont encouragée et soutenue durant mes années d'étude, Stépha-nie Bridoux et Sébastien Millecam pour leur lecture attentive et leur appuiinestimable.

1

Table des matières

1 Dé�nitions et notions de base de Théorie des Graphes 5

1.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Degré d'un sommet . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Chemins et cycles . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.5 Arbres et forêts . . . . . . . . . . . . . . . . . . . . . . . . . . 121.6 Contraction et mineur . . . . . . . . . . . . . . . . . . . . . . 151.7 Quelques ensembles particuliers . . . . . . . . . . . . . . . . . 16

1.7.1 Couplage . . . . . . . . . . . . . . . . . . . . . . . . . 161.7.2 Couverture . . . . . . . . . . . . . . . . . . . . . . . . 181.7.3 Ensemble dominant . . . . . . . . . . . . . . . . . . . . 19

2 Complexité, algorithmes et approximations 22

2.1 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.1.1 Qu'est-ce que la complexité ? . . . . . . . . . . . . . . . 222.1.2 Quelques classes de complexité . . . . . . . . . . . . . 252.1.3 Relations entre les di�érentes classes . . . . . . . . . . 262.1.4 Théorème de Cook-Levin et problèmes NP -complets . 262.1.5 Quelques problèmes NP -complets . . . . . . . . . . . . 282.1.6 Interprétation de la NP -complétude . . . . . . . . . . 31

2.2 Algorithmes et approximations . . . . . . . . . . . . . . . . . . 322.2.1 Qu'est-ce qu'un algorithme d'approximation ? . . . . . 332.2.2 Le Problème de Couverture . . . . . . . . . . . . . . . 352.2.3 Le Problème de l'Ensemble Dominant . . . . . . . . . . 482.2.4 La L-réduction ou réduction linéaire . . . . . . . . . . 49

3 Prix de la Connexité 59

3.1 Dé�nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.2 Le Prix de la Connexité de V C . . . . . . . . . . . . . . . . . 60

3.2.1 Borne supérieure du PoC de V C . . . . . . . . . . . . 613.2.2 Qualité de la borne supérieure du PoC de V C . . . . . 63

2

4 Le Problème de l'Ensemble Dominant 66

4.1 Applications des ensembles dominants . . . . . . . . . . . . . 664.2 Le PoC concernant l'Ensemble Dominant . . . . . . . . . . . . 67

4.2.1 Encadrement du PoC . . . . . . . . . . . . . . . . . . 684.2.2 Étude du PoC en fonction de l'ordre d'un graphe et de

son degré minimum . . . . . . . . . . . . . . . . . . . . 704.3 Quelques familles particulières de graphes . . . . . . . . . . . 82

4.3.1 Les cographes . . . . . . . . . . . . . . . . . . . . . . . 824.3.2 Les graphes de diamètre 2 . . . . . . . . . . . . . . . . 83

4.4 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5 Conclusion 89

3

Introduction

Ce mémoire s'inscrit dans le domaine de la Théorie des Graphes. Il abordedeux problèmes di�ciles d'optimisation : le Problème de l'Ensemble Domi-nant, ainsi que sa version connexe. Rappelons qu'un ensemble dominant estun ensemble D de sommets tel que chaque sommet du graphe est soit dansD, soit voisin à au moins un élément de D. Nous avons aussi qu'un ensembledominant D est connexe s'il existe un chemin dans D entre toutes les pairesde sommets de D.

Ces ensembles trouvent leurs applications dans de nombreux domainestels que la localisation des radars, l'emplacement des stations de communi-cation entre di�érentes villes, les routages, ...

Dans le Chapitre 1, nous donnons les dé�nitions et les notions de base dela Théorie des Graphes.

Le Chapitre 2 se scinde en deux grandes parties. La première partie dé-voile, dans les grandes lignes, la théorie de la complexité. Cette théorie étudiela di�culté de résolution d'un problème par un algorithme. Après avoir dé�nila notion de complexité, nous donnons quelques résultats issus de la théoriede la complexité et nous énonçons le Théorème de Cook-Levin. La secondepartie de ce chapitre explique la notion d'algorithme d'approximation pourun problème. Un tel algorithme permet de trouver rapidement une solutionproche d'une optimale. Plusieurs algorithmes d'approximation sont analysés.Nous découvrons également une relation entre deux problèmes. Il s'agit dela L-réduction ou réduction linéaire.

Le Chapitre 3 porte sur le concept du Prix de la Connexité, introduit parCardinal et Levy en 2008. Cette notion permet d'évaluer le coût de l'ajoutde la contrainte de connexité pour un problème donné. Nous étudions le Prixde la Connexité pour un autre problème que celui de l'Ensemble Dominantconnu sous le nom de Problème de Couverture des Arêtes par les Sommets.

Dans le dernier chapitre, nous détaillons les recherches personnelles con-cernant le Prix de la Connexité de l'Ensemble Dominant. Les résultats obte-nus portent sur des applications, l'encadrement du Prix de la Connexité etsur la complexité de son calcul.

Ainsi, le travail réalisé dans ce mémoire permet de découvrir une nouvellebranche de la � forêt � composant la Théorie des Graphes.

4

Chapitre 1

Dé�nitions et notions de base de

Théorie des Graphes

Dans ce chapitre, nous présentons quelques notions de base de Théoriedes Graphes. Notre objectif est de nous munir d'un bagage lexicographiquesu�sant. Nous nous basons sur le livre de Diestel [Die00, p. 1-21].

1.1 Graphes

Dé�nition 1.1. Un graphe est une paire G = (V,E) d'ensembles telle queE contient des paires non ordonnées de V .

Les éléments de V sont appelés sommets, noeuds ou points du grapheG et les éléments de E sont les arêtes. Nous notons l'ensemble des sommetsd'un graphe G par V (G) et celui des arêtes par E(G). Le nombre de sommetsd'un graphe G est son ordre, noté |G|. Le nombre d'arêtes est noté ‖G‖. Noustravaillerons toujours dans le cadre de graphes d'ordre �ni.

Dé�nition 1.2. Un sommet v est incident à une arête e ou encore e est unearête sur v si v ∈ e.

Les deux sommets incidents à une arête sont appelés les extrémités decette arête. Nous disons qu'une arête joint ses extrémités. Une arête {u, v}est notée uv ou vu. L'ensemble de toutes les arêtes sur un sommet v estinscrit E(v).

Exemple 1.3. Le graphe G représenté par la Figure 1.1 est dé�ni parV = {a, b, c, d} et par E = {ab, bc, cd, ad, ac}. L'ordre de G est 4. Ce graphepossède 5 arêtes. L'ensemble E(a) est {ab, ac, ad}.

5

a b

cd

G

ab

cd

bcadac

Figure 1.1 � Exemple d'un graphe.

Dé�nition 1.4. Deux noeuds u et v de G sont adjacents ou voisins si uvforme une arête de G.

Deux arêtes distinctes e et f sont dites adjacentes si elles ont une extré-mité en commun. Si tous les noeuds de G sont adjacents deux-à-deux alorsG est complet. Nous noterons Kn le graphe complet à n sommets.

Exemple 1.5. La Figure 1.2 représente le graphe complet à 8 sommets.

Figure 1.2 � K8, le graphe complet à 8 sommets.

Un ensemble de sommets forme une clique si tous les sommets de cetensemble sont deux-à-deux adjacents. Une paire d'arêtes ou de noeuds non-adjacents est dite indépendante. Plus généralement, un ensemble de noeudsou d'arêtes est indépendant ou stable s'il ne contient pas deux élémentsadjacents.

Exemple 1.6. Dans le graphe de la Figure 1.3, l'ensemble de sommets{x2, x3, x4, x7} forme une clique tandis que les ensembles {x1, x3, x5} et{x2x3, x4x7, x5x6} sont indépendants.

6

x1

x2

x3

x4

x5

x6 x7

Figure 1.3 � Graphe contenant une clique de taille 4 et deux ensemblesstables de sommets et d'arêtes de taille 3.

Dé�nition 1.7. Soient G1 = (V1, E1) et G2 = (V2, E2) deux graphes. Nousdisons que G1 est un sous-graphe de G2, ou encore que G2 contient G1 siV1 ⊆ V2 et E1 ⊆ E2. On écrit alors que G1 ⊆ G2.

Une notion importante liée à celle de sous-graphe est le sous-graphe in-duit. Le graphe G1 est un sous-graphe induit de G2 si G1 ⊆ G2 et G1 contienttoutes les arêtes uv de E2 où u et v appartiennent à V1. Nous disons que V1

induit G1 dans G2 et on note G1 = G2[V1]. Donc si U ⊆ V est un ensemblede sommets alors G[U ] est le graphe sur U où les arêtes sont précisémentles arêtes de G avec les deux extrémités dans U . Par ailleurs, si U est unensemble de sommets alors G− U est le graphe induit sur G par V (G) \ U .D'un autre point de vue, nous pouvons comprendre G − U par le graphe Gdans lequel nous avons éliminé tous les sommets de V ∩ U et leurs arêtesincidentes.

Exemple 1.8. Dans la Figure 1.4, H est un sous-graphe de G mais il n'estpas induit car l'arête ac n'appartient pas à H. Par contre, G− d est bien ungraphe induit dans G.

Nous disons que G1 ⊆ G2 est un sous-graphe couvrant de G2 si V (G1)couvre tous les sommets de G2, c'est-à-dire si V (G1) = V (G2).

Exemple 1.9. Le graphe de la Figure 1.5 contient un sous-graphe couvrantqui est le graphe représenté par des arêtes plus foncées.

Soient G1 = (V1, E1), G2 = (V2, E2) deux graphes. Nous dé�nissonsG1∪G2 par (V1∪V2, E1∪E2) et G1∩G2 par (V1∩V2, E1∩E2). De plus, si Fest un ensemble d'arêtes sur V1 alors G1 − F est naturellement (V1, E1 \ F )et G1 + F vaut (V1, E1 ∪ F ).

7

a b

c

d

e

a b

ce

a b

ce

G H G− d

Figure 1.4 � G− d est un graphe induit dans G mais ce n'est pas le cas dusous-graphe H.

Figure 1.5 � Graphe contenant un sous-graphe couvrant.

1.2 Degré d'un sommet

Soit G = (V,E) un graphe non vide. L'ensemble des voisins d'un sommetv dans G est noté NG(v).

Dé�nition 1.10. Le degré d'un sommet v de G, noté dG(v) ou d(v), est lenombre d'arêtes incidentes sur v, c'est-à-dire le nombre de voisins de v, ouencore dG(v) = |NG(v)|.

Un sommet de degré 0 est dit isolé. Le degré minimum d'un graphe G,noté δ(G), vaut min{dG(v)|v ∈ V (G)}, et le degré maximum est

∆(G) = max{dG(v)|v ∈ V (G)}.

Nous avons toujours δ(G) 6 ∆(G).

8

Exemple 1.11. Dans le graphe de la Figure 1.1, le sommet a possède 3voisins. Donc son degré vaut 3. De plus, le degré minimum de G est 2 et sondegré maximum vaut 3.

1.3 Chemins et cycles

Dé�nition 1.12. Un chemin est un graphe non-vide P = (V,E) de la forme :V = {x0, ..., xk}, E = {x0x1, ..., xk−1xk}, où les xi sont tous distincts.

Les sommets x0 et xk sont liés par P et sont appelés extrémités du che-min P . Les autres sommets, à savoir x1, ..., xk−1, sont les sommets intérieursde P . La longueur d'un chemin est dé�nie par le nombre d'arêtes de ce che-min, à savoir dans ce cas-ci k. Notons que si le chemin est réduit à un seulsommet alors il est de longueur nulle. Nous dé�nirons souvent un chemin parl'abréviation suivante : P = x0x1...xk.

Dé�nition 1.13. Soit P = x0...xk−1 un chemin de longueur au moins 2. Legraphe C = x0x1...xk−1x0 est un cycle.

La longueur d'un cycle est le nombre de sommets ou d'arêtes, à savoir kpour C. Un cycle de longueur k, où k > 3, est dit un k-cycle. La circonférence

d'un graphe est la longueur d'un plus long cycle dans ce graphe et le tour de

taille ou maille est la longueur d'un plus court cycle. Si G ne contient pasde cycle alors son tour de taille vaut +∞ et sa circonférence est nulle. Unearête qui a ses extrémités dans un cycle mais qui ne fait pas elle-même partiede ce cycle est appelée une corde de ce cycle. Un cycle induit dans G est uncycle qui ne possède aucune corde.

Exemple 1.14. Dans la Figure 1.6, le graphe P est un chemin de G delongueur 4. Le graphe C est un cycle de G avec une corde. Ce cycle estde longueur 6. De plus, le tour de taille de G vaut 3, car c'est la longueurminimum d'un cycle, et sa circonférence vaut 7.

La distance dG(u, v) dans G entre deux sommets u et v est la longueurdu plus court chemin dans G ayant pour extrémités u et v. Le diamètre deG est la plus grande distance entre deux sommets de G, c'est-à-dire

diam(G) = max{dG(u, v)|u, v ∈ G}.

Dé�nition 1.15. Soient G = (V,E) un graphe, A,B deux ensembles desommets sur V . Nous appelons P = x0...xk un A−B chemin si

V (P ) ∩ A = {x0} et V (P ) ∩B = {xk}.

9

G P C

Figure 1.6 � Un chemin P de longueur 4 et un cycle non-induit C de lon-gueur 6 dans le graphe G.

Plus généralement, soit H un sous-graphe de G. On dit que P est unH-chemin si P est un chemin de longueur au moins 1 et si P rencontre Hexactement en ses extrémités.

1.4 Connexité

Nous nous intéressons ici à la notion de connexité. Intuitivement, ungraphe connexe est un graphe pour lequel chaque sommet est relié à n'importequel autre sommet par un chemin. Dès lors aucun sommet n'est isolé, niaucune � partie � du graphe.

Dé�nition 1.16. Un graphe non-vide G est dit connexe si pour toute pairede ses sommets, il existe un chemin dans G reliant ces sommets.

Soit G un graphe quelconque. Un sous-graphe maximal connexe de G estappelé composante connexe de G. Un ensemble de sommets de G est ditconnexe si son graphe induit sur G est connexe.

Exemple 1.17. Le graphe de la Figure 1.7 n'est pas connexe ; il a deux com-posantes connexes, C1 et C2. De plus, l'ensemble de sommets {x1, x2, x3, x4}est connexe puisque G[{x1, x2, x3, x4}] est connexe.

Soient G = (V,E) un graphe connexe et A,B deux ensembles connexesdisjoints de sommets sur V . La distance entre A et B, notée d(A,B), est lalongueur d'un plus court A − B chemin. Un A − B chemin avec une tellelongueur réalise la distance entre A et B. Remarquons qu'un tel cheminn'est pas nécessairement unique. Plus généralement, considérons A1, . . . , Anune suite �nie d'ensembles connexes disjoints de sommets sur V . La distance

10

x1

x2

x3x4

x5

x6 x7

x8

x9

x10

x1 x2

x3x4

G

C1

C2

G[{x1, x2, x3, x4}]

Figure 1.7 � Graphe G formé de deux composantes connexes, C1 et C2, etun sous-graphe induit G[{x1, x2, x3, x4}].

entre A1 et les autres ensembles est le minimum des distances entre A1 etchaque autre ensemble, c'est-à-dire

d(A1,∪ni=2Ai) = min{d(A1, Ai)|i = 2, . . . , n}.

Un ensemble Ak à une distance d(A1,∪ni=2Ai) de A1 est un ensemble le plus

proche de A1 et un A1 − Ak chemin avec une telle longueur réalise cettedistance. De plus, aucune hypothèse n'assure l'unicité, tant pour un ensemblele plus proche de A1 que pour un A1−Aj chemin de longueur d(A1,∪ni=2Ai).

Exemple 1.18. Le graphe de la Figure 1.8 contient 4 ensembles connexes :A1, A2, A3 et A4. L'ensemble A1 est à une distance 2 des autres ensembles.L'ensemble A3 est le plus proche de A1 et tous les A1−A3 chemins ne passantpas par un autre ensemble, A2 ou A4, sont de longueurs 2, d'où ils réalisent ladistance entre A1 et A3. De plus, la distance entre A4 et les autres ensemblesvaut 1. Les ensembles A2 et A3 sont les plus proches de A4. Malgré qued(A1, A3) = 2 et d(A3, A4) = 1, nous avons que la distance entre A1 et A4

vaut 4.

Dans ce mémoire, nous travaillerons toujours avec des graphes connexes.

11

A1

A3A4

A2

Figure 1.8 � Graphe contenant 4 ensembles connexes : A1, A2, A3 et A4.

1.5 Arbres et forêts

Nous allons découvrir une classe de graphes intéressants : celle des forêtset des arbres. Intuitivement, la structure d'arbre rappelle la rami�cation desbranches d'un arbre. Elle est sujette à de nombreuses études en raison deses nombreuses applications. En e�et, nous trouvons la structure d'arbreet de forêt dans des domaines tels que les dossiers informatiques, l'ordrelexicographique, les hiérarchies d'un groupe social (famille, entreprise, . . .),des outils de résolution pour certains problèmes principalement informatiqueset mathématiques, . . .

Dé�nition 1.19. Une forêt est un graphe acyclique, c'est-à-dire un graphesans cycle. Un arbre est une forêt connexe.

Par conséquent, une forêt est un graphe dont ses composantes connexessont des arbres. Les sommets de degré 1 dans un arbre sont appelés feuilles.

Théorème 1.20. Soit T un graphe. Les assertions suivantes sont équiva-lentes :

(1) T est un arbre,

(2) toute paire de sommets de T est reliée par un unique chemin dans T ,

(3) T est connexe minimal, c'est-à-dire T est connexe mais T − e ne l'estplus pour toute arête e de T ,

12

(4) T est acyclique maximal, c'est-à-dire T ne contient aucun cycle maisT + uv en contient un pour toute paire de sommets u, v de T non-adjacents dans T .

Démonstration. (1)⇒ (4) Montrons que T + uv contient un cycle pourtous sommets u, v de T non-adjacents. Puisque T est connexe, il existeun chemin P dans T allant de u à v. Alors il su�t de considérer le cycleP + vu dans T + uv.

(4)⇒ (3) Soient u, v deux sommets de T . Si uv n'est pas une arête de Talors par hypothèse, T+uv contient un cycle C. Puisque T est acyclique,C passe par uv, disons C = uvx1 . . . xku. Le chemin P = vx1 . . . xkuest dans T et relie v à u. Donc T est connexe. Soit e = uv une arêtede T . Si T − e est connexe, alors il existe une chemin Q allant de u à vdans T − e, disons Q = uy1 . . . ymv. Dès lors le cycle C = uy1 . . . ymvuest dans T , ce qui est impossible par hypothèse.

(3)⇒ (2) Soient u, v deux sommets de T . Nous savons qu'il existe unchemin P dans T allant de u à v. Véri�ons que ce chemin est unique.Par l'absurde, supposons qu'il existe un autre chemin Q.Prenons C = c1 . . . ck un cycle dans P ∪ Q. Alors T − c1c2 n'est pasconnexe par hypothèse. Nous allons prouver le contraire pour obtenirune contradiction. Soient x, y deux sommets de T et R un chemin de xà y dans T . Si c1c2 appartient à R, disons R = r1 . . . riri+1ri+2ri+3 . . . rj,où r1 = x, ri+1 = c1, ri+2 = c2 et rj = y, alors prenons m ∈ {0, . . . , i}le plus grand entier tel que rl n'appartient pas à C pour 1 6 l 6 m etn ∈ {i+ 3, . . . j + 1} le plus petit entier tel que rl n'appartient pas à Cpour n 6 l 6 j. Posons p et q les entiers tels que cp = rm+1 et cq = rn−1.Comme la Figure 1.9 l'illustre, il su�t de considérer le chemin suivantr1 . . . rmcpcp−1 . . . cq+1cqrn . . . rj dans T − c1c2 allant de x à y.

(2)⇒ (1) Il su�t de véri�er que T n'a pas de cycle. Par l'absurde, si T aun cycle C = c1 . . . ckc1, alors T possède deux chemins di�érents pouraller de c1 à c2 : c1c2 ou c1ckck−1 . . . c2, ce qui est impossible.

Proposition 1.21. Tout graphe connexe contient un arbre couvrant.

Démonstration. Soit G un graphe connexe. Par équivalence des points (1) et(3) du Théorème 1.20, nous savons que tout sous-graphe connexe minimalcouvrant est un arbre couvrant. Il reste donc à montrer l'existence d'untel sous-graphe. Soit T un sous-graphe connexe minimal avec un nombremaximum de sommets. Si |T | < |G|, alors il existe un sommet v de G quin'appartient pas à T . Puisque G est connexe, il existe un T−v chemin P dansG. Alors T ∪ P est un sous-graphe connexe minimal avec plus de sommetsque T : contradiction.

13

r1 = xrm

cp = rm+1

c1

c2

cq = rn−1

rn

rj = y

cq+1

cp−1

R

C

Figure 1.9 � Le chemin R rencontrant le cycle C en au moins l'arête c1c2.

Exemple 1.22. Le sous-graphe du graphe connexe dans la Figure 1.5 est unarbre couvrant.

Proposition 1.23. Un graphe connexe avec n sommets est un arbre si etseulement si ce graphe a n− 1 arêtes.

Démonstration. (⇐) Soit G un graphe connexe avec n sommets et n − 1arêtes. Si n = 1, alors G est trivialement un arbre. Sinon n > 1 et utilisonsun argument par récurrence ; supposons que tout graphe connexe avec k < nsommets et k−1 arêtes est un arbre. Si tout sommet v est de degré au moins2 alors 2(n − 1) = 2‖G‖ =

∑v∈V d(v) > 2|G| = 2n, ce qui est impossible.

Dès lors, il existe un sommet v de degré 1. Par hypothèse d'induction, G− vest un arbre. D'où G est un arbre.(⇒) Soit G un arbre avec n sommets. Si n = 1 alors l'arbre n'a pas d'arêtes.Sinon n > 1. Puisque un arbre possède au moins une feuille v et qu'un arbresans une feuille reste un arbre, par hypothèse d'induction, nous obtenons que‖G‖ = ‖G− v‖+ 1 = n− 2 + 1 = n− 1.

Dans certains cas, nous pouvons �xer un sommet particulier, dit racine.Dans un arbre T avec une racine r, les sommets à une distance k de r ontune profondeur k et forment le kième niveau de T .

14

1.6 Contraction et mineur

Nous avons déjà vu les notions de sous-graphes et de sous-graphes in-duits. Dans cette section, nous allons en découvrir une nouvelle : le mineur.Préalablement, nous allons étudier un autre concept : la contraction d'unearête.

Soit e = xy une arête du graphe G = (V,E). Par G/e, nous notonsle graphe obtenu à partir de G par contraction de l'arête e en un nouveausommet ve qui est adjacent à tous les anciens voisins de x et de y.

Dé�nition 1.24. Le graphe G/e est un graphe (V ′, E ′) avec

V ′ = (V \ {x, y}) ∪ {ve} et

E ′ = {uv ∈ E|{u, v} ∩ {x, y} = ∅} ∪ {uve|ux ∈ E \ {e} ou uy ∈ E \ {e}},

où ve est un nouveau sommet, c'est-à-dire ve /∈ V ∪ E.

x

y

veG G/ee

Figure 1.10 � Contraction de l'arête e = xy dans le graphe G.

Dé�nition 1.25. Un graphe H est un mineur d'un autre graphe G si Hpeut être obtenu à partir de G en prenant d'abord un sous-graphe et ensuiteen contractant une suite �nie d'arêtes dans ce sous-graphe.

En d'autres mots, un mineur peut être obtenu à partir de G en appliquantun nombre �ni d'opérations parmi les suivantes : suppression d'un sommet,d'une arête et contraction d'une arête.

15

G

H

Figure 1.11 � Le graphe H est un mineur de G.

1.7 Quelques ensembles particuliers

Dans cette section, nous allons parcourir di�érents ensembles de sommetsou d'arêtes ayant des propriétés intéressantes.

1.7.1 Couplage

Intuitivement, un couplage est un ensemble d'arêtes qui permet d'attacherles sommets deux-à-deux. Donc un sommet est lié par le couplage à au plusun autre sommet.

Dé�nition 1.26. Un couplage d'un graphe est un ensemble d'arêtes indé-pendantes, c'est-à-dire un ensemble d'arêtes qui n'ont pas de sommets encommun.

Tout ensemble contenant une seule arête forme un couplage. Un couplage

maximum est un couplage contenant le plus grand nombre possible d'arêtes.Un couplage maximum n'est pas nécessairement unique.

Exemple 1.27. Dans le graphe de la Figure 1.12, nous avons au moins deuxcouplages maximums :

{x1x2, x3x4, x5x7, x6x8, x9x10, x11x12, x13x14}

et {x1x3, x2x4, x5x6, x7x8, x9x10, x11x13, x12x14}.

Ces ensembles de 7 arêtes sont bien maximums car le graphe est d'ordre 14.

Un couplage maximal est un couplage M du graphe véri�ant la propriétésuivante : toute arête du graphe possède une intersection non vide avec au

16

x1

x2 x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

x14

Figure 1.12 � Graphe contenant tous les di�érents types de couplage.

moins une arête de M , ou encore le couplage est maximal pour l'inclusion,c'est-à-dire si une arête quelconque deG−M est ajoutée àM , alors l'ensembleobtenu n'est plus un couplage.

Proposition 1.28. Un couplage maximum est un couplage maximal.

L'exemple suivant montre qu'un couplage maximal n'est pas nécessaire-ment maximum.

Exemple 1.29. Dans le graphe de la Figure 1.12, l'ensemble

{x2x4, x3x5, x6x8, x9x11, x12x13}

est un couplage maximal mais il ne forme pas un couplage maximum. Évi-demment, tout couplage maximum est maximal.

Un couplage parfait ou complet est un couplage du graphe tel que toutsommet du graphe est incident à exactement une arête du couplage. Parconséquent, si un graphe admet un couplage parfait avec n arêtes alors il estd'ordre 2n.

Proposition 1.30. Un couplage parfait est un couplage maximal et maxi-mum.

Cependant un couplage maximal ou maximum n'est pas obligatoirementparfait. Tout graphe d'ordre impair ne contient pas de couplage parfait. Parcontre, si un graphe est d'ordre pair, nous ne pouvons pas assurer l'existenced'un couplage parfait. L'exemple suivant illustre ces di�érentes nuances entrecouplages.

17

Exemple 1.31. Dans le graphe de la Figure 1.12, les couplages maximumsde l'Exemple 1.27 forment deux couplages parfaits. Le couplage maximal del'Exemple 1.29 n'est pas parfait car x1 n'est incident à aucune arête de cetensemble. Et dans le graphe de la Figure 1.13, l'arête ab forme un couplagemaximum. Ce graphe d'ordre pair ne possède pas de couplage complet.

a b

cd

Figure 1.13 � Graphe ne contenant pas de couplage parfait.

1.7.2 Couverture

Nous pouvons comprendre la notion de couverture par ce qui suit : unecouverture est un ensemble de sommets qui couvrent au moins une extrémitépour chaque arête du graphe. Dès lors, chaque arête du graphe a au moinsune de ses extrémités prise sous la couverture.

Dé�nition 1.32. Une couverture d'un graphe est un ensemble de sommetsC tel que chaque arête de G est incidente à au moins un sommet de C.L'ensemble C couvre les arêtes de G.

Pour un graphe donné, l'ensemble de tous ses sommets forme une cou-verture. Une couverture minimum est une couverture contenant le plus petitnombre possible de sommets. Certains graphes possèdent plusieurs couver-tures minimums, comme l'illustre l'exemple suivant.

Exemple 1.33. Dans le graphe de la Figure 1.14, les ensembles {a, c, e} et{b, c, d} forment deux couvertures minimums.

Proposition 1.34. Soit G = (V,E) un graphe. Un ensemble de sommets Uest une couverture si et seulement si son complémentaire V \U est un stable.

Par dé�nition de couplage maximal, les extrémités d'un tel couplageforment une couverture.

Lemme 1.35. Tout couplage a un nombre d'arêtes inférieur au nombre desommets de toute couverture.

18

a b

c

d

e

Figure 1.14 � Graphe contenant des couvertures minimums de taille 3.

Démonstration. Par l'absurde, supposons qu'il existe un couplage de n arêteset une couverture de m sommets avec n > m. Par dé�nition de couverture,pour chacune des n arêtes du couplage, une de ses extrémités est un des msommets de la couverture. Donc n extrémités (peut-être confondues) sontdans la couverture. Vu que ces n arêtes forment un couplage, toutes lesextrémités sont deux-à-deux distinctes. Dès lors, nous avons un ensemble de nextrémités di�érentes inclus dans l'ensemble desm sommets de la couverture.Or n > m, ce qui amène notre contradiction.

Une couverture minimum connexe d'un graphe connexe G est une cou-verture minimum C tel que le sous-graphe induit par C sur G est connexe.Le nombre de sommets d'une couverture minimum est, en général, plus petitou égal à celui d'une couverture minimum connexe.

Exemple 1.36. Dans le graphe de la Figure 1.14, la couverture minimum{a, c, e} est connexe mais ce n'est pas le cas de celle-ci : {a, c, d}. Pour legraphe de la Figure 1.15, la taille d'une couverture minimum, par exemple{a, e}, est strictement inférieure à celle d'une couverture minimum connexe.En e�et, une couverture minimum connexe contient 3 sommets. L'ensemble{a, b, e} en est un exemple.

1.7.3 Ensemble dominant

Un ensemble dominant est, de façon intuitive, un ensemble de sommetstel que tout sommet est dominé ou proche d'un sommet de cet ensemble.

Dé�nition 1.37. Un ensemble dominant d'un graphe G est un ensemble desommets D tel que tout sommet de G est soit un sommet de D, soit voisinà un sommet de D.

19

a

bcd

e

Figure 1.15 � Graphe ayant une couverture minimum de taille inférieure àcelle d'une couverture connexe.

L'ensemble de tous les sommets d'un graphe forme un ensemble dominant.Un ensemble dominant minimum est un ensemble dominant contenant leplus petit nombre possible de sommets. Un graphe peut posséder plusieursensembles dominants minimums. Un ensemble dominant minimum D d'ungraphe G est connexe si le graphe induit par D sur G est connexe. Commepour les couvertures, la taille d'un ensemble dominant minimum est majoréepar celle d'un ensemble dominant connexe.

Exemple 1.38. L'ensemble {x1, x4} du graphe représenté par la Figure 1.16est un ensemble dominant minimum qui n'est pas connexe. De plus, un en-semble dominant minimum connexe contient 4 sommets. L'ensemble conte-nant x1, x2, x3 et x4 est un ensemble dominant minimum connexe.

x1

x2

x3 x4

x5

x6

Figure 1.16 � Graphe ayant un ensemble dominant minimum de taille infé-rieure à celle d'un ensemble dominant connexe.

Proposition 1.39. Soit G = (V,E) un graphe connexe d'ordre supérieur à2. Il existe un ensemble dominant D ⊆ V tel que V \D soit aussi un ensembledominant.

Démonstration. Par la Proposition 1.21, nous savons qu'il existe un arbrecouvrant T dans G. Soit r un sommet de T considéré comme racine. Prenons

20

D l'ensemble de tous les sommets à une profondeur paire de r dans T . Cetensemble est clairement dominant et son complémentaire V \D, l'ensemblede tous les sommets à une profondeur impaire de r dans T , est aussi unensemble dominant.

Corollaire 1.40. Soit G un graphe connexe à n > 2 sommets. Un ensembledominant minimum a au plus

⌈n2

⌉sommets.

Démonstration. Par l'absurde, supposons que tout ensemble dominant a aumoins

⌈n2

⌉+ 1 sommets. Par la Proposition 1.39, il existe D un ensemble de

sommets sur G tel que D et V (G) \D sont deux ensembles dominants. Parhypothèse par l'absurde, D et V (G) \D contiennent tous les deux au moins⌈n2

⌉+ 1 sommets. Or

n = |V (G)| = |V (G) \D ∪D| = |V (G) \D|+ |D|.

Nous obtenons la contradiction suivante :

n > 2⌈n

2

⌉+ 2 > n.

Proposition 1.41. Soit G un graphe à n > 2 sommets. Un ensemble domi-nant contient au moins n

1+∆sommets où ∆ représente le degré maximum de

G.

Démonstration. Par l'absurde, supposons qu'un ensemble dominant a au plusn

1+∆−1 sommets. Puisqu'un sommet domine tout au plus ∆ autres sommets,

cet ensemble domine au plus ( n1+∆− 1)(1 + ∆) < n

1+∆(1 + ∆) = n, ce qui est

en contradiction avec la dé�nition d'ensemble dominant.

21

Chapitre 2

Complexité, algorithmes et

approximations

Ce chapitre est divisé en deux grandes sections : une première introduisantla complexité et di�érentes notions liées à celle-ci, et une seconde expliquantles algorithmes d'approximation.

2.1 Complexité

Dans cette section, nous allons rappeller la notion de complexité ainsique tous les outils liés à ce concept (problème algorithmique, classes de com-plexité, problèmes NP -complets, . . .), basés sur le cours de Calculabilité etComplexité donné par Bruyère à l'UMons, ainsi que sur les livres de Teu-scher [TH04], de Rozenberg et Salomaa [RS97], de Wolper [Pie], de Carton[Car08] et de Garey et Johnson [GJ+79]. Ensuite, nous nous attarderons surdi�érents problèmes.

2.1.1 Qu'est-ce que la complexité ?

La théorie de la complexité étudie et évalue la di�culté ou la complexitéd'une réponse par algorithme à un problème, dit algorithmique, posé de ma-nière mathématique. Pour cela, nous allons dé�nir trois concepts : problèmesalgorithmiques, réponses algorithmiques aux problèmes et complexité desproblèmes algorithmiques.

Dé�nition 2.1. Un problème algorithmique est un problème énoncé de ma-nière mathématique et comprenant des hypothèses, des données et une ques-tion.

22

Il existe deux sortes de problèmes :� les problèmes de décision : problème où la réponse attendue est � oui �ou � non �.

� les problèmes d'existence : problème qui questionne sur l'existence d'uncertain élément et dont la réponse consiste à fournir un tel élément.

Dé�nition 2.2. Un problème possède une réponse algorithmique si un al-gorithme peut calculer la réponse à ce problème.

Un problème est dit décidable si c'est un problème de décision et si saréponse peut être calculée par un algorithme. Parallèlement, un problème estdit calculable si c'est un problème d'existence et si un algorithme peut donnerl'élément recherché par ce problème. La théorie de la complexité se restreintaux problèmes décidables et calculables. Elle permet d'évaluer les ressourcesen temps et en espace mémoire utilisées pour obtenir algorithmiquement laréponse.

La théorie de la complexité cherche à connaître si la réponse à un pro-blème donné peut être fournie de façon très e�cace ou au contraire n'est pasatteignable en pratique. Il existe évidemment di�érents niveaux de di�cultéentre ces deux extrêmes, appelés classes de complexité. Pour pouvoir donnerune telle information, on se base sur une estimation théorique des temps decalcul et des besoins en mémoire informatique.

L'analyse de la complexité est inhérente à un modèle de calcul. L'undes modèles de calcul le plus courant est celui des machines de Turing. Unemachine de Turing fonctionne selon le procédé suivant : à chaque étape,pour un état donné de la mémoire de la machine, une action élémentaireest choisie dans un ensemble d'actions possibles. Les machines déterministes

sont celles où l'ensemble d'actions possibles est réduit à une seule tandis quepour les machines non déterministes, cet ensemble peut contenir plus d'uneaction ou aucune. Une machine de Turing permet de savoir si un mot sur uncertain alphabet appartient à un langage, c'est-à-dire un ensemble de motsparticuliers dé�nissant le problème. La machine de Turing a trois sortiesdi�érentes : un calcul acceptant, un calcul rejetant ou un calcul in�ni. Selonla sortie, nous pouvons peut-être déterminer si le mot appartient au langage.

Ce modèle de calcul est un précurseur des ordinateurs essayant de dé�nirle concept d'algorithme. Comme le détaille Teuscher [TH04, p. 77-81], AlanTuring, mathématicien britannique du début du 20ème siècle, fût le premierà développer un modèle abstrait et technique permettant de calculer ce dontl'homme en a les capacités. L'idée de Turing était simple : les opérationse�ectuées par une machine de Turing simulent, étapes par étapes, certainesopérations élémentaires. Cette découverte engendra de multiples questions,

23

comme par exemple : � Est-ce qu'une machine peut penser ? �. Selon Tu-ring, les machines peuvent peut-être penser mais elles ne sont pas meilleuresque les humains concernant les mathématiques, ou alors elles sont peut-êtremeilleures que les humains mais ne savent pas penser. Beaucoup de ces ques-tions restent encore ouvertes à l'heure actuelle. Nous ne pouvons parler dedé�nition d'algorithme sans citer la thèse de Church-Turing. En e�et, Rozen-berg et Salomaa [RS97, p. 14-15] nous expliquent que cette thèse considèreles machines de Turing comme formalisation de la notion d'algorithme.

Pour survoler la notion de calculabilité, nous allons parcourir les di�é-rentes classes de langages ainsi que quelques propriétés. On dit qu'un langageest récursivement énumérable s'il existe une machine de Turing calculant celangage. Cette machine ne s'arrête pas nécessairement. Par contre, un lan-gage est récursif s'il existe une machine de Turing qui s'arrête toujours etqui calcule ce langage. La classe des langages récursivement énumérables estnotée LRE et celle des langages récursifs LR. Tous les langages sont dans L.Nous avons que

LR ( LRE ( L.De plus, il existe certaines propositions concernant l'appartenance à une

classe. Wolper [Pie, p. 130-137] s'intéresse davantage à ces classes de langageset prouve ces di�érents résultats dans son ouvrage.

Proposition 2.3. Soient L un langage et LC son complémentaire.

L ∈ LR ⇔ LC ∈ LR.

L ∈ LR ⇔ L ∈ LRE et LC ∈ LRE.L ∈ LRE \ LR ⇒ LC ∈ L \ LRE.

Nous allons nous intéresser uniquement à la classe des langages récursifs,LR, et subdiviser cette classe en plusieurs sous-classes. Auparavant, nous al-lons éclairer la notion de complexité. La complexité d'une machine de Turingest donnée en fonction de la taille de l'entrée et évalue le temps nécessaireà la machine de Turing pour résoudre le problème. Ce temps est calculé ennombre de transitions sur la machine de Turing, en nombre d'opérations élé-mentaires e�ectuées et ce dans le pire des cas possibles. En général, ce tempsn'est pas une fonction précise mais un ordre de grandeur. Dès lors, la notionde grand O s'impose.

Dé�nition 2.4. Soient f, g deux fonctions de N dans R. On dit que f esten grand O de g, noté f(n) = O(g(n)) si

∃C > 0,∃N ∈ N,∀n > N, |f(n)| 6 C|g(n)|.

24

Intuitivement, cette notion signi�e que f ne croît pas plus vite que g, à unfacteur près. Par exemple, si f(n) = 2n2 + 1000n+ 1014 alors f est en grandO de n2. Si f est une fonction polynomiale de degré k alors f est en grandO de nk. En fonction de l'ordre de grandeur, nous avons di�érents types decomplexité :

� O(1) : complexité constante, indépendante de la taille des données,� O(log(n)) : complexité logarithmique,� O(n) : complexité linéaire,� O(n log(n)) : complexité quasi-linéaire,� O(n2) : complexité quadratique,� O(n3) : complexité cubique,� O(nk) : complexité polynomiale,� O(2n) : complexité exponentielle,� O(n!) : complexité factorielle.

2.1.2 Quelques classes de complexité

Les deux grandes classes de complexité selon le temps, ainsi que les classessuivantes, sont détaillées dans le cours de Calculabilité et Complexité deBruyère. Nous n'abordons pas la complexité en espace.

La classe TIME

La classe TIME(t(n)) est l'ensemble des langages récursifs L tels qu'ilexiste une machine de Turing déterministe calculant L et de complexité entemps O(t(n)).

La classe NTIME

La classse NTIME(t(n)) est l'ensemble des langages récursifs L tels qu'ilexiste une machine de Turing non déterministe calculant L et de complexitéen temps O(t(n)).

De plus, nous allons discuter de trois grandes classes importantes :

La classe P

La classe P reprend les langages récursifs pouvant être calculés par unemachine de Turing déterministe en temps polynomial, c'est-à-dire

P =⋃k>0

TIME(nk).

25

La classe NP

La classe NP est la version non déterministe de la classe P , c'est-à-dire

NP =⋃k>0

NTIME(nk).

Intuitivement, cette classe contient les langages récursifs pour lesquels il estpossible de véri�er par une machine déterministe en un temps polynomial siun mot appartient à ce langage. Mais il faut bien comprendre que, jusqu'àprésent, nous n'avons trouvé aucune machine déterministe pouvant calculerun langage de la classe NP en un temps polynomial.

La classe EXPTIME

La classe EXPTIME rassemble les langages récursifs L tels qu'il existeune machine de Turing déterministe calculant L et avec un temps de calculexponentiel, c'est-à-dire

EXPTIME =⋃k>0

TIME(2nk

).

2.1.3 Relations entre les di�érentes classes

Puisque toute machine de Turing déterministe est une machine non dé-terministe, il est clair que P ⊆ NP . Par le théorème suivant, déduit du livrede Wolper [Pie, p. 167], nous pouvons conclure que NP ⊆ EXPTIME.

Théorème 2.5. Soit M une machine de Turing non déterministe polyno-miale. On peut construire une machine de Turing déterministe acceptant lemême langage que celui de M et ayant une complexité en O(2p(n)) où p(n)est un polynôme.

Une des grandes questions ouvertes à ce jour est : est-ce que P = NP ?Nous avons l'impression que P 6= NP mais, jusqu'à présent, aucune preuvedémontrant cette inégalité n'a encore vu le jour. Par contre, nous savonsque P ( EXPTIME. En e�et, l'argument essentiel à cette inclusion stricteréside dans le Théorème de hiérarchie que nous pouvons retrouver dans lelivre de Carton [Car08, p. 217-218].

2.1.4 Théorème de Cook-Levin et problèmes NP -com-plets

Nous allons découvrir le célèbre théorème de Cook-Levin ainsi que lesdi�érents concepts qui en découlent. Garey et Johnson [GJ+79, p. 34-44] y

26

P NP EXPTIME LR LRE L

Figure 2.1 � Diagramme des di�érentes classes de langages.

consacrent deux sections dans leur livre, ce qui con�rme l'importance de cethéorème. En e�et, celui-ci est fondamental dans la théorie de la complexitédes algorithmes. Cook l'a démontré en 1971 dans un article intitulé � TheComplexity of Theorem Proving Procedures � [Coo71]. Nous appelons cethéorème � théorème de Cook-Levin � car il a été démontré par Levin sensi-blement à la même époque. Pour comprendre la structure de la preuve de cethéorème, dé�nissons un problème de décision particulier : le Problème SAT .Le langage associé à ce problème est l'ensemble de toutes les formules boo-léennes satisfaisables, c'est-à-dire des formules booléennes telles qu'il existeune assignation des variables de la formule qui la rend vraie. Par exemple, laformule booléenne

φ = (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x1)

est satisfaisable par l'assignation x1 = vrai, x2 = faux, x3 = vrai. Par contre,aucune assignation ne rend vraie la formule suivante :

φ′ = (x1 ∨x2 ∨x3)∧ (¬x1 ∨x2)∧ (¬x2 ∨x3)∧ (¬x3 ∨x1)∧ (¬x1 ∨¬x2 ∨¬x3).

Théorème 2.6 (Théorème de Cook-Levin). Si SAT appartient à P alorsP = NP .

Pour comprendre la structure de la preuve du théorème de Cook-Levin,nous allons dé�nir deux nouveaux concepts. Tout d'abord, certains langagesrécursifs ont une relation particulière entre eux : un langage peut se réduirede façon polynomiale à un autre.

Dé�nition 2.7. Soient L1, L2 deux langages récursifs. On dit que L1 se réduit

de façon polynomiale à L2, noté L1 6p L2, s'il existe une machine de Turingdéterministe C, appelée convertisseur, qui calcule en temps polynomial unefonction f telle que ω ∈ L1 ⇔ f(ω) ∈ L2.

27

Grâce à cette relation entre langages, la proposition suivante nous assureque si un langage se réduit de façon polynomiale à un autre et si cet autreest dans P , alors le premier langage est aussi dans P .

Proposition 2.8. Soit L1, L2 deux langages récursifs. Si L1 6p L2 et siL2 ∈ P alors L1 ∈ P .

Ensuite, la deuxième notion pour expliquer la structure du théorème deCook-Levin est le langage NP -complet.

Dé�nition 2.9. Un langage L est NP -complet si L est NP -facile, c'est-à-dire L ∈ NP , et si L est NP -di�cile, c'est-à-dire ∀L′ ∈ NP,L′ 6p L.

Intuitivement, un langage est NP -complet s'il est dans NP et s'il est aumoins aussi di�cile que n'importe quel autre langage de NP . On a l'impres-sion que les langages NP -complets sont les plus di�ciles de la classe NP . Laproposition suivante, qui est un élément clé dans le théorème de Cook-Levin,généralise celui-ci.

Proposition 2.10. Soit L un langage récursif. Si L est NP -complet et si Lest dans P alors P = NP .

Cette proposition est assez importante par sa signi�cation : il su�t demontrer qu'un seul langage NP -complet est dans P pour montrer que tousles langages de NP sont dans P . En fait, le théorème de Cook-Levin montreque SAT est NP -complet et conclut par la proposition précédente.

Montrer qu'un langage est NP -complet n'est pas une tâche facile. C'estpourquoi la proposition suivante a toute son utilité.

Proposition 2.11. Soient L1, L2 deux langages récursifs. Si L1 est NP -complet, si L2 est dans NP et si L1 6p L2 alors L2 est aussi NP -complet.

Jusqu'à présent, nous avons principalement parlé de langages mais, enpratique, nous parlerons essentiellement de problèmes de décision. En fait,nous avons une équivalence entre ces deux notions. Un langage forme exac-tement les mots sur un certain alphabet qui répond � oui � à un problèmede décision. De tout problème de décision, nous pouvons extraire un langagecorrespondant.

2.1.5 Quelques problèmes NP -complets

Nous allons étudier la NP -complétude de deux problèmes formant la basede ce mémoire. Pour montrer qu'un problème est NP -complet, il est néces-saire de prouver qu'il appartient à NP . Pour cela, nous avons vu qu'il faut

28

trouver une machine de Turing non déterministe calculant le langage corres-pond au problème et e�ectuant sa tâche en temps polynomial. En pratique, ilsu�t de trouver un algorithme non déterministe de complexité polynomiale.

Le Problème de Couverture

Le Problème de Couverture, noté V C (pour Vertex Cover), est dé�nicomme suit : pour un graphe connexe donné G et un entier k 6 |G|, nousdésirons savoir si G possède une couverture de taille au plus k.

Théorème 2.12. Le Problème V C est NP -complet.

Garey et Johnson [GJ+79, p. 53-56] démontrent exactement cette asser-tion.

Le Problème de l'Ensemble Dominant

Parallèlement au Problème de Couverture, le Problème de l'EnsembleDominant, noté DS (pour Dominating Set), s'intéresse à l'existence dans ungraphe connexe G d'un ensemble dominant de taille au plus k 6 |G|.

Théorème 2.13. Le Problème DS est NP -complet.

Démonstration. Il su�t de prendre l'Algorithme 1 non déterministe de com-plexité polynomiale pour montrer que DS est dans NP .

Cet algorithme devine un ensemble de sommets de taille au plus k et véri-�e que tout sommet de G est soit dans l'ensemble, soit voisin à un sommet decet ensemble. Le Problème DS est NP -di�cile. En e�et, par la Proposition2.11, il su�t de montrer que V C se réduit polynomialement à DS. Considé-rons le convertisseur donné par l'Algorithme 2, prenant en entrées un grapheconnexe G et un entier k et retournant G′, un graphe, et un entier k′.

Le graphe G′, solution du convertisseur, est donc construit à partir de Gauquel on ajoute des sommets correspondants aux arêtes de G et chacun deces sommets est voisin dans G′ aux extrémités de l'arête qu'il représente dansG (cf. Figure 2.2). Cet algorithme est clairement déterministe et polynomial.Il reste à véri�er l'équivalence suivante :

(G, k) ∈ LV C ⇔ (G′, k′) ∈ LDS.

(⇒) Supposons que G a une couverture C de taille au plus k. Véri�onsque C forme un ensemble dominant dans G′. Soit v ∈ V (G′). Siv ∈ V (G) alors v admet un voisin u dans G, c'est-à-dire uv ∈ E(G).Puisque C est une couverture, soit u, soit v est dans C. Donc v est cou-vert par C. Si v ∈ E(G) alors v = uw. Parce que C est une couverture,

29

Algorithme 1: Algorithme d'ensemble dominantEntrées : G graphe connexe, k 6 |G| un entierSortie : Vrai si et seulement si G contient un ensemble dominant de

taille au plus k

début

ds←− faux ;Soit D un ensemble de sommets de G de taille 6 k ;pour tous les sommets v de G faire

si v /∈ D alors

pour tous les voisins u de v fairesi u ∈ D alors

ds←− vrai ;�n

�n

si ¬ds alorsretourner faux ;

�n

ds←− faux ;�n

�n

retourner vrai ;�n

Algorithme 2: Convertisseur V C 6p DS

Entrées : G graphe connexe, k 6 |G| un entierSorties : G′ graphe connexe, k′ un entier

début

k′ ←− k ;V (G′)←− V (G) ∪ E(G) ;E(G′)←− E(G) ∪ {(u, e) ∈ V (G)× E(G)|u ∈ e} ;retourner (G′, k′);

�n

30

a b

cd

a b

cd

ab

bc

cd

ad

acG G′

Figure 2.2 � Un graphe G et le graphe G′ obtenu à partir de G par leconvertisseur de l'algorithme 2.

soit u, soit w est dans C. Puisque v est voisin de u et de w dans G′, vest couvert par C.

(⇐) Soit G′ le graphe obtenu par le convertisseur à partir d'un grapheconnexe G et un entier k 6 |G|. Supposons que G′ possède un ensembledominant D de taille au plus k. Prenons f une fonction de E(G) dansV (G) dé�nie par

f(uv) =

{u si u /∈ Dv sinon.

Posons C = {v ∈ D|v ∈ V (G)} ∪ {f(e) ∈ V (G)|e ∈ D ∩ E(G)}.Véri�ons que C est une couverture. Soit e = uv ∈ E(G). Si e appartientà D alors soit u, soit v appartient à C par dé�nition de f . Sinon e,sommet de G′, est voisin dans G′ d'un élément de l'ensemble dominantD, disons u. Puisque les voisins de e dans G′ sont des sommets de G,alors u appartient à C.

2.1.6 Interprétation de la NP -complétude

Sous l'hypothèse que P 6= NP , si nous cherchons une solution algorith-mique pour un problème NP -complet, alors ce problème ne possède pas desolution algorithmique polynomiale (par la contraposée de la Proposition2.10). Est-ce une raison pour renoncer dé�nitivement à résoudre ce problème

31

par un algorithme ? Les quelques arguments suivants, suggérés par Wolper[Pie, p. 184], nous montrent que ce n'est pas forcément le cas.

� La complexité d'un algorithme se base sur le pire des cas possibles. Dèslors, l'absence d'un algorithme polynomial se traduit par l'absence d'unalgorithme dont toutes les instances du problèmes se calculent en untemps polynomial. Il se peut pourtant qu'il existe un algorithme dontle comportement est polynomial dans 99% des cas.

� En général, on trouve une solution à un problèmeNP -complet en explo-rant un nombre exponentiel de cas possibles. Pour limiter ce nombre,on utilise des heuristiques, algorithmes fournissant en temps polyno-mial une solution réalisable, pas nécessairement optimale. Donc, au lieud'énumérer systématiquement toutes les possibilités, on utilise des cri-tères approximatifs pour découvrir plus rapidement une solution recher-chée. La théorie de la NP -complétude nous enseigne que de telles mé-thodes heuristiques ne peuvent pas toujours donner de bons résultats.Cependant, rien n'exclut une certaine e�cacité pour de nombreusesinstances du problème.

� Dans le cas d'un problème d'optimisation NP -complet, on peut secontenter d'une solution approximative, c'est-à-dire qu'au lieu de cher-cher la solution optimale, on peut rechercher une solution proche del'optimum. Il existe des problèmes d'optimisation NP -complets pourlesquels il y a des algorithmes polynomiaux calculant une solution quine di�ère de la solution optimale que d'un facteur. Nous allons, dans lasection suivante, approfondir ce concept d'algorithme d'approximation.

2.2 Algorithmes et approximations

Dans cette section, nous allons étudier le principe des algorithmes d'ap-proximation résolvant des problèmes d'optimisation NP -complets, pour les-quels tous les algorithmes exacts connus à ce jour sont de complexité expo-nentielle.

Rappelons les di�érentes données d'un problème d'optimisation P . Voicileur signi�cation :

� IP l'ensemble des instances du problème,� SolP (x) l'ensemble des solutions admissibles pour une instance x,� CP (x, y) une fonction de coût à optimiser, c'est-à-dire minimiser oumaximiser, qui dépend d'une instance x et d'une solution admissible y,

� OPTP (x) le coût d'une solution optimale.Pour mieux comprendre les di�érents outils utilisés, nous allons les dé�nir

pour le Problème de l'Ensemble Dominant.

32

� IDS = {G = (V,E)|G est un graphe},� SolDS(G) = {U ⊆ V |U est un ensemble dominant},� CDS(G,U) = |U |.

Le Problème de l'Ensemble Dominant vise à trouver la cardinalité minimaled'un ensemble dominant dans un graphe. Par conséquent, nous cherchons àminimiser la fonction de coût.

2.2.1 Qu'est-ce qu'un algorithme d'approximation ?

Cette partie du mémoire est basée sur le livre de Ausiello, Crescenzi,Gambosi, Kann, Marchetti-Spaccamela et de Protasi [ACG+99, p. 87-91].

Dé�nition 2.14. Un algorithme d'approximation est une heuristique, decomplexité polynomiale, garantissant la qualité de la solution obtenue pourune instance donnée et un problème d'optimisation, c'est-à-dire une solutionproche d'une solution optimale, et ce pour toutes les instances possibles duproblème.

En d'autres mots, un algorithme d'approximation est un algorithme decomplexité polynomiale, moins coûteuse que l'exponentielle, dont la solutionvéri�e certaines conditions selon le cas du problème d'optimisation et la mé-thode d'évaluation de la qualité d'une solution. Il existe di�érents procédéspour évaluer la qualité d'une solution d'un problème d'optimisation. Nous al-lons en aborder deux. La première méthode est la plus intuitive. Discutons-enen fonction du problème d'optimisation.

Pour toute instance x d'un problème P de minimisation, si y∗ est unesolution optimale et y celle donnée par l'algorithme d'approximation alorsCP (x, y) 6 αCP (x, y∗) pour α > 1. La borne α, qui majore CP (x,y)

CP (x,y∗), peut

être une constante mais aussi une fonction dépendante de paramètres de l'ins-tance, comme par exemple, dans le cas des graphes, du nombre de sommets oudu degré maximum du graphe. Parallèlement, pour une instance x d'un pro-blème P de maximisation et pour les mêmes solutions y∗ et y que précédem-ment, on aura CP (x, y) > 1

αCP (x, y∗) pour α > 1 dépendant éventuellement

des paramètres de l'instance. La borne α est appelée facteur d'approximation.De plus, un algorithme d'approximation avec un facteur d'approximation αest dit algorithme α-approché. Un problème est α-approximable s'il existeun algorithme d'approximation résolvant ce problème où son facteur d'ap-proximation vaut α. L'idéal est de trouver des algorithmes d'approximationavec un facteur d'approximation proche de 1, c'est-à-dire des algorithmes peucoûteux donnant une solution très proche de l'optimale.

Nous pouvons voir de manière plus formelle ce procédé d'évaluation d'unesolution. Pour cela, dé�nissons le rapport de performance.

33

Dé�nition 2.15. Soient P un problème d'optimisation, x ∈ IP , y ∈ SolP (x).Le rapport de performance de y selon x est dé�ni par

RP (x, y) = max

(CP (x, y)

OPTP (x),OPTP (x)

CP (x, y)

).

La dé�nition suivante exprime exactement ce que nous avons vu ci-dessusmais de façon beaucoup plus rigoureuse et mathématique.

Dé�nition 2.16. Soient P un problème d'optimisation et A un algorithmed'approximation pour P . On dit que A est un algorithme r-approché pourP , avec r > 1 si, pour toute instance x ∈ IP , le rapport de performance dela solution approchée A(x) est borné par r, c'est-à-dire

RP (x,A(x)) 6 r.

S'il existe un tel algorithme pour le problème P alors on dit que P est r-approximable.

Une autre méthode d'évaluation de la qualité d'une solution pour unproblème d'optimisation est de faire appel à l'erreur relative.

Dé�nition 2.17. Soient P un problème d'optimisation, une instance x ∈ IPet une solution admissible y ∈ SolP (x) de x. L'erreur relative de y selon xest dé�nie par

εrP (x, y) =|OPTP (x)− CP (x, y)|

OPTP (x).

En fait, l'erreur relative d'une solution y de x vaut 0 si y est une solutionoptimale. Si une solution admissible est pauvre, alors son erreur relative estgrande dans le cas d'une minimisation et, dans le cas d'une maximisation,est proche de 1.

Comme pour le rapport de performance, il est intéressant de considérer lessituations pour lesquelles la mesure de qualité que peut être l'erreur relativeest bornée pour toutes les instances possibles.

Dé�nition 2.18. Soient P un problème d'optimisation et A un algorithmed'approximation pour P . On dit que A est un algorithme d'approximation

d'erreur relative ε pour P si, pour toute instance x ∈ IP , l'erreur relativede la solution approchée A(x) fournie par l'algorithme A est bornée par ε,c'est-à-dire

εrP (x,A(x)) 6 ε.

34

Clairement, le rapport de performance et l'erreur relative sont étroitementliés. En e�et, dans le cas d'une maximisation, l'erreur relative d'une solutiony sur une instance x est égale à εrP (x, y) = 1 − 1

RP (x,y). Tandis que dans le

cas d'une minimisation, nous avons εrP (x, y) = RP (x, y) − 1. Dès lors, nouspouvons facilement calculer le rapport de performance à partir de l'erreurrelative et vice versa. En général, nous utiliserons le rapport de performancepour exprimer le caractère d'approximabilité relative d'un problème.

Nous voyons un dernier procédé d'évaluation de la qualité d'une solutionpour un problème d'optimisation. Celui-ci, moins souvent utilisé, nous donneune information sur l'approximabilité absolue.

Dé�nition 2.19. Soient P un problème d'optimisation, une instance x ∈ IPet une solution admissible y ∈ SolP (x) de x. L'erreur absolue de y selon xest dé�nie par

AbsP (x, y) = |OPTP (x)− CP (x, y)|.

Parallèlement aux deux autres méthodes d'évaluation, nous dé�nissonsun algorithme et un problème d'optimisation selon son erreur absolue.

Dé�nition 2.20. Soient P un problème d'optimisation et A un algorithmed'approximation pour P . On dit que A est un algorithme d'approximation

d'erreur absolue δ pour P si, pour toute instance x ∈ IP , l'erreur absoluede la solution approchée A(x) fournie par l'algorithme A est bornée par δ,c'est-à-dire

AbsP (x,A(x)) 6 δ.

2.2.2 Le Problème de Couverture

Nous allons découvrir di�érents algorithmes d'approximation pour le Pro-blème de Couverture, appelé aussi Vertex Cover et noté V C. Nous avons déjàvu que le Problème de Couverture est NP -complet. De plus, nous allons nousintéresser aux algorithmes d'approximation pour sa version connexe, appeléeConnected Vertex Cover (CV C). Ces deux problèmes ont été dé�nis dans leChapitre 1.

Algorithme Couverture-Couplage

L'algorithme Couverture-Couplage est présenté dans le livre de Vazirani[Vaz04, p. 1-3].

Théorème 2.21. Le Problème V C est un problème de minimisation 2-ap-proximable par l'Algorithme 3.

35

Algorithme 3: Algorithme Couverture-CouplageEntrée : un graphe connexe G = (V,E)Sortie : une couverture C

début

H ←− G ;C ←− ∅ ;tant que ‖H‖ > 1 faire

choisir une arête uv de H au hasard ;C ←− C ∪ {u, v} ;poser H le sous-graphe induit par V (H) \ {u, v} ;

�n

retourner C ;�n

Démonstration. L'Algorithme 3 s'arrête toujours car le graphe G possède unnombre �ni d'arêtes. De plus, la solution renvoyée forme bien une couverturecar à chaque étape, nous enlevons uniquement toutes les arêtes incidentes auxdeux extrémités de l'arête choisie. Par conséquent, les arêtes choisies à chaqueétape dans l'algorithme forment un couplage maximal. Par le Lemme 1.35,nous déduisons que tout couplage maximal a un nombre d'arêtes inférieur aunombre minimum de sommets d'une couverture. Dès lors, si k représente lenombre d'arêtes choisies par l'algorithme et si s′ est la taille minimum d'unecouverture dans G alors k 6 s′, c'est-à-dire 2k 6 2s′. Puisque l'algorithme asélectionné k arêtes, la couverture retournée contiendra les deux extrémitésde chaque arête, à savoir 2k sommets. Donc s 6 2s′ où s est le nombre desommets de la couverture fournie par l'algorithme. Cette dernière inégalitéprouve bien que le Problème de Couverture est 2-approximable.

Les Figures 2.3 et 2.4 illustrent l'application de l'Algorithme 3 sur unexemple.

Cardinal et Levy [CL08] nous expliquent les di�érents algorithmes d'approxi-mation dans les deux sections suivantes.

Algorithme de Savage

Savage [Sav82] a montré que V C est 2-approximable par un autre algo-rithme que celui présenté dans la section précédente.

36

x1x2

x3

x4

x5 x6 x7

x8

x9

x3

x4

x5 x6 x7

x8

x9

G

Sélection de l'arête x1x2 ;C = {x1, x2}

et suppression de x1 et x2.

Sélection de l'arête x3x4 ;C = {x1, x2, x3, x4}

et suppression de x3 et x4.

Figure 2.3 � Application de l'Algorithme 3 sur le grapheG (première partie).

Théorème 2.22. Le Problème V C est 2-approximable par l'algorithme deSavage.

Démonstration. Expliquons l'algorithme de Savage. On construit un arbrecouvrant T à partir d'un graphe G de la manière suivante. Initialement,considérons un sommet v0 de G. Ensuite, on part d'un sommet v de G, qui àla première étape sera v0, et on considère un voisin u de v dans G. Si celui-cin'a pas encore été visité, u sera le �ls de v dans T et on itère en prenant ucomme sommet de départ. Si tous les voisins de v ont été visités, alors onconsidère un autre voisin non visité du père de v. Cette démarche s'appellele parcours en profondeur. Savage nous dit que les sommets internes, c'est-à-dire ceux qui ne sont pas des feuilles, de l'arbre couvrant T fournissent une2-approximation pour V C. Notons cet ensemble I. Tout d'abord, remarquonsque cette solution est bien une couverture dans G car la particularité duparcours en profondeur est la non-existence d'arête de G entre deux feuillesde T . Ensuite, véri�ons que la cardinalité d'un tel ensemble est majoréepar le double d'une couverture minimale de G. Rappelons le Lemme 1.35 :

37

x5 x6 x7

x8

x9

x5

x8

x9

Sélection de l'arête x6x7 ;C = {x1, x2, x3, x4, x6, x7}et suppression de x6 et x7.

Fin de l'algorithme,C = {x1, x2, x3, x4, x6, x7}.

Figure 2.4 � Application de l'Algorithme 3 sur le graphe G (seconde partie).

la taille d'un couplage est majorée par celle d'une couverture. Nous allonsmontrer l'existence d'un couplage de taille supérieure à |I|

2dans T , ce qui

su�ra à démontrer la 2-approximation car toute couverture de G est aussicouverture dans T . Pour chaque u ∈ I, prenons eu une arête de u vers unde ses �ls dans T . Ces arêtes sont distinctes et il y en a exactement |I|.Séparons M ′ = {eu|u ∈ I} en deux ensembles MA et MB tels que MA et MB

sont des couplages et par conséquent, l'un d'eux aura la taille exigée. PosonsA = {w ∈ T |dT (v0, w) est paire} et B = {w ∈ T |dT (v0, w) est impaire}. Ilsu�t de prendreMA = {eu|u ∈ I∩A} etMB = {eu|u ∈ I∩B} pour terminerla preuve.

Nous avons vu que le facteur d'approximation peut dépendre de certainsparamètres des instances. Dans ce cas-ci, ce rapport peut être dé�ni sur labase du nombre d'arêtes m ou du degré minimum δ. En général, ces facteurssont normalisés, en particulier, m∗ = m

n(n−1)2

et δ∗ = δn. Actuellement, les

meilleurs facteurs paramétrisés avec m∗ et δ∗ pour V C sont 22−√

1−m∗ et2

1+δ∗

[KZ98], lorsqu'un seul paramètre est pris en compte.Remarquons que l'ensemble I dé�ni dans l'algorithme de Savage induit

un sous-graphe connexe. Puisque la taille minimale d'une couverture connexe

38

est minorée par celle d'une couverture minimum, cet algorithme nous donneaussi une 2-approximation du Problème de CV C. Étudions le facteur d'ap-proximation du Problème de CV C.

Des résultats récents [FM09] montrent que le Problème de CV C est NP -complet à approximer avec un facteur constant plus petit que

10√

5− 21 ≈ 1, 36.

Nous allons découvrir que l'algorithme proposé par Savage possède enréalité un meilleur facteur d'approximation que 2 pour CV C pour des famillesparticulières de graphes. Pour cela, nous utiliserons les notations suivantes :OPT ∗V C = OPTV C

n, OPT ∗CV C = OPTCV C

n,m∗ = m

n(n−1)/2, δ∗ = δ

n, α∗ = α

n, où α

représente la taille du plus grand stable. Démontrons le lemme suivant.

Lemme 2.23. Nous avons les inégalités suivantes :

OPT ∗CV C > 1−√

1−m∗ +O

(1

n

),

OPT ∗CV C > δ∗.

Démonstration. Véri�ons la première inégalité. Puisqu'il manque au moinsα(α−1)

2arêtes dans un graphe, nous en avons au plus n(n−1)

2− α(α−1)

2. Par

conséquent, m∗ 6 1− α∗2 +O( 1n). En isolant α∗, nous obtenons

α∗ 6√

1−m∗ +O(1

n).

Par ailleurs, le complémentaire d'une couverture est un stable et récipro-quement. Dès lors, nous avons OPT ∗V C = 1 − α∗ et en remplaçant dans ladernière inégalité, nous obtenons OPT ∗V C > 1 −

√1−m∗ + O( 1

n). Et nous

obtenons le résultat voulu car OPTCV C > OPTV C . Pour la seconde inégalité,nous savons qu'un sommet dans un stable maximum possède au plus n− αvoisins. Par conséquent, δ 6 n − α = OPTV C , d'où OPT ∗V C > δ∗. PuisqueOPTCV C > OPTV C , nous obtenons la dernière inégalité.

Nous pouvons immédiatement déduire la borne supérieure du facteurd'approximation pour l'algorithme de Savage.

Théorème 2.24. L'algorithme de Savage approxime CV C avec un facteurde {

2 si m∗ < 34

+ o(1)1

1−√

1−m∗ + o(1) sinon

et de {2 si δ∗ < 1

2+ o(1)

1δ∗

+ o(1) sinon

39

Démonstration. Puisque nous connaissons déjà le facteur 2 de l'algorithmede Savage et que la valeur n−1 est le pire cas possible donné comme solutionpar l'heuristique, nous avons trivialement comme facteur

min

{2,

n− 1

OPTCV C

}=

{2 si OPT ∗CV C <

n2

n−1OPTCV C

sinon

En d'autres mots, nous avons le facteur suivant : min{

2, 1OPT ∗CV C+O( 1

n)

}. Nous

déduisons des deux inégalités du lemme précédent :

1

OPT ∗CV C6

1

1−√

1−m∗ +O( 1n)

=1

1−√

1−m∗+ o(1),

1

OPT ∗CV C6

1

δ∗ +O( 1n)

=1

δ∗+ o(1).

Il nous su�t de calculer dans quels cas le minimum vaut 2 :

1

1−√

1−m∗+ o(1) > 2⇔ m∗ <

3

4+ o(1),

1

δ∗+ o(1) > 2⇔ δ∗ <

1

2+ o(1).

Nous allons maintenant montrer la qualité de ces facteurs. En e�et, nousallons trouver une famille de graphes pour laquelle le rapport entre le pire caspossible d'une solution de l'algorithme de Savage avec l'optimum est prochede la borne donnée par le Théorème 2.24. Nous dé�nissons le graphe fenducomplet, noté ψn,α, comme le joint d'une clique Kn−α et d'un stable de αsommets. Le joint entre deux graphes est l'union disjointe de ces graphes àlaquelle nous ajoutons toutes les arêtes entre un sommet du premier grapheet un du second. La Figure 2.5 représente le graphe fendu complet ψ5,2.

Avant de montrer la qualité de la borne du Théorème 2.24, nous allonsdémontrer le lemme suivant.

Lemme 2.25. Soit H une solution dans le pire cas possible donnée par l'al-gorithme de Savage. Alors

|H(ψn,α)| ={n− 1 si α < n

2

2(n− α) sinon

40

Figure 2.5 � ψ5,2 le graphe fendu complet.

Démonstration. Discutons en fonction de α. Supposons α < n2. Une exécution

possible de l'algorithme est de partir d'un sommet de la clique, de prendrealternativement un sommet du stable et un de la clique, et de terminer parprendre les sommets nécessaires dans la clique. Cette exécution donnera unchemin de n sommets, d'où la solution sera de taille n − 1, en supprimantle dernier sommet. Maintenant, supposons que α > n

2. La pire exécution

possible de l'algorithme commence par un sommet du stable, prend succes-sivement un sommet de la clique et un du stable, ce qui induit un chemin de2(n− α) + 1 sommets. Donc la solution est de taille 2(n− α).

Théorème 2.26. Les bornes du Théorème 2.24 sont atteintes.

Démonstration. Il est clair que OPTV C(ψn,α) = n−α et que la solution opti-male correspondante est la clique Kn−α. Puisque cette solution est connexe,nous avons OPTCV C(ψn,α) = OPTV C(ψn,α) = n− α. En combinant ce résul-tat avec celui du lemme précédent, nous obtenons :

H(ψn,α)

OPTCV C(ψn,α)=

{2 si α > n

2n−1n−α sinon

=

{2 si OPT ∗CV C <

12

+ o(1)1

OPT ∗CV C+O( 1n

)sinon

Puisqu'il manque exactement α(α−1)2

arêtes dans ψn,α, nous avons

m(ψn,α) =n(n− 1)

2− α(α− 1)

2.

41

En isolant α et en normalisant, nous obtenons α∗(ψn,α) =√

1−m∗ + O( 1n).

Finalement, en remplaçant OPT ∗CV C = 1−α∗ = 1−√

1−m∗+O( 1n) dans la

borne ci-dessus, nous obtenons le résultat voulu. De plus, il est facile de voirque δ(ψn,α) = n− α = OPTCV C . Donc, en subsituant OPT ∗CV C = δ∗ dans laborne ci-dessus, le résultat souhaité en découle directement.

Remarquons que cet algorithme est de complexité O(m), donc en O(n2).Dans la prochaine section, nous améliorerons le facteur d'approximation audétriment de la complexité.

Une variante de l'algorithme de Karpinski et de Zelikovsky

Karpinski et Zelikovsky [KZ98] proposent deux algorithmes d'approxi-mation qui assurent un facteur d'approximation asymptotique de 2

1+δ∗et

22−√

1−m∗ respectivement. Cependant, ces algorithmes ne retournent jamais desolutions connexes. Levy [Lev09] propose deux variantes de leurs algorithmespour CV C, avec les mêmes facteurs d'approximation asymptotiques.

Avant de découvrir les algorithmes d'approximation, nous allons démon-trer un lemme technique.

Lemme 2.27. Toute solution H de CV C, constituée� d'un ensemble H1, sous-ensemble d'une solution optimale à CV C detaille ε1n,

� d'une 2-approximation H2 de CV C dans G[V − H1] obtenue par l'al-gorithme de Savage et

� d'un dernier ensemble H3 de ε2n sommets, avec |H1| > |H3|,approxime CV C avec un rapport de 2

1+ε1−ε2 .

Démonstration. Calculons le facteur d'approximation :

|H|OPTCV C

=|H1|+ |H2|+ |H3||H1|+ |OPT ′CV C |

où OPT ′CV C est une solution optimale �xée de CV C à laquelle nous avonsretiré H1. Remarquons que OPT ′CV C est une couverture de G[V − H1] etque H2 est une 2-approximation de V C dans G[V −H1] car l'algorithme deSavage est aussi une 2-approximation pour V C. D'où,

|H2| 6 2OPTV C(G[V −H1]) 6 2|OPT ′CV C |

et par conséquent, |OPT ′CV C | >|H2|

2. Nous déduisons :

|H|OPTCV C

6|H1|+ |H2|+ |H3||H1|+ |H2|

2

=ε1n+ |H2|+ ε2n

ε1n+ |H2|2

.

42

Ce dernier terme augmente proportionnellement avec |H2| quand ε1 > ε2. Enremplaçant |H2| par sa plus grande valeur possible, à savoir n(1 − ε1 − ε2),nous obtenons

|H|OPTCV C

62

1 + ε1 − ε2

.

L'algorithme de Karpinski et de Zelikovsky utilise l'observation suivante :si un sommet n'appartient pas à une couverture, alors tous ses voisins doiventappartenir à la couverture. Donc pour chaque sommet v, on construit unecouverture à partir de l'ensemble N(v), l'ensemble des voisins de v, et à partird'une 2-approximation sur le sous-graphe induit restant. L'Algorithme 4 im-plémente cette stratégie. Pour s'assurer que la couverture retournée induit ungraphe connexe, nous choississons d'e�ectuer une exécution de l'algorithmede Savage sur un sommet qui est adjacent à N(v).

Algorithme 4: Algorithme de CV C pour les graphes fortement densesEntrée : W ⊆ V un ensemble de sommets du graphe G.Sortie : une couverture connexe avec au plus 2

1+δ∗OPTCV C(G)

sommets.

début

pour tous les sommets v de W faire

vois(v)← {v} ∪N(v);pour toutes les composantes connexes C deG[V \ {{v} ∪N(v)}] faire

Trouver un sommet c ∈ C qui a un voisin dans N(v);Soit Savage(c) le résultat de l'algorithme de Savage sur Cen commençant avec c;vois(v)← vois(v) ∪ Savage(c);

�n

�n

vmin ← arg minv∈W |vois(v)|;retourner vois(vmin);

�n

Théorème 2.28. L'Algorithme 4 approxime CV C avec un facteur d'approxi-mation de 2

1+δ∗.

Démonstration. Il est facile de voir que l'Algorithme 4 retourne une solutionconnexe : vois(v) = {v ∪N(v)} est connexe, ainsi que le résultat de la

43

2-approximation sur chaque composante C, et chacune de celles-ci est ad-jacente à N(v) du fait que nous démarrons l'algorithme de Savage sur lesommet c adjacent à N(v). Remarquons que c existe toujours puisque legraphe est connexe. Par ailleurs, la solution retournée est de taille au plus|vois(v′)|, pour un sommet v′ n'appartenant pas à une solution optimale deCV C, disons E. Puisque v′ /∈ E, nous avons que N(v′) ⊆ E. En appliquantle Lemme 2.27 à vois(v′), avec |H1| = |N(v′)| > δ∗n et |H3| = |{v′}| = 1,nous obtenons directement le résultat souhaité.

Le second algorithme est basé sur l'idée de choisir un ensemble de sommetsW ⊆ V de taille au moins ρn et avec des sommets tous de degré au moins ρnpour une certaine constante ρ bien choisie. Posons E une solution optimalede CV C. Dans ce cas, soit W ⊆ E, soit il existe un sommet w dans W telque N(w) ⊆ E. Dans les deux cas, un ensemble de taille au moins ρn estinclus dans E. Karpinski et Zelikovsky [KZ98] ne demandent pas de toujoursretourner une solution connexe. En particulier, si tous les sommets de Wsont dans E, des opérations supplémentaires sont nécessaires, comme W n'apas nécessairement un sous-graphe induit connexe. Nous montrons que lacondition de connexité peut être satisfaite en ajoutant le plus petit ensembleX de sommets bien choisis.

Un algorithme comme l'Algorithme 5 est basé sur certaines propriétés.Voici deux lemmes développant ces propriétés. Le premier étant démontrépar Karpinski et Zelikovsky [KZ98].

Lemme 2.29. Soient ρ = 1 −√

1−m∗ et W l'ensemble de dρne sommetsavec les plus hauts degrés. Alors tout sommet de W a un degré d'au moins|W |.

Lemme 2.30. Il existe un ensemble X de taille O(log n) tel que G[W ∪X]est connexe. Un tel ensemble est calculé comme dans l'Algorithme 5.

Démonstration. Nous construisonsX itérativement en choisissant un sommetqui connecte le plus grand nombre de composantes connexes restantes. Soitvi un sommet arbitraire de la iième composante connexe de G[W ]. Prenonski la taille de cette composante et k le nombre total de composantes. Par leLemme 2.29, le degré de vi est au moins |W |. Donc vi a au moins |W |−ki+1voisins dans V \W . En sommant sur i, nous obtenons :

k∑i=1

|W | − ki + 1 = (k − 1)|W |+ k.

44

Algorithme 5: Algorithme de CV C pour les graphes faiblement densesEntrée : G un graphe connexe.Sortie : une couverture connexe.

début

ρ← 1−√

1−m∗;Soit W un ensemble de dρne sommets de plus hauts degrés;C1 ← Algorithme 4(W );C2 ← W ;pour tous les composantes connexes C de G[V \W ] faire

Trouver un sommet c ∈ C qui a un voisin dans W ;Soit Savage(c) le résultat de l'algorithme de Savage sur C encommençant avec c;C2 ← C2 ∪ Savage(c);

�n

X ← ∅;tant que G[W ∪X] n'est pas connexe faire

Trouver un sommet v dans V \W qui est adjacent au plusgrand nombre de composantes connexes de G[W ∪X];X ← X ∪ {v};

�n

C2 ← C2 ∪X;retourner l'ensemble de taille minimum entre C1 et C2;

�n

45

Par le principe des tiroirs, il existe un sommet v ∈ V \W qui connecte lenombre suivant de composantes :

(k − 1)|W |+ k

n− |W |=

(k − 1)ρn+ k

n(1− ρ)= (k− 1)

ρ

1− ρ+

k

n(1− ρ)> (k− 1)

ρ

1− ρ.

Nous pouvons ajouter v à l'ensemble X et répéter cet argument. A chaqueétape, un nouveau sommet est ajouté à X. Le nombre de composantesconnexes dans G[W ∪X] se réduit avec un facteur constant de 1− ρ

1−ρ = 1−2ρ1−ρ .

Puisque le nombre initial de composantes est au plus |W | alors nous avons|X| 6 log 1−ρ

1−2ρ(ρn) = O(log n).

Théorème 2.31. L'Algorithme 5 approxime CV C avec un facteur de

2

2−√

1−m∗.

Démonstration. Soit E une solution optimale à CV C. Si W contient unsommet v /∈ E, la preuve est identique à celle du théorème 2.28, en pre-nant |H1| = |N(v)| > |W | et |H3| = 1 dans le Lemme 2.27. Sinon W ⊆ E.Alors nous pouvons encore appliquer le Lemme 2.27 avec |H1| = |W | et,par le Lemme 2.30, |H3| = |X| = O(log n). La condition |H3| < |H1| de-mandée par le Lemme 2.27 est véri�ée asymptotiquement, et nous avonsε2 = O(log n)/n −→n→∞ 0. Donc le facteur d'approximation vaut

2

1 + ε1 − ε2

−→n→∞2

2−√

1−m∗.

Remarquons que les Algorithmes 4 et 5 sont de compléxité O(nm), d'oùen O(n3) quand m∗ est �xé.

Théorème 2.32. Les facteurs des Théorèmes 2.28 et 2.31 sont atteintsasymptotiquement.

Démonstration. Considérons la famille suivante de graphes : νn,α, le jointentre une clique de taille n− 2α− 1 et une roue de taille 2α+ 1 (voir Figure2.6). Une roue de taille k est tout simplement le joint entre une clique detaille 1 et un cycle de taille k − 1.

Nous allons d'abord montrer que OPTCV C(νn,α) = n− α et que les deuxAlgorithmes 4 et 5 retournent n − 1 pour νn,α. Ensuite, nous étudierons lefacteur d'approximation.

Nous pouvons véri�er facilement qu'en prenant la clique Kn−2α−1, lecentre K1 de la roue, et pour les sommets du cycle C2α, une couverture

46

Figure 2.6 � ν10,3 le joint entre K3 et le joint entre K1 et C6.

de α sommets su�t pour avoir une couverture connexe de νn,α. De plus, c'estle nombre minimum de sommets nécessaires pour couvrir toutes les arêtes.

Pour l'Algorithme 4, si le sommet v est dans la clique ou au centre de laroue, alors vois(v) = {v}∪N(v) = V et |vois(v)| = n−1. Sinon v appartientau cycle C2α. Par conséquent, {v} ∪ N(v) contient exactement les sommetsde la clique, le centre de la roue, les deux voisins dans le cycle C2α et v lui-même. De plus, l'algorithme de Savage sera appliqué et donnera un cheminP2α−3. Donc |vois(v)| = n− 1.

Pour l'Algorithme 5, nous avons |C1| = n− 1 pour les mêmes raisons queci-dessus. Puisque OPT ∗CV C > 1 −

√1−m∗ + o(1) par le Lemme 2.24, W

contient au moins la clique et le centre de la roue. Par conséquent, il induittoujours un sous-graphe connexe. Dans le pire des cas, V \W est un chemin,ce qui implique que |C2| = n− 1.

Étudions le facteur d'approximation. Puisque seulement les sommets ducycle C2α sont de degré inférieur à n − 1, nous obtenons δ(νn,α) = n − 2α.De plus, νn,α a toutes les arêtes possibles exceptées les 2α(2α−1)

2− 2α arêtes

manquantes dans le cycle C2α. Donc

m(νn,α) =n(n− 1)

2− 2α(2α− 1)

2+ 2α.

Rappelons que δ∗ = δnet m∗ = m

n(n−1)/2. La borne du Théorème 2.28 est

21+δ∗

= 21+n−2α

n

= nn−α , dont

n−1n−α est arbitrairement proche pour n grand. Par

ailleurs, celle du Théorème 2.31 vaut

2

2−√

1−m∗=

2

2−√

4α2−6αn(n−1)

=2√n(n− 1)

2√n(n− 1)−

√4α2 − 6α

≈ n

n− α,

47

dont n−1n−α est aussi arbitrairement proche pour n grand.

2.2.3 Le Problème de l'Ensemble Dominant

Le Problème de l'Ensemble Dominant est le sujet principal dans ce mé-moire. Par conséquent, nous allons passer une bonne partie de ce chapitresur ce problème. Nous allons étudier des algorithmes d'approximation et� l'équivalence � de ce problème avec d'autres. Pour cela, nous devrons dé-�nir di�érentes notions pour comprendre le concept d' � équivalence � aupoint de vue algorithme d'approximation.

Tout d'abord, nous avons vu par le convertisseur donné par l'Algorithme2 que le problème DS est lié à celui de V C. Nous pouvons en déduire laproposition suivante.

Proposition 2.33. Si DS est α-approximable, où α > 1, alors V C est aussiα-approximable.

Démonstration. Soit A un algorithme α-approximable résolvant DS, c'est-à-dire prenant en entrée un graphe H et retournant D un ensemble dominantpour H avec une cardinalité au plus de αγ(H), où γ(H) est la cardinalitédu plus petit ensemble dominant de H. Prenons l'algorithme qui consiste àtransformer par le Convertisseur 2 l'instance G de V C en une instance G′

pour DS, c'est-à-dire V (G′) = V (G) ∪ E(G) et

E(G′) = E(G) ∪ {(u, e) ∈ V (G)× E(G)|u ∈ E}.

Ensuite, appliquons l'algorithme A à G′. Nous obtenons D un ensemble do-minant de G′. Reprenons la fonction de E(G) dans V (G) dé�nie dans lapreuve que DS est NP -complet, à savoir pour tout uv ∈ E(G),

f(uv) =

{u si u /∈ Dv sinon.

Posons C = {v ∈ D|v ∈ V (G)} ∪ {f(e) ∈ V (G)|e ∈ D ∩ E(G)}. Nous avonsdéjà montré que C est une couverture. De plus, il est clair que C est de tailleau plus |D|. Par conséquent, nous avons les inégalités suivantes :

|C| 6 |D| 6 αγ(G′).

De plus, puisque le convertisseur permet une réduction polynomiale de V Cà DS, il en découle que γ(G′) = τ(G), où τ(G) est la cardinalité de la pluspetite couverture par les sommets dans G. Donc |C| 6 ατ(G), ce qu'il restaità prouver. De plus, remarquons que toutes les opérations e�ectuées en plusde l'algorithme A se font en un temps polynomial, et donc n'in�uencent pasvraiment la complexité de l'algorithme trouvé.

48

Khot et Regev [KR08] nous disent que le problème de V C n'est pas ap-proximable avec un facteur de 7

6≈ 1, 66667. Par conséquent, nous pouvons

déduire par la contraposée de la Proposition 2.33 que DS n'est pas approxi-mable avec ce même facteur.

2.2.4 La L-réduction ou réduction linéaire

Dans la section précédente, nous avons vu que la réduction polynomialesur les problèmes de décision � modi�ée � pour des problèmes d'existence oud'optimisation nous permet de déduire certaines implications concernant lecaractère d'algorithme d'approximation. En fait, il existe une réduction dansle contexte des algorithmes d'approximation : la L-réduction ou réduction

linéaire. Ce concept a été introduit par Papadimitriou et Yannakakis en 1988pour prouver la complétude de certaines classes de problèmes. Soient P1 et P2

deux problèmes d'optimisation. Une réduction quelconque de P1 à P2 signi�eque nous pouvons résoudre P1 à l'aide d'un algorithme résolvant P2. Dans cecas-ci, la L-réduction garantit qu'une solution approximative de P2 peut êtreutilisée pour en obtenir une de P1 et ceci dans un temps raisonnable. Pourcela, nous avons juste besoin d'une fonction f partant des instances de P1

vers celles de P2 mais aussi d'une fonction-retour g de l'ensemble des solutionsde P2 vers celles de P1 (cf. Figure 2.7). Ausiello, Crescenzi, Gambosi, Kann,Marchetti-Spaccamela et Protasi [ACG+99, p. 256-260] nous font décourircette nouvelle réduction.

Dé�nition 2.34. Soient P1 et P2 deux problèmes d'optimisation. Le qua-druple (f, g, α, β) est une L-réduction ou réduction linéaire 1 de P1 vers P2,noté P1 6L P2, si les fonctions f et g et les constantes positives α et βvéri�ent les conditions suivantes :

1. Pour tout x ∈ IP1 , f(x) ∈ IP2 et est calculable en un temps polynomial,

2. Pour tout x ∈ IP1 , si SolP1(x) 6= ∅ alors SolP2(f(x)) 6= ∅,3. Pour tout x ∈ IP1 et y ∈ SolP2(f(x)), g(x, y) ∈ SolP1(x) et est calcu-

lable en un temps polynomial,

4. Pour tout x ∈ IP1 , OPTP2(f(x)) 6 αOPTP1(x),

5. Pour tout x ∈ IP1 et y ∈ SolP2(f(x)),

|OPTP1(x)− C1(x, g(x, y))| 6 β|OPTP2(f(x))− C2(f(x), y)|.

1. Le terme � linéaire � provient de la relation linéaire entre le coût des solutions op-

timales et de la relation linéaire entre les erreurs absolues, données dans les points 4 et 5de la dé�nition.

49

IP1

x

IP2

f(x)

y

g(x, y)

SolP2(f(x))SolP1(x)

OPTP2

OPTP1

Solapprox2Solapprox1

Figure 2.7 � L-réduction entre deux problèmes d'optimisation P1 et P2.

où IPk représente les instances du problème Pk, SolPk(z) les solutions po-tentielles du problème Pk pour l'instance z et Ck est une fonction coût duproblème Pk, que l'on cherche à optimiser. Nous disons aussi que P1 estL-réductible en P2.

Exemple 2.35. Le Problème V C est L-réductible en DS. En e�et, en pre-nant α = β = 1, nous trouvons tous les éléments d'une L-réduction dans lapreuve de la Proposition 2.33.

La dé�nition suivante nous donne une formalisation de l'équivalence dedeux problèmes d'optimisation concernant les algorithmes d'approximation.

Dé�nition 2.36. Soient P1, P2 deux problèmes d'optimisation. On dit queP1 et P2 sont équivalents sous la L-réduction si P1 6L P2 et P2 6L P1.

La proposition suivante est un outil essentiel pour comprendre l'impor-tance de la L-réduction. Cette proposition est basée sur la thèse de Kann[Kan92, p. 18-19].

Proposition 2.37. Soient P1, P2 deux problèmes d'optimisation et(f, g, α, β) une L-réduction de P1 vers P2. S'il existe un algorithme d'ap-proximation de temps polynomial pour P2 avec une erreur relative dans le

50

pire des cas de ε, alors P1 possède un algorithme d'approximation de tempspolynomial avec une erreur relative dans le pire des cas de αβε.

Démonstration. Soit A un algorithme d'approximation de temps polynomialpour P2 avec une erreur relative d'au plus ε. Considérons l'Algorithme 6 detemps polynomial.

Algorithme 6: Algorithme d'approximation de P1 de rapport αEntrée : x ∈ IP1

Sortie : h(x) ∈ SolP1(x) d'erreur relative αβε

début

y ←− A(f(x)) ;retourner g(x,y);

�n

Véri�ons que l'erreur relative de la sortie est toujours majorée par αβε.Soient x ∈ IP1 et h(x) la solution donnée par l'Algorithme 6. Nous avonsles inégalités suivantes :

εrP1(x, h(x)) =

|OPTP1(x)− CP1(x, h(x))|OPTP1(x)

6β|OPTP2(f(x))− CP2(f(x), y)|

OPTP2 (f(x))

α

= αβεrP2(f(x), y)

6 αβε.

Nous comprenons davantage la Dé�nition 2.36 d'équivalence sous laL-réduction avec les corollaires suivants, déduits immédiatement de la Pro-position 2.37. En e�et, si deux problèmes d'optimisation sont équivalentssous la L-réduction, alors trouver un algorithme d'approximation pour l'unrevient à en trouver un pour l'autre en gardant un certain contrôle de laqualité d'approximation.

Corollaire 2.38. Soient P1 et P2 deux problèmes d'optimisation. Si P2 estapproximable avec une erreur relative d'au plus ε et P1 est L-réductible en P2

par (f, g, α, β) alors P1 est approximable avec une erreur relative d'au plusαβε.

51

Corollaire 2.39. Soient P1 et P2 deux problèmes d'optimisation, r > 0. SiP1 6L P2 avec le quadruple (f, g, 1, 1) et si P2 est r-approximable alors P1

est aussi r-approximable et ceci au sens de l'erreur relative ou du rapport deperformance.

Maintenant, nous allons nous concentrer sur deux L-réductions en liendirect avec le Problème de l'Ensemble Dominant. Pour cela, nous allons dé-�nir un nouveau problème : le Problème de Couverture par des Ensembles.Ce problème est une question classique de la théorie de la complexité. Il seranoté SC (pour Set Cover) et est décrit comme suit : pour une collectionde sous-ensembles d'un ensemble �ni E, ceux-ci ayant certains éléments encommun et recouvrant E, nous devons sélectionner un nombre minimal deces sous-ensembles tels que E soit recouvert par cette sélection. Plus formel-lement, pour un ensemble �ni E et une collection C de sous-ensembles de E,une couverture est une sous-famille C ′ de C telle que l'union des ensemblesde C ′ vaut E. Le problème de décision considère (E,C ) et un entier k et setraduit par la question suivante : � existe-t-il une couverture de E par desensembles de C de taille au plus k ? � Tandis que le problème d'optimisa-tion ne prend que la paire (E,C ) comme entrée et demande de trouver unecouverture composée d'un nombre minimum d'ensembles de C .

Ce problème est NP -complet, comme nous le dit Papadimitriou [PP94,p. 201].

Exemple 2.40. Pour illustrer ce problème, prenons les ensembles suivants :E = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} et C = {E1, E2, E3, E4, E5} oùE1 = {1, 3, 5, 7, 9}, E2 = {2, 3, 4, 5}, E3 = {4, 6, 8, 10}, E4 = {2, 6, 8, 10} etE5 = {1, 4}. Une couverture minimale est C ′ = {E1, E4, E5}.

Le théorème suivant est tiré de la thèse de Kann [Kan92, p. 108-109],intitulée � On the approximability of NP -complete optimization problems �.

Théorème 2.41. Les Problèmes DS et SC sont équivalents sous la L-ré-duction. De plus, DS est α-approximable si et seulement si SC est α-ap-proximable.

Démonstration. (DS 6L SC) Soit G = (V,E) un graphe avec V = {1, ..., n}.Construisons une instance (U,C ) de SC comme suit : l'ensemble U est V etla collection d'ensembles C est {V1, ..., Vn} où Vi = {i} ∪ NG(i), c'est-à-direVi est l'ensemble des voisins de i avec i lui-même.

SiD est un ensemble dominant pourG alors C ′ = {Vi|i ∈ D} est une solu-tion admissible pour SC avec |D| = |C ′|. Réciproquement, si C ′ = {Vi|i ∈ D}est une solution admissible pour SC alors D est un ensemble dominant pour

52

G avec |C ′| = |D|. Par conséquent, la taille d'un ensemble dominant mini-mum pour G est égale à celle d'une couverture minimum par des ensemblespour (U,C ). Dès lors, les constantes recherchées α et β de la L-réductionvalent toutes les deux 1.

(SC 6L DS) Soit (U,C ) une instance du Problème SC avec

C = {Ui|i ∈ I}.Nous pouvons supposer que l'ensemble des indices I et U sont disjoints.Construisons un graphe G = (V,E) comme suit : l'ensemble V est l'unionde I avec U , il y a une arête (i, j) ∈ E entre chaque paire i, j ∈ I et il y aune arête (i, u) ∈ E pour chaque i ∈ I, u ∈ Ui. Pour rappel, G est un graphefendu : I est une clique et U est un ensemble indépendant.

Si C ′ = {Ui|i ∈ D} est une solution admissible pour SC, où D ⊆ I, alorsD est un ensemble dominant pour G, avec |D| = |C ′|. En e�et, tout d'abord,pour chaque u ∈ U , il existe un i ∈ D tel que u ∈ Ui et par construction, u eti sont adjacents dans G. Donc u est dominé par i. Ensuite, puisque D ne peutpas être vide, chaque i ∈ I est adjacent à un sommet de D. Réciproquement,prenons D un ensemble dominant pour G. Construisons un autre ensembledominant D′ avec |D′| 6 |D| et D′ ⊆ I. Remplaçons simplement chaqueu ∈ D ∩ U par un voisin i ∈ I de u. Alors C ′ = {Ui|i ∈ D′} est unesolution admissible pour SC, avec |C ′| = |D′| 6 |D|. Par notre constructionet puisque nous avons la relation suivante, OPTDS(G) = OPTSC(U,C ), lesconstantes recherchées α et β de la L-réduction sont égales à 1.

Par le Corollaire 2.39 et puisque DS et SC sont équivalents sous laL-réduction avec toutes les constantes égales à 1, alors il est évident que DSest α-approximable si et seulement si SC est α-approximable.

Exemple 2.42. Pour illustrer les constructions dans la preuve du Théorème2.41, voici deux exemples.

(DS 6L SC) Pour le graphe G de la Figure 2.8, nous construisons l'ins-tance de SC avec l'ensemble U = {1, 2, 3, 4, 5, 6} et les ensembles suivants :V1 = {1, 2, 5}, V2 = {1, 2, 3, 5}, V3 = {2, 3, 4, 6}, V4 = {3, 4}, V5 = {1, 2, 5, 6}et V6 = {3, 5, 6}. Puisque l'ensemble D = {3, 5} est un ensemble dominantdans G, la collection C ′ = {V3, V5} est une couverture de U .

(SC 6L DS) Considérons l'instance suivante de SC : (U,C ) oùU = {a, b, c, d, e} et C = {V1, V2, V3, V4} avec V1 = {a, b, c}, V2 = {a, b},V3 = {b, c, d}, V4 = {c, d, e}. A partir de cette instance, nous construisons legraphe G de la Figure 2.9. De plus, nous pouvons déduire de la couverture{V1, V4} de (U,C ) l'ensemble dominant {1, 4} pour G. Réciproquement, parexemple, puisque D = {a, 3, 4} est un ensemble dominant de G, nous consi-dérons un autre ensemble dominant D′ = {1, 3, 4} pour lequel la collectioncorrespondante C ′ = {V1, V3, V4} est une couverture de U .

53

1

2

3 4

5

6

G

Figure 2.8 � L'ensemble {3, 5} est un ensemble dominant dans le graphe G.

a b c d e

12 3 4

G

Figure 2.9 � Graphe fendu obtenu à partir d'une instance de SC.

Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela et Protasi[ACG+99] rassemblent di�érents résultats d'approximabilité et d'inapproxi-mabilité pour ces deux problèmes. La symétrie des résultats est évidente. Ilsexpliquent ainsi qu'en 1996, Feige a montré que DS n'est pas approximableavec un facteur de (1− ε) log(|G|) pour tout ε > 0 sans que

NP ⊆ TIME(nlog(logn)).

Sous cette même condition, SC n'est pas approximable avec un facteur de(1 − ε) log(|E|), pour tout ε > 0. Par ailleurs, DS est approximable avecun rapport de 1 + ln(|G|), parce que DS 6L SC et SC est 1 + ln(|E|)-approximable. Valika K. Wan et Khanh Do Ba [WB10] démontrent ce dernierrésultat.

Théorème 2.43. Le Problème SC est 1 + ln(|E|)-approximable.

Démonstration. Considérons l'Algorithme 7, algorithme glouton et polyno-mial.

54

Algorithme 7: Algorithme glouton de SCEntrée : (E,C ) une instance de SCSortie : C ′ une sous-collection de C couvrant E

début

U ←− E;C ′ ←− ∅;tant que U 6= ∅ faire

Soit C ∈ C maximisant |C ∩ U |;U ←− U \ C;C ′ ←− C ′ ∪ {C};

�n

retourner C ′;�n

L'Algorithme 7 part d'une collection C ′ vide et à chaque étape, nousajoutons à cette collection un élément de C couvrant le plus d'éléments deE non couverts par C ′. En fait, nous allons montrer que cet algorithme rendle Problème SC H (max (|C| : C ∈ C ))-approximable, où H(d) =

∑di=1

1i, le

dème nombre harmonique. Puisque d est ici majoré par |E| et

H(d) =d∑i=1

1

i6 ln(d) + 1 6 ln(|E|) + 1,

nous aurons alors le résultat voulu.Lorsque nous parlons de l'algorithme, nous faisons référence à l'Algo-

rithme 7. Désignons par C ∗ une solution optimale de SC et C ′ la solutionretournée par l'algorithme. Pour démontrer le théorème, il su�t de montrerque

|C ′||C ∗|

6 H(max(|C| : C ∈ C )).

Assignons un prix de 1 à chaque ensemble C ∈ C séléctionné par l'algorithmeet distribuons ce prix sur tous les éléments de cet ensemble couverts pourla première fois. Notons Ci le ième ensemble séléctionné par l'algorithme à laième itération. Posons cx le prix alloué à chaque élément x ∈ E, couvert pourla première fois à la ième itération. En d'autres mots,

cx =1∣∣∣∣∣Ci \(i−1⋃j=1

Cj

)∣∣∣∣∣.

55

Notons que |Ci \ (C1 ∪ C2 ∪ · · · ∪ Ci−1)| est le nombre d'éléments couvertspour la première fois par Ci à la ième itération.

A chaque itération de l'algorithme, une unité de prix est assignée et unseul des éléments C ∈ C est ajouté à la couverture C ′. Dès lors, la couverturedonnée par l'algorithme est de taille exactement égale au prix de l'univers,c'est-à-dire

|C ′| =∑x∈E

cx. (⊕)

Nous ne pouvons traiter une solution optimale. Dès lors, pour comparer lasolution de notre algorithme glouton à une solution optimale, nous devonsfaire des comparaions en utilisant des notions de référence, comme le prix del'univers. Le prix assigné à une couverture optimale C ∗ est dé�ni par∑

C∈C ∗

∑x∈C

cx.

Nous avons besoin de trouver une relation entre le prix de l'univers et le prixde la couverture C ∗. A partir du prix de la couverture optimale dé�ni ci-dessus, si certains éléments de C ∗ se chevauchent, alors le prix des élémentsde E dans les intersections non vides est compté deux fois. Nous avons donc :∑

C∈C ∗

∑x∈C

cx >∑x∈E

cx. (⊗)

A partir des équations (⊕) et (⊗), nous obtenons :

|C ′| 6∑C∈C ∗

∑x∈C

cx. (�)

Dans un premier temps, nous allons supposer l'inégalité suivante vraie etensuite, nous la démontrerons.

∀C ∈ C ,∑x∈C

cx 6 H(|C|). ()

Si la proposition () est véri�ée, alors nous obtenons de l'inégalité (�) etpar croissance de la fonction H(.) :

|C ′| 6∑C∈C ∗

H(|C|)

6 |C ∗|H(max(|C| : C ∈ C )),

ce qui démontre le résultat souhaité.

56

Maintenant, il nous reste à montrer (). Soit C un élément de C . Pouri = 1, 2, . . . , |C ′|, posons

ui(C) = |C \ (C1 ∪ C2 ∪ · · · ∪ Ci)|,

le nombre d'éléments de C non couverts par l'algorithme après l'ajout deC1, C2, . . . , Ci dans C ′ à la ième itération. Nous dé�nissons

u0(C) = |C|,

le nombre de tous les éléments de C, qui initialement ne sont pas couverts.Posons k le plus petit indice tel que

uk(C) = 0.

Par conséquent, à la kème itération, tous les éléments de C sont couvertspour la première fois par les ensembles C1, C2, . . . Ck choisis par l'algorithme.Remarquons que u0(C) > u1(C) > · · · > uk−1(C) > uk(C) = 0. Nous avonsdonc toujours ui−1(C) > ui(C) et ui−1(C)− ui(C) est le nombre d'élémentsde C qui sont couverts pour la première fois par Ci à la ième itération, pouri = 1, 2, . . . , k. Donc,

∑x∈C

cx =k∑i=1

(ui−1(C)− ui(C))1

|Ci \ (C1 ∪ · · · ∪ Ci−1)|, (�)

c'est-à-dire la somme des prix des éléments de C vaut la somme du nombred'éléments de C couverts par Ci pour la première fois, où chacun de ceséléments a un prix assigné par la ième itération. Observons que

|Ci \ (C1 ∪ · · · ∪ Ci−1)| > |C \ (C1 ∪ · · · ∪ Ci−1)|= ui−1

parce que Ci est choisi par l'algorithme à l'itération i comme un ensemble deC maximisant le nombre de ces éléments non couverts jusqu'à cette itération,c'est-à-dire maximisant |Ci \ (C1 ∪ · · · ∪Ci−1)|. De ces dernières inégalités etde l'égalité (�), nous obtenons :

∑x∈C

cx 6k∑i=1

(ui−1 − ui)1

ui−1

.

57

Nous allons majorer cette somme de la manière suivante :∑x∈C

cx 6k∑i=1

(ui−1 − ui)1

ui−1

=k∑i=1

ui−1∑j=ui+1

1

ui−1

6k∑i=1

ui−1∑j=ui+1

1

j

=k∑i=1

(ui−1∑j=1

1

j−

ui∑j=1

1

j

)

=k∑i=1

(H(ui−1)−H(ui))

= (H(u0)−H(u1)) + (H(u1)−H(u2))+ · · ·+ (H(uk−1)−H(uk))

= H(u0)−H(uk)= H(u0)−H(0)= H(u0)= H(|C|),

ce qui démontre la proposition (), et donc complète cette preuve.

58

Chapitre 3

Prix de la Connexité

Ce chapitre sera consacré à une nouvelle notion de théorie des graphesintroduite par Cardinal et Levy [Lev09, CL08] : le Prix de la Connexité, notéPoC.

3.1 Dé�nition

Ce concept est dé�ni en fonction d'un problème. Découvrons-le pour unproblème que nous avons déjà rencontré : la Couverture des Arêtes par desSommets ou le Vertex Cover, noté V C.

Nous allons nous occuper de la version connexe de ce problème : la Cou-verture Connexe des Arêtes par des Sommets ou le Connected Vertex Cover(CV C). Nous avons simplement ajouté une contrainte supplémentaire auproblème précédent. Regardons maintenant le coût de cette contrainte. Pourcela, dé�nissons trois outils, relatifs au Problème de V C. Soit G un grapheconnexe. Nous noterons par OPTV C(G) la cardinalité d'un ensemble mini-mum de sommets du graphe G ayant la propriété de V C, par OPTCV C(G)la cardinalité d'un même ensemble mais véri�ant la propriété de CV C et parPoCV C(G) le rapport entre OPTCV C(G) et OPTV C(G), c'est-à-dire le prixde la connexité.

Tous ces éléments sont dé�nis en fonction d'un graphe et d'un problèmedonnés. Pour enlever la dépendance au graphe, nous pouvons notammentétudier le PoCV C :

PoCV C = supG graphe connexe

PoCV C(G).

Pour ce problème, le meilleur des cas est d'avoir un graphe G tel que

PoCV C(G) = 1,

59

c'est-à-dire que la contrainte de connexité n'augmente pas la taille minimumd'une couverture.

Nous pouvons évidemment étendre ces notions à d'autres problèmes d'op-timisation, pour lesquels la contrainte de connexité a du sens. Voici une dé-�nition générique du PoC.

Dé�nition 3.1. Soient P un problème d'optimisation de théorie des graphespossédant une variante connexe et G un graphe connexe. Nous noteronsOPTP (G) le coût optimal de G pour le problème P et OPTCP (G) celuipour la version connexe de P . Le Prix de la Connexité du graphe G, notéPoCP (G), est dé�ni comme suit :

PoCP (G) =OPTCP (G)

OPTP (G).

Si le contexte n'est pas ambigu, nous n'écrirons pas l'indice référant leproblème. Le Prix de la Connexité peut être vu comme une indication surl'ajout de la contrainte de connexité. Remarquons que ces notions n'ont desens que pour des graphes connexes.

En général, nous allons rechercher des bornes supérieures et inférieuresau PoC, ainsi que des familles de graphes atteignant ces bornes, si de tellesfamilles existent. Si P est un problème de minimisation, alors nous avonsla relation suivante : OPTP (G) 6 OPTCP (G), c'est-à-dire 1 6 PoC(G). Defaçon analogue, si nous avons un problème de maximisation, nous avons :1 > PoC(G). De la dé�nition du PoC, nous pouvons déduire l'observationsuivante.

Théorème 3.2. Soient P un problème d'optimisation de théorie des graphespossédant une variante connexe et G un graphe connexe. Le graphe G possèdeun PoCP égal à 1 si et seulement s'il existe une solution optimale à la versionconnexe de P qui est aussi une solution optimale de P .

Revenons au Problème de V C.

3.2 Le Prix de la Connexité de V C

Dans cette section, nous allons étudier le prix de la connexité pour leProblème de Couverture, détaillé par Cardinal et Levy [CL08], [Lev09, p.118-122]. Dans ce cas, le prix de la connexité est dé�ni par le rapport entrela cardinalité de la plus petite couverture connexe et celle de la plus pe-tite couverture pas nécessairement connexe. Nous allons d'abord analyser laborne supérieure de ce rapport et ensuite, trouver une famille de graphespour lesquels le rapport est proche de cette borne supérieure.

60

3.2.1 Borne supérieure du PoC de V C

Désignons par T une couverture optimale arbitraire, par I = V \ T lestable maximum correspondant, par k le nombre de composantes connexesdans le sous-graphe induit par T et par err la di�érence OPTCV C −OPTV C .Finalement, nous noterons par S l'ensemble de sommets supplémentairesdans une plus petite couverture connexe contenant T , de taille s = |S|.

Le premier lemme donne une relation entre err, s et k.

Lemme 3.3. err 6 s < k.

Démonstration. Par l'absurde, si s est strictement plus petit que err alors ilexiste une couverture connexe de taille strictement plus petite que OPTCV C ,ce qui est impossible. Nous en déduisons la première inégalité. La secondeinégalité, s < k, vient du fait que, puisque S est un stable, chacun de sessommets diminue strictement le nombre de composantes connexes de T .

Le second lemme nous donne une borne supérieure sur le nombre decertains voisins des sommets du stable maximum I.

Lemme 3.4. Tout sommet de I est voisin d'un sommet dans au plus k−s+1composantes connexes di�érentes de T .

Démonstration. Par contradiction, supposons qu'un sommet v ∈ I est liéà au moins k − s + 2 composantes connexes de T . Alors T ∪ {v} a au plusk−(k−s+1) = s−1 composantes connexes, d'où le plus petit sous-ensembleX de I qui contient v et tel que T ∪X est connexe est de taille au plus s−1,ce qui contredit la minimalité de S.

Le dernier lemme majore le nombre d'arêtes par une expression dépen-dante de (n,OPTV C , k, s).

Lemme 3.5.

m 6(OPTV C − k + 1)(OPTV C − k)

2+ (n−OPTV C)(OPTV C − s+ 1).

Démonstration. Posons E1 l'ensemble des arêtes de G[T ] et E2 celui entre Tet I. Puisque I est indépendant, il est clair que m = |E1|+ |E2|. Nous allonsmajorer séparément la taille de chacun de ces deux ensembles.

Il est évident que E1 est maximal lorsque toutes les composantes connexesde T sont des cliques. De plus, puisque le nombre total d'arêtes dans cescliques est une somme de termes comme x(x−1)

2, E1 est maximal lorsqu'il

possède une grande clique de taille OPTV C − k + 1 et k − 1 sommets isolés.D'où, |E1| 6 (OPTV C−k+1)(OPTV C−k)

2.

61

Nous allons maintenant considérer E2. Comme chaque sommet v dans Iest lié à au plus k − s+ 1 composantes connexes de T , par le Lemme 3.4, ilexiste au moins s− 1 composantes connexes qui ne sont pas liées à v. Doncv n'est pas voisin d'au moins s − 1 sommets de T , c'est-à-dire a au plusOPTV C − (s − 1) = OPTV C − s + 1 voisins dans T . En multipliant cetteborne par n−OPTV C , la taille de I, nous obtenons

|E2| 6 (n−OPTV C)(OPTV C − s+ 1).

Finalement, le théorème suivant est construit à partir de la borne donnéepar le Lemme 3.5 pour obtenir une borne supérieure du PoC.

Théorème 3.6. Le rapport entre la taille d'une couverture connexe minimumet d'une couverture minimum d'un graphe G avec m arêtes est au plus

21+m∗

+ o(1), c'est-à-dire

PoC(G) 62

1 +m∗+ o(1).

Démonstration. Démarrons par le résultat du Lemme 3.5 :

m 6(OPTV C − k + 1)(OPTV C − k)

2+ (n−OPTV C)(OPTV C − s+ 1).

Nous pouvons remarquer que cette borne décroît en fonction de k et s. Nousallons la maximiser en prenant les plus petites valeurs possibles pour k et s.Ces valeurs minimales sont s = err et k = err + 1 par le Lemme 3.3. Nousobtenons :

m 6(OPTV C − err)(OPTV C − err − 1)

2+ (n−OPTV C)(OPTV C − err+ 1).

Nous dé�nissons β, le PoC, comme le rapport OPTCV COPTV C

. Puisqueerr = OPTCV C−OPTV C , nous avons err

OPTV C= β−1 et err = OPTV C(β−1).

En remplaçant cette donnée dans la dernière majoration, nous aboutissons à

m 6OPTV C(2− β)(OPTV C(2− β)− 1)

2+(n−OPTV C)(OPTV C(2−β)+1).

(⊕)Nous allons maintenant maximiser l'expression ci-dessus, notée f(OPTV C),en cherchant la racine de sa dérivée selon OPTV C . Calculons d'abord cettedérivée :

62

∂OPTV C (f(OPTV C)) = ∂OPTV C(

12(OPT 2

V C(2− β)2 −OPTV C(2− β)))

+∂OPTV C (nOPTV C(2− β) + n)+∂OPTV C (−OPT 2

V C(2− β)−OPTV C)

= ((2− β)2 − 2(2− β))OPTV C+n(2− β)− 2−β

2− 1.

La racine de cette dérivée est, pour chaque β �xé :

OPT ′V C =n(2−β)− 2−β

2−1

2(2−β)−(2−β)2

=n(2−β)− 2−β

2−1

(2−β)β

= 2n(2−β)−2+β−22β(2−β)

= nβ

+ β−42β(2−β)

= nβ

+O(1).

En remplaçant OPT ′V C dans (⊕), nous obtenons :

m 6 OPT ′V C(2−β)(OPT ′V C(2−β)−1)

2

+(n−OPT ′V C)(OPT ′V C(2− β) + 1)

= n2(2−β)2β

+O(n).

D'où,

m∗ 62− ββ

+ o(1) et β 62

1 +m∗+ o(1).

3.2.2 Qualité de la borne supérieure du PoC de V C

Nous allons décrire une famille de graphes dont le PoC est proche dufacteur du Théorème 3.6. Prenons Gn,x, avec (n − x) un multiple de 3, legraphe composé d'une clique de taille x et de n−x

3chemins de longueur 3, où

les extrémités sont adjacentes à tous les sommets de la clique. La Figure 3.1représente le graphe G10,4.

La couverture minimum est constituée de la clique de taille x et du centrede chaque chemin, d'où a une cardinalité de x+ (n− x)/3 = (n+ 2x)/3. Deplus, la couverture connexe minimum n'est autre que cet ensemble auquelnous avons ajouté un sommet par chemin, d'où elle est de taille

x+ 2(n− x)/3 = (2n+ x)/3.

Par conséquent, nous obtenons PoC(Gn,x) = 2n+xn+2x

.Nous allons déterminer une valeur de x pour obtenir un PoC(Gn,x) proche

de la borne donnée par le Théorème 3.6. Pour cela, nous allons exprimer cette

63

Figure 3.1 �G10,4 graphe composé d'une clique de taille 4 et de deux cheminsde longueur 3.

borne comme une fonction de la densité m∗. Le graphe Gn,x a x(x−1)2

arêtes

dans la clique, x.2(n−x)3

arêtes entre les chemins et la clique et 2(n−x)3

arêtesdans les chemins. D'où,

m(Gn,x) =x(x− 1)

2+x.2(n− x)

3+

2(n− x)

3=

2nx

3− x2

6− 7x

6+

2n

3.

En normalisant, nous obtenons :

m∗(Gn,x) =m(Gn,x)n(n−1)

2

=4x∗ − x∗2

3+O

(1

n

), où x∗ =

x

n.

En résolvant cette équation du second ordre selon x∗, nous obtenons lessolutions x∗ = 2 ±

√4− 3m∗ + o(1). Mais seulement la solution inférieure

x∗ = 2 −√

4− 3m∗ + o(1) doit être considérée pour avoir x∗ ∈ [0, 1]. Enremplaçant cette valeur de x∗ dans la borne du PoC, nous trouvons :

PoC(Gn,x) =2n+ x

n+ 2x=

4 + 2m∗ +√

4− 3m∗

3 + 4m∗+ o(1).

Cette nouvelle borne est très proche de celle du Théorème 3.6. En fait, Car-dinal et Levy [CL08] nous disent que la di�érence entre les deux bornes nedépasse pas 1, 6% de cette nouvelle borne. Les graphes Gn,x sont, en e�et, debons candidats pour des exemples extrémaux du prix de la connexité. Pourune meilleure compréhension, regardons la Figure 3.2 représentant G10,4.L'ensemble T est constitué d'une clique de taille x et de k − 1 sommetsisolés, et chaque sommet en dehors de T est relié à ceux de la clique et unsommet isolé.

Le graphe Gn,x a comme couverture T de taille x+ n−x3

= 2x+n3

et commecouverture connexe T ∪S de taille 2x+n

3+ n−x

3= 2n+x

3. Dès lors, les instances

64

T

S

Figure 3.2 �G10,4 graphe composé d'une clique de taille 4 et de deux cheminsde longueur 3.

err, s et k ont pour valeur err = s = n−x3

et k = n−x3

+ 1. En réalité,Gn,x a un nombre d'arêtes exactement égal à la borne donnée par le Lemme3.5. Pour trouver une borne supérieure au PoC, nous partons de celle duLemme 3.5 pour ensuite la maximiser. Puisque Gn,x véri�e les conditionserr = s = k − 1, la qualité du PoC s'est dégradée lorsque nous maximisonsen prenant OPTV C = OPT ′V C . En e�et, nous prenons un OPTV C maximum.Or la construction de Gn,x ne le permet pas.

65

Chapitre 4

Le Problème de l'Ensemble

Dominant

Dans ce dernier chapitre, nous découvrirons di�érentes études person-nelles sur le Prix de la Connexité : encadrement, étude en fonction d'unparamètre ou sur certaines familles de graphes et complexité. Auparavant,Roberts [Rob87], Wu et Li [WL99] motivent l'importance de l'ensemble do-minant ainsi que de sa version connexe.

4.1 Applications des ensembles dominants

Dans la pratique, il est intéressant de connaître un ensemble dominant mi-nimum d'un graphe mais surtout un ensemble dominant minimum connexe.En e�et, l'avantage d'un tel ensemble est la possibilité de donner une infor-mation à tous les sommets du graphe en un minimum de temps : il su�t,grâce à la connexité de l'ensemble dominant, de la passer aux sommets de cetensemble et, en une arête, la transmettre à tous les sommets. Les ensemblesdominants se retrouvent dans di�érents problèmes. Roberts [Rob87, p. 62-63]donne trois intérêts de l'ensemble dominant.

Il explique qu'en 1973, Berge parle de cette notion dans la localisationdes stations radar. En e�et, nous devons observer un certain nombre d'en-droits stratégiques. Toutefois, nous souhaitons placer un nombre minimumde stations radar, par exemple pour des raisons �nancières. Une questionnaturelle découle de ce problème : comment pouvons-nous déterminer un en-semble d'emplacements dans lequel placer ces stations ? Tout d'abord, nousmodélisons cette situation avec le graphe suivant. L'ensemble des sommets re-présente les emplacements à observer et il existe une arête entre les sommetsx et y si d'un endroit x ou y, il est possible d'observer l'autre emplacement.

66

Un ensemble acceptable d'endroits où placer des radars correspond à un en-semble dominant dans ce graphe, et nous souhaitons trouver un tel ensemblede taille minimale.

Nous avons un autre problème similaire dans les centrales nucléaires. Dansce cas, il est possible pour un gardien posté en x ou y d'observer l'autreendroit tactique, à savoir y ou x respectivement. Combien de gardes sontnécessaires pour observer tous les endroits et où doivent-ils être situés ? Laréponse correspond à nouveau à un ensemble dominant minimum.

De même, supposons que nous ayons des liens de communication entredi�érentes villes et nous souhaitons mettre en place des stations de transmis-sion dans quelques-unes des villes de sorte que chaque ville puisse recevoir unmessage d'au moins une des stations émettrices. D'après les explications deRoberts [Rob87, p. 63], en 1968, Liu souligne que nous sommes de nouveauà la recherche d'un ensemble dominant.

Wu et Li [WL99] utilise en pratique l'aspect connexe de l'ensemble do-minant. Ce dernier est davantage mis en évidence dans le routage, dont no-tamment celui de MANET, Mobile Ad-hoc NETworks. En e�et, le routageest un mécanisme qui détermine les chemins à suivre pour transmettre desdonnées d'un expéditeur jusqu'à un certain nombre de destinataires. Le rou-tage trouve une application dans beaucoup de réseaux tels que les réseauxde données électroniques comme l'Internet, les réseaux de transports et le ré-seau téléphonique. Dans cette application, un ensemble dominant minimumconnexe est utilisé comme réseau principal de communication et nous attei-gnons tous les sommets du graphe en faisant passer le message aux voisinsdes sommets de cet ensemble.

4.2 Le PoC concernant l'Ensemble Dominant

Comme nous avons vu dans le chapitre précédent, nous pouvons parlerdu PoC d'un graphe concernant un problème pourvu qu'il existe une versionconnexe de celui-ci. Puisque c'est le cas du Problème de l'Ensemble Dominant(DS), nous allons étudier le PoC pour ce problème. Dans un premier temps,encadrons le PoC de n'importe quel graphe connexe. Ensuite, a�nons cetteétude en fonction de l'ordre et du degré minimum du graphe. En�n, nousregarderons la valeur maximale du PoC pour certaines familles de graphes.

67

4.2.1 Encadrement du PoC

Théorème 4.1 (Encadrement du PoC.). Pour tout graphe connexe G, sonPoC est dans l'intervalle [1, 3[. De plus,

supG graphe connexe

PoC(G) = 3.

Dans la preuve de ce théorème, nous allons utiliser le lemme suivant quinous dit : la distance entre une composante connexe d'un DS avec toutes lesautres composantes connexes de celui-ci est au maximum 3.

Lemme 4.2. Soit G un graphe connexe sans DS connexe. Soit D un en-semble dominant de G. Soient C1 une composante connexe de D, C2 unedes composantes connexes de D les plus proches de C1. Alors soit il existev ∈ V (G) \ D tel que v est voisin d'un sommet de C1 et C2, soit il existev1, v2 ∈ V (G) \D tels que v1 et v2 sont voisins et vi est voisin d'un sommetde Ci, pour i = 1, 2.

Démonstration du Lemme 4.2. Soit P = v1...vn un C1 − C2 chemin de lon-gueur minimum, c'est-à-dire un chemin réalisant les distances d(C1, C2) etd(C1,∪ki=2Ci), où C3, . . . , Ck sont les éventuelles autres composantes connexesde D. Par dé�nition du chemin, v1 ∈ C1, vn ∈ C2 et vi ∈ V (G) \D. Par l'ab-surde, supposons que les deux composantes connexes ne sont pas reliées parun chemin de longueur 2 ou 3. Dès lors, P contient au moins 5 sommets.Puisque C2 est une des composantes les plus proches de C1 et que P est undes C1−C chemins de longueur minimum, où C est une composante connexede D, nous déduisons que v3 est voisin d'aucun sommet de D, ce qui amènenotre contradiction puisque D est un ensemble dominant.

Démonstration du Théorème 4.1. Puisque le DS est un problème de mini-misation, nous avons toujours 1 6 PoC. Par ailleurs, nous allons montrerque le PoC est majoré par 3 et que cette borne supérieure est minimale.Tout d'abord, nous allons trouver une famille de graphes ayant un PoCaussi proche que l'on souhaite de 3. Ensuite, nous prouverons que le PoC estborné par 3.

Pour cette première étape, il su�t de considérer la famille des cyclesd'ordre multiple de 3. Soit Gk un cycle avec 3k sommets, où k ∈ N0. Numé-rotons les sommets de 1 à 3k en suivant l'ordre de voisin en voisin. Montronsqu'un ensemble dominant minimum de Gk possède k sommets. Une solutionoptimale est la suivante : prenons tous les sommets ayant un numéro modulo3 égal à 2, comme l'illustre la Figure 4.1. Nous avons donc sélectionné unsommet sur 3 (toujours celui du milieu). Remarquons que dans un cycle, tous

68

x1x2

x3

x4

x5x6x3k−5

x3k−4

x3k−3

x3k−2

x3k−1x3k

Gk. . .

Figure 4.1 � Cycle d'ordre 3k avec {xi|1 6 i 6 3k et imod 3 = 2} commeensemble dominant minimum.

les sommets ont exactement deux voisins. L'ensemble choisi est bien une so-lution car chaque sommet couvre ses deux voisins. De plus, véri�ons que k estla cardinalité minimale d'un ensemble dominant. Par l'absurde, supposonsqu'il existe un tel ensemble de j sommets avec 0 < j < k. Puisque chaquesommet a exactement deux voisins, dans le meilleur des cas, cet ensemble dej sommets ne couvrira que 3j sommets. Or 3j < 3k. Donc cet ensemble nepeut pas être dominant. D'où la contradiction.

De plus, un ensemble dominant minimum connexe dans Gk a exactement3k − 2 sommets. En e�et, il su�t de prendre les sommets numérotés de 1 à3k − 2. Cet ensemble est clairement connexe et les deux sommets à couvrir,à savoir le 3k−1ième et le 3kième, ont chacun un voisin dans l'ensemble choisi,à savoir le 3k − 2ième et le premier.

Véri�ons que 3k − 2 est la cardinalité minimale d'un ensemble dominantconnexe. En e�et, nous cherchons un ensemble connexe de i sommets, c'est-à-dire i sommets dont la numérotation est consécutive. Pour englober tousles cas, nous supposons que le numéro après 3k est 1. Si i < 3k−2 alors nousavons au moins 3 sommets non-sélectionnés avec une numérotation consécu-tive. Disons le jième, le j + 1ième et le j + 2ième. Alors le sommet j + 1 ne serapas couvert car ses deux seuls voisins sont les jième et j + 2ième sommets quine sont pas sélectionnés. Donc 3k − 2 est bien la cardinalité minimale.

Nous obtenons :

PoC(Gk) =3k − 2

k−→k→+∞

3.

Il nous reste à montrer que le PoC de tout graphe est majoré par 3.

69

Si un ensemble dominant minimum d'un graphe est déjà connexe alors sonPoC vaut 1. Considérons les graphes connexes sans DS minimum connexe.Soient G un tel graphe et k > 2 le nombre de composantes connexes d'unDS minimum D �xé. Soient C1 une composante connexe de D et C2 unedes autres composantes connexes de D les plus proches de C1. Le Lemme4.2 nous dit que C1 et C2 peuvent être connectées en ajoutant au plus deuxsommets à D. Répétons ce processus au total k − 1 fois pour relier toutesles composantes connexes. L'ensemble obtenu DC est dominant connexe etde cardinalité pas forcément minimale. Dès lors, la cardinalité minimale d'unensemble dominant connexe est majorée par |DC | qui lui-même l'est par|D|+ 2(k − 1). Nous terminons par :

PoC(G) =|DC ||D|

6|D|+ 2(k − 1)

|D|= 1 +

2(k − 1)

|D|.

Or chaque composante connexe possède au moins un sommet, d'où |D| > k.Donc

PoC(G) 6 1 +2k − 2

k= 3− 2

k< 3.

4.2.2 Étude du PoC en fonction de l'ordre d'un grapheet de son degré minimum

Nous allons étudier le PoC de graphes en fonction de deux paramètres :l'ordre et le degré minimum du graphe. Cette étude a pour but d'a�nerl'encadrement précédent. Nous allons voir quatre de mes résultats. Le premiernous dit que si un graphe a beaucoup d'arêtes bien réparties alors son PoCvaut 1. Le second a�rme que nous pouvons trouver un graphe où les sommetsont au moins un certain nombre �xé de voisins et avec un PoC aussi prochede 3 que nous le désirons. Le troisième nous assure que la valeur maximaledu PoC est d'autant plus petite que le degré minimum est grand. Et ledernier nous donne une majoration plus précise du PoC de graphes où ledegré minimum est proportionnel à son ordre.

Le PoC en fonction de l'ordre et d'un grand degré minimum du

graphe

Le théorème suivant peut être interprété suivant di�érents angles. Toutd'abord, si un graphe a beaucoup d'arêtes bien réparties, alors un des en-sembles dominants minimums est connexe. Ensuite, si nous avons un grapheG à n sommets avec un degré minimum n − i proche du plus grand degré

70

possible de G, à savoir n − 1, alors, à partir d'un certain rang (pour n), lePoC de G vaut 1.

Théorème 4.3. Soient n > 3 un naturel et i > 1 un autre naturel tel quen > (i− 1)i+ 1. Si un graphe est d'ordre n et de degré minimum n− i alorsson PoC vaut 1.

Démonstration. Par le Théorème 3.2, il su�t de trouver un ensemble domi-nant minimum qui soit connexe pour prouver que le PoC vaut 1. Nous allonsdécomposer cette preuve en trois cas : i = 1, 2 ou > 3.

Si un graphe G à n sommets est de degré minimum n − 1 alors tousles sommets de G ont n − 1 voisins, c'est-à-dire G = Kn. Dès lors, un seulsommet forme un ensemble dominant minimum qui, de plus, est connexe.

Soit G un graphe avec n sommets et de degré minimum n− 2. S'il existeun sommet de degré n − 1, alors un DS minimum contient uniquement cesommet et forme un ensemble connexe. Sinon, tous les sommets de G sontde degré n − 2. Par conséquent, un ensemble dominant, connexe ou non,contiendra au moins 2 sommets. Soit v un sommet de degré n − 2. PosonsN(v) = {ui|i = 1, ..., n− 2}. Alors V (G) \ {v, ui|i = 1, ..., n− 2} ne contientqu'un seul élément, disons u. Puisque u et v ne sont pas voisins et que u an− 2 voisins, ceux-ci sont exactement les ui, où i = 1, ..., n− 2. Dès lors, unDS minimum est {v, u1} car v domine tous les ui et lui-même et u1 domineu. De plus, cet ensemble est connexe.

Soit G un graphe avec n sommets et de degré minimum n− i où i > 3 etn > (i− 1)i+ 1. Discutons des di�érents cas en fonction de ∆(G).

Si ∆(G) = n−1 alors il existe un sommet v ayant tous les autres sommetscomme voisins. Par conséquent, un DS minimum est {v}, ensemble connexe.

Si ∆(G) = n− 2 alors il existe un sommet v1 ayant n− 2 voisins, disonsu1, ..., un−2. Posons v2 le sommet non-adjacent à v1. Puisque v2 a au moinsn− i > 1 voisin(s) parmi ceux de v1, il existe k tel que {v1, v2} ⊆ N(uk). Ilsu�t de prendre {v1, uk} comme DS minimum, qui est connexe.

Soit 3 6 k 6 i. Si ∆(G) = n − k, alors il existe un sommet v1 de degrén−k. Posons v2, ..., vk les sommets non-adjacents à v1 et u1, ..., un−k les voisinsde v1. S'il existe r ∈ {1, ..., n − k} tel que {vi|i = 1, ..., k} ⊆ N(ur), alors{v1, ur} est un DS minimum, de plus, connexe. Sinon l'assertion suivante estvéri�ée :

∀1 6 r 6 n− k,∨ks=2vs /∈ N(ur).

Par conséquent, l'intersection de tous les voisinages de vs, où s = 2, ..., k,est vide. Posons As = N(vs) pour 1 6 s 6 k. Puisque ∩ks=2As = ∅, Ak estinclus dans le complémentaire de ∩k−1

s=2As. De plus, nous avons les inégalités

71

suivantes, pour tout s :

|As| = |N(vs)| = d(vs) > δ(G) = n− i.

Nous déduisons ces relations :

|Ak| 6

∣∣∣∣∣k−1⋃s=2

Acs

∣∣∣∣∣ 6k−1∑s=2

|Acs| 6k−1∑s=2

i = (k − 2)i.

Or |Ak| > n − i. Dès lors, n − i 6 (k − 2)i, c'est-à-dire n 6 (k − 1)i, pour3 6 k 6 i. Contradiction avec notre hypothèse n > (i− 1)i+ 1.

Le PoC en fonction de l'ordre et d'un petit degré minimum du

graphe

Si un graphe a peu d'arêtes, il paraît naturel que son PoC soit aussi grandque possible. Le théorème suivant exprime exactement cette idée.

Théorème 4.4. Soit δ ∈ N0. Il existe une suite de graphes (Gk)k telle que

∀k, δ(Gk) = δ et PoC(Gk) −→k→+∞

3.

Démonstration. Si δ vaut 2, nous avons déjà vu dans la preuve du Théorème4.1 que les cycles remplissent ces conditions. De façon similaire, nous pouvonsmontrer que les chemins de longueur multiple de 3 forment une telle suite.Par conséquent, nous pouvons considérer δ > 3.

Soit k > 1. Comme l'illustre la Figure 4.2, le kième graphe, Gk, est décritcomme suit. Il est formé de k cliques de taille δ+1 et de k−1 cliques de tailleδ−1. Toutes ces cliques sont agencées en alternance selon un chemin. Tous lessommets des petites cliques sont voisins à un seul même sommet de la grandeclique précédente et suivante. Un tel sommet est dit point d'articulation. Nousconstruisons notre graphe de telle manière à ce qu'un point d'articulation nesoit voisin que d'une seule petite clique. De plus, un point d'articulation dela ième grande clique et adjacent aux sommets d'une petite clique précédentesera noté v(i,1) tandis que celui voisin à la petite clique suivante est nommév(i,2).

Étudions le degré de tous les sommets. Soit v un sommet de Gk. Si v estun point d'articulation alors v est voisin des sommets d'un K(δ−1) et appar-tient à un K(δ+1). D'où, le degré de v vaut (δ − 1) + δ = 2δ − 1. Sinon, siv est un sommet d'un K(δ+1) alors son degré est δ. Sinon, v appartient à unK(δ−1), disons le iième, et il est voisin des sommets v(i,2) et v(i+1,1). Dès lors,le degré de v est égal à (δ − 2) + 2 = δ.

72

v(1,1)

...

...

v(i,1)

...

v(i,2)

...

...

v(k,1)

...

1erKδ+1

iièmeKδ+1

kièmeKδ+1

1erKδ−1

(i− 1)ièmeKδ−1

iièmeKδ−1

(k − 1)ièmeKδ−1

Figure 4.2 � Construction du graphe Gk.

Donc δ(Gk) vaut δ, et ∆(Gk) est égal à 2δ−1. Nous allons montrer qu'un en-semble dominant minimum de Gk contient k sommets et que si nous ajoutonsla contrainte de connexité, alors il y aura 3k − 3 sommets. Par conséquent,PoC(Gk) = 3k−3

k−→k→+∞

3, ce que nous désirons.

Cherchons un ensemble dominant de k sommets et véri�ons qu'il est mi-nimum. Remarquons que l'ordre de Gk vaut

(δ + 1)k + (δ − 1)(k − 1) = 2δk − δ + 1,

puisque Gk est l'union de kK(δ+1) et de (k − 1)K(δ−1). L'ensemble

{v(i,1)|1 6 i 6 k}

73

est bien dominant. De plus, il est de cardinalité minimale. En e�et, si unDS aau plus k−1 éléments, alors ceDS domine au plus (2δ−1+1)(k−1) = 2δk−2δsommets puisque ∆(Gk) = 2δ− 1 et qu'un sommet domine ses voisins et lui-même. Or Gk possède 2δk − δ + 1 sommets et 2δk − 2δ < 2δk − δ + 1. Donctous les sommets ne peuvent être dominés par ce DS. Contradiction.

L'ensemble DC comprenant tous les points d'articulation et un sommetde chaque K(δ−1) est bien un ensemble dominant connexe. Il possède(2k− 2) + (k− 1) = 3k− 3 sommets. Et tout ensemble dominant connexe deGk est de taille au moins 3k − 3 car un tel ensemble doit contenir au moinsun sommet du premier et du dernier K(δ+1) (sinon les autres sommets de cesKδ+1, qui ne sont pas d'articulation, ne seront pas dominés) et la distanceentre le premier et le dernier K(δ+1) vaut 3k − 4. Donc l'ensemble DC estdominant minimum connexe.

La décroissance du PoC maximum en fonction du degré minimum

Le théorème suivant nous dit exactement que la valeur maximale du PoCdécroît en fonction du degré minimum.

Théorème 4.5. Soit n un naturel supérieur à 4. Prenons la fonction fdé�nie sur {1, ..., n− 1} dans R par

f(δ) = maxδ(G)=δ,|G|=n

PoC(G).

Alors, la fonction f est décroissante.

Démonstration. Puisque le domaine de f est discret, il su�t de montrer que

∀δ ∈ {1, ..., n− 2}, f(δ) > f(δ + 1).

Soit G un graphe connexe avec n sommets et un degré minimum égal à δ+1.Soit D un ensemble dominant minimum dans G. Pour chaque v ∈ V (G) \D,il existe uv ∈ D voisin de v dans G. Pour tous les sommets v en dehors deD, �xons-nous un tel élément uv. Prenons E l'ensemble des arêtes suivant{vuv|v ∈ V (G) \D} auquel nous ajoutons toutes les arêtes nécessaires pourque chaque composante connexe de D soit un arbre. Le graphe (V (G), E)est une forêt où chaque composante connexe est à une distance dans G de1 avec les autres composantes. La Figure 4.3 illustre cette construction surun graphe et un ensemble dominant quelconque. Prenons F un ensemble desarêtes incluant E auquel nous ajoutons toutes les arêtes de G nécessairespour rendre la forêt (V (G), F ) connexe, c'est-à-dire une arête entre certainescomposantes connexes de (V (G), E). Posons T = (V (G), F ). Ce graphe estun arbre couvrant G. Dès lors, T a n− 1 arêtes.

74

Figure 4.3 � Construction d'un sous-graphe ayant un degré minimum dé-crémenté et un DS inchangé.

De plus, il existe un sommet v ∈ V (T ) tel que dT (v) 6 δ. En e�et, parl'absurde, si ∀v ∈ V (T ), dT (v) > δ + 1 alors T a au moins δ+1

2n arêtes.

Or δ > 1, d'où δ+12

> 1. Donc T a au moins δ+12n > n arêtes, ce qui est

impossible.Posons EG(v) = {e1, ..., ek} où k > δ + 1 et tel que les i 6 δ premières

arêtes sont celles de T . Prenons H le graphe dé�ni par V (H) = V (G) etE(H) = E(G) \ {eδ+1, ..., ek}. Ce graphe est construit à partir de G : nousenlevons des arêtes incidentes à v n'appartenant pas à T pour obtenirdH(v) = δ. Il est clair que H ⊆ G, |H| = n, δ(H) = δ et T est un arbrecouvrant H. Dès lors, H est un graphe connexe et, par dé�nition de T , D estun ensemble dominant dans H. De plus, il est minimum car E(H) ⊆ E(G),V (H) = V (G) et D est minimum dans G. Par conséquent, nous obtenons lesinégalités suivantes :

PoC(G) 6 PoC(H) 6 f(δ).

En d'autres mots, pour tout graphe G d'ordre n et de degré minimum égalà δ + 1, PoC(G) 6 f(δ), c'est-à-dire f(δ + 1) 6 f(δ).

La proposition suivante nous donne une indication sur les graphes attei-gnant la valeur maximale du PoC.

Proposition 4.6. Soit n ∈ N. Le plus grand PoC des graphes d'ordre n estatteint par un graphe de degré minimum égal à 1, c'est-à-dire

max|G|=n

PoC(G) = maxδ(G)=1,|G|=n

PoC(G).

75

Démonstration. Cette proposition découle du Théorème 4.5. En e�et, si

f(δ) = maxδ(G)=δ,|G|=n

PoC(G),

alors l'énoncé de cette proposition devient :

max16δ<n

f(δ) = f(1).

Puisque f est dé�nie sur {1, ..., n− 1} et que cette fonction est décroissante,le résultat est immédiat.

Le PoC en fonction de l'ordre et d'un degré minimum proportionnel

à cet ordre

Jusqu'à présent, à un ordre �xé, nous avons étudié la valeur maximaledu PoC en fonction d'un degré minimum indépendant de l'ordre. Dès lors,une question s'impose. Si le degré minimum est proportionnel à l'ordre dugraphe, est-ce que la valeur maximale du PoC de tels graphes est majoréepar une constante entre 1 et 3 exclus ? La réponse est � oui �. Mes recherchespersonnelles ont abouti aux résultats présentés dans cette section.

Dans un premier temps, nous allons nous intéresser à la valeur maximaledu PoC pour des graphes de degré minimum égal à la moitié de l'ordre.Ensuite, nous explorerons toutes celles pour des graphes ayant un degré mi-nimum égal à n'importe quelle fraction de l'ordre.

Proposition 4.7. Soient n un naturel supérieur à 4 et δ un naturel tels queδ = n

2. Alors,

maxδ(G)=δ,|G|=n

PoC(G) < 2.

Démonstration. Il su�t de montrer que pour tout graphe G d'ordre n et dedegré minimum δ, son PoC est strictement plus petit que 2, car il en existeun nombre �ni. Soient G un tel graphe et D un ensemble dominant minimum.Discutons en fonction de la cardinalité de D.

Si |D| = 1 alors le PoC de G vaut aussi 1.Si |D| = 2 alors disons que D contient les éléments v1 et v2. Si v1v2 est

une arête de G alors PoC(G) vaut 1. Sinon puisque d(v1), d(v2) > n2, il existe

v voisin de v1 et de v2. Alors {v1, v2, v} est un ensemble dominant connexe.D'où, PoC(G) 6 3

2< 2.

Sinon |D| = k > 3. Posons D = {v1, ..., vk}. Nous avons l'assertion sui-vante :

∀vi, vj ∈ D,N(vi) ∩N(vj) 6= ∅

76

puisque d(vi), d(vj) > n2et qu'il faut au moins 3 sommets pour dominer G.

Par conséquent, pour i = 1, ..., k − 1, il existe xi ∈ V (G) tel que

xi ∈ N(vi) ∩N(vi+1).

Dès lors, D∪{xi|1 6 i 6 k− 1} forme un ensemble dominant connexe. Donc

PoC(G) 6|D|+ |{xi|1 6 i 6 k − 1}|

|D|6k + k − 1

k=

2k − 1

k< 2.

Dans la preuve de la proposition précédente, nous discutons de la cardina-lité de l'ensemble dominant minimum. Dans le contexte actuel, nous savonspar le Corollaire 1.40 qu'un tel ensemble possède au maximum δ sommets.Nous allons montrer que cette borne ne peut pas être atteinte.

Proposition 4.8. Soient n un naturel et δ > 3 tels que δ = n2. Si un graphe

G est d'ordre n et de degré minimum δ alors un ensemble dominant minimumdans G contiendra au plus δ − 1 sommets.

Démonstration. Par l'absurde, par le Corollaire 1.40, supposons qu'il existeun graphe G ayant la cardinalité d'ensemble dominant minimum exactementégale à δ. Soit v1 ∈ V (G) avec d(v1) = δ. Alors v1 domine δ + 1 sommets.Posons A = {v2, ..., vδ} le complémentaire de {v1} ∪ N(v1). Il est clair queA∪{v1} domineG. Dès lors, cet ensemble est une solution minimum. Véri�onsl'assertion suivante

∀vi, vj, vivj /∈ E(G).

Par l'absurde, supposons que vivj est une arête de G. Nous pouvons supposerque i est di�érent de 1. Alors {vk|k 6= i} domine G et est de taille inférieureà δ, ce qui est impossible.

Dès lors, pour tout v ∈ A ∪ {v1}, N(v) ⊆ N(v1). Or, v a au moinsδ voisins et v1 en a δ. Donc N(v) = N(v1). Soit u ∈ N(v1). L'ensemble{v1, u} est dominant car v1 domine ses voisins et lui-même et u domine A.Donc l'ensemble dominant minimum contient seulement 2 éléments, ce quiest strictement inférieur à δ. Contradiction.

Des deux propositions précédentes, nous déduisons le théorème suivant.Il nous donne une majoration plus précise de la valeur maximale du PoC.

Théorème 4.9. Soient n > 4 un naturel et δ > 3 tels que δ = n2. Alors,

maxδ(G)=δ,|G|=n

PoC(G) 62δ − 3

δ − 1< 2.

77

Démonstration. Soit G un graphe d'ordre n et de degré minimum δ. Nousavons vu dans la preuve de la Proposition 4.7 que si G possède k > 1 sommetsdans un ensemble dominant minimum, alors son PoC est majoré par 2k−1

k.

De plus, pour un tel graphe G, par la Proposition 4.8, un ensemble dominantminimum a une cardinalité entre 1 et δ − 1. Puisque la suite

(2k−1k

)kest

croissante, nous obtenons

supδ(G)=δ,|G|=n

PoC(G) 62(δ − 1)− 1

δ − 1=

2δ − 3

δ − 1.

Il faut savoir que la majoration donnée par le Théorème 4.9 n'est pas for-cément atteinte. Dès lors, il existe peut-être une plus petite borne supérieure.Cependant, nous avons un autre résultat intéressant. La proposition suivanteminore par 3

2la valeur maximale du PoC des graphes de degré minimum δ

et d'ordre 2δ.

Proposition 4.10. Pour tout k > 4, il existe un graphe d'ordre 2k, de degréminimum k et ayant un PoC égal à 3

2, c'est-à-dire

3

26 max

δ(G)=k,|G|=2kPoC(G).

Démonstration. Nous allons construire un tel graphe par récurrence. Pourcela, nous supposerons les hypothèses suivantes. Le graphe Gk, d'ordre 2k, aun degré minimum égal à k et un degré maximum égal à 4+2(k−4) < 2k−1,ce qui implique qu'un ensemble dominant minimum a au moins 2 sommets.De plus, Gk a deux sommets non adjacents v1 et v2 dominant V (Gk), d'oùun ensemble dominant minimum contiendra exactement 2 sommets.

Posons Aik = {vi} ∪NGk(vi) pour i = 1, 2. Nous voulons :A1k ∩ A2

k = {u1, u2} avec u1u2 /∈ E(Gk),d(u1) = d(u2) = 4 + 2(k − 4)

et ∀v ∈ V (Gk) \ {u1, u2}, d(v) = k.De plus, nous désirons que pour tout v ∈ {u1, u2}, il existe un u ∈ A1

k \ A2k

et un t ∈ A2k \A1

k qui ne sont pas voisins de v. Pour �nir, nous demanderonsque

∀xy ∈ E(Gk), NGk(x) ∪NGk(y) 6= V (Gk).

Il en découlera que PoC(Gk) = 32.

(Cas de base) Le graphe représenté par la Figure 4.4 véri�e bien toutesles conditions précisées ci-dessus.

78

v1 v2

u1

u2

A14 A2

4

Figure 4.4 � Graphe d'ordre 8 de degré minimum 4 avec un PoC de 32.

(Etape d'induction) Soit k > 4. Supposons qu'il existe un graphe Gk

véri�ant toutes nos hypothèses. Construisons Gk+1 comme illustré par laFigure 4.5. Soient x1, x2 deux nouveaux sommets. Posons

V (Gk+1) = V (Gk) ∪ {x1, x2}

et E(Gk+1) = E(Gk) ∪ {x1a1|a1 ∈ A1k} ∪ {x2a2|a2 ∈ A2

k},

c'est-à-dire nous ajoutons aux arêtes de Gk toutes les arêtes entre x1 et leséléments de A1

k ainsi que celles entre x2 et les sommets de A2k.

u1 u2

x1 x2

A1k A2

k

Gk

Figure 4.5 � Construction de Gk+1 à partir de Gk.

Le graphe Gk+1 a bien deux sommets non adjacents dominant V (Gk+1),x1 et x2. Posons Aik+1 = {xi}∪NGk+1

(xi) pour i = 1, 2. Par construction, pouri = 1, 2, Aik+1 = {xi} ∪Aik. Dès lors, A1

k+1 ∩A2k+1 = A1

k ∩A2k = {u1, u2} avec

u1u2 /∈ E(Gk+1). Soit v ∈ {u1, u2}. Nous savons qu'il existe un u ∈ A1k \ A2

k

79

et un t ∈ A2k \A1

k non adjacents de v dans Gk. En particulier, u appartient àA1k+1 \ A2

k+1, t à A2k+1 \ A1

k+1 et ils ne sont pas voisins à v dans Gk+1.Étudions le degré des sommets de Gk+1. Nous savons que |Aik| = k + 1,

pour i = 1, 2. Dès lors, dGk+1(x1) = dGk+1

(x2) = k + 1. Puisque les ui sonttous les deux voisins des deux xi et qu'ils sont de degré 4 + 2(k − 4) dansGk, alors dGk+1

(u1) = dGk+1(u2) = 4 + 2(k− 4) + 2 = 4 + 2((k + 1)− 4). Soit

v ∈ V (Gk)\{u1, u2}. Alors, v a k voisins dans Gk et est voisin d'un des deuxxi. D'où, dGk+1

(v) = k + 1.Il reste à véri�er que

∀xy ∈ E(Gk+1), NGk+1(x) ∪NGk+1

(y) 6= V (Gk+1).

Soit xy ∈ E(Gk+1). Si x, y appartiennent à Gk alors par hypothèse de récur-rence, il existe un sommet z non adjacent à x et y dans Gk. Puisque x, y etz sont dans Gk, alors z n'est voisin ni de x ni de y dans Gk+1. Sinon soit x,soit y appartient à {x1, x2}. Nous pouvons supposer sans perte de généralitésque x = x1 et y ∈ A1

k. Si y ∈ A1k \ A2

k alors x2 n'est dominé ni par x, nipar y. Sinon y est soit u1, soit u2. Par hypothèse de récurrence, il existe unt ∈ A2

k \A1k non adjacent à y dans Gk, d'où dans Gk+1. Donc t n'est dominé

ni par y, ni par x.

Nous allons étudier la valeur maximale du PoC de graphes ayant un degréminimum proportionnel à l'ordre.

Proposition 4.11. Soient δ ∈ N0, i un naturel supérieur à 3 et n un natureltels que δ = n

i. Alors,

1 6 maxδ(G)=δ,|G|=n

PoC(G) 6 3− 2

i− 1.

Démonstration. Soient G un graphe d'ordre n et de degré minimum δ et Dun ensemble dominant minimum de G. Posons k = |D|. Notons 1 6 j 6 k lenombre de composante(s) connexe(s) de D dans G et notons ces composantes(Cs)

js=1. Posons Cs = Cs ∪

⋃c∈Cs NG(c) pour 1 6 s 6 j, l'ensemble dominé

par Cs. Puisque chaque composante possède au moins un sommet et que toutsommet est voisin d'au moins δ autres, il en découle que

∣∣Cs∣∣ > δ + 1. Deplus, nous avons les inégalités suivantes :∣∣∣∣∣

j⋃s=1

Cs

∣∣∣∣∣ 6 |V (G)| = n = iδ.

Si j < i alors pour connecter chaque composante de D dans le but d'obte-nir un ensemble dominant connexe, par le Lemme 4.2, il su�t d'ajouter au

80

plus deux sommets entre deux composantes les plus proches. Dès lors, nousdéduisons les majorations suivantes :

PoC(G) 6k + 2(j − 1)

k

= 1 +2j − 2

kj6k6 1 +

2j − 2

j

= 3− 2

jj6i−1

6 3− 2

i− 1.

Sinon, j > i. Dès lors, tous les Cs ne sont pas disjoints avec les autres Ct lesplus proches. Il y en a au plus i− 1. Par conséquent, pour connecter les i− 1composantes correspondantes, il su�t, par le Lemme 4.2, d'ajouter 2(i− 2)sommets à D (deux sommets entre deux composantes les plus proches) etj − i + 1 sommets pour les autres composantes (un seul sommet entre deuxcomposantes les plus proches). Donc,

PoC(G) 6k + 2(i− 2) + (j − i+ 1)

kj6k6

k + 2(i− 2) + (k − i+ 1)

k

=2k + i− 3

k.

Puisque la suite(

2k+i−3k

)kest décroissante, car i > 3, et que k > j > i,

PoC(G) 62i+ i− 3

i=

3i− 3

i= 3− 3

i.

Ce dernier nombre est borné supérieurement par 3− 2i−1

car i > 3.

Le théorème suivant généralise la proposition précédente.

Théorème 4.12. Soient n > 4 et δ deux naturels, K un rationnel supérieurà 3 tels que δ = n

K. Alors,

1 6 maxδ(G)=δ,|G|=n

PoC(G) 6 3− 2

dKe − 1.

81

Démonstration. Posons i = dKe. Par le Théorème 4.5, nous savons que lafonction f dé�nie par

f(δ) = maxδ(G)=δ,|G|=n

PoC(G)

est décroissante. Par la Proposition 4.11, il su�t donc de véri�er quenK

> ni, c'est-à-dire 1

K> 1dKe , ou encore 1

KdKe > 1. En e�et, nous avons la

minoration suivante : 1KdKe > 1

KK = 1.

4.3 Quelques familles particulières de graphes

Des recherches personnelles ont conduit à l'étude du PoCDS de certainesfamilles de graphes. Nous allons la découvrir dans cette section.

4.3.1 Les cographes

Dé�nition 4.13. Un cographe est un graphe construit comme suit :� tout sommet isolé est un cographe,� si G = (VG, EG) et H = (VH , EH) sont deux cographes alors

(VG ∪ VH , EG ∪ EH ∪ {(g, h)|g ∈ VG, h ∈ VH}) est un cographe,

� si G et H sont deux cographes alors leur union disjointe G∪H est aussiun cographe.

Nous pouvons montrer facilement la proposition suivante qui déterminecette classe de graphes. Brandstädt et Spinrad [BS99, p. 176] donnent d'autrescaractérisations de la classe des cographes, en plus de la suivante.

Proposition 4.14. Un cographe est un graphe qui ne contient pas de cheminformé de 4 sommets, c'est-à-dire de longueur 3, comme sous-graphe induit.En d'autres termes, un graphe est un cographe si et seulement si pour toussommets v1, v2, v3, v4, si {v1, v2}, {v2, v3} et {v3, v4} sont des arêtes du graphealors celui-ci possède au moins une des arêtes suivantes : {v1, v3}, {v1, v4}ou {v2, v4}.

La classe des cographes est une classe particulière pour le calcul duPoCDS.

Théorème 4.15. Soit G un cographe connexe. Alors G possède un ensembledominant connexe de même taille qu'un ensemble dominant minimum.

82

Démonstration. Si G = (V,E) est réduit à un sommet isolé alorsDS = CDS = V . Sinon si G possède un sommet v de degré |V | − 1 alorsDS = CDS = {v}. Sinon puisque G est connexe alors G est dé�ni par

(VH1 ∪ VH2 , EH1 ∪ EH2 ∪ {(h1, h2)|h1 ∈ VH1 , h2 ∈ VH2})

pour deux cographes H1 et H2. Puisque G ne possède pas de sommet voi-sin à tous les autres sommets, nous savons déjà qu'un ensemble dominantpossédera au moins 2 sommets. Soient h1 et h2 deux sommets de H1 etH2 respectivement. Prenons DS = {h1, h2}. Tout sommet de H2 est voisinde h1 et tout sommet de H1 l'est de h2, d'où DS est un ensemble domi-nant. Par conséquent, c'est un ensemble dominant minimum. De plus, il estconnexe.

Nous pouvons déduire immédiatement du théorème précédent le corollairesuivant.

Corollaire 4.16. Soit G un cographe connexe. Alors PoCDS(G) vaut 1.

4.3.2 Les graphes de diamètre 2

Nous allons discuter des graphes de diamètre 2.

Théorème 4.17. Soit G un graphe connexe de diamètre 2.Alors,

PoCDS(G) < 2.

Démonstration. Puisque le diamètre de G est 2, la distance entre deux som-mets quelconques est toujours majorée par 2. Soit D un ensemble dominantminimum avec 1 6 k 6 |D| composante(s) connexe(s). Les composantesconnexes de D sont distantes d'au plus 2. Par conséquent, il existe un en-semble dominant connexe de cardinalité

|D|+ (k − 1)

|D|= 1 +

k − 1

|D|6 1 +

k − 1

k= 2− 1

k< 2.

Donc PoC(G) < 2.

Grâce à l'utilisation du système GraPHedron [Mél08], nous avons pu re-marquer qu'un ensemble dominant dans des graphes d'ordre maximum 10 etde diamètre 2 possède au plus deux composantes connexes. Si cette intui-tion se véri�e pour n'importe quel graphe alors la valeur maximale du PoCpour les graphes de diamètre 2 sera d'au plus 3

2. En e�et, si un tel graphe

G possède un ensemble dominant de taille k > 2 avec deux composantes

83

connexes, alors il su�ra d'ajouter un sommet pour avoir un ensemble domi-nant connexe (car le diamètre du graphe vaut 2). D'où, PoC 6 k+1

k6 1 + 1

k.

Puisque la suite(1 + 1

k

)k>2

est décroissante, PoC 6 32. De plus, nous avons,

par la proposition suivante, que

maxG graphe connexe,diam(G)=2

PoC(G) >3

2.

Proposition 4.18. Soit n un naturel supérieur à 7. Il existe un graphed'ordre n qui soit de diamètre 2 et de PoC égal à 3

2.

Démonstration. Il su�t de considérer le graphe représenté par la Figure 4.6.Nous pouvons facilement véri�er que ce graphe est de diamètre 2. Et il est

v1 v2

v3

. . .

Figure 4.6 � Graphe d'ordre n de diamètre 2 avec un PoC de 32.

clair que {v1, v2} est un ensemble dominant minimum ainsi que {v1, v2, v3}est un ensemble dominant minimum connexe. Par conséquent, ce graphe aun PoC de 3

2.

4.4 Complexité

Nous allons nous intéresser à la complexité du calcul du PoC du Pro-blème de l'Ensemble Dominant. Nous savons que le Problème de l'EnsembleDominant est un problème d'optimisation. Cependant, nous pouvons lui as-socier le problème de décision suivant : � est-ce que le PoCDS est majoré parK ′ ? �. De plus, nous avons un problème de décision parallèle concernant leProblème SC dé�ni à la �n du chapitre 2 : � existe-t-il une SC de taille auplus K ? �. Nous allons montrer que SC se réduit polynomialement à PoCDS.

Théorème 4.19.

SC 6p PoCDS.

84

Démonstration. Nous cherchons une fonction f calculable en temps polyno-mial telle que x est une instance de SC répondant � oui � au problème dedécision correspondant si et seulement si f(x) en est une de PoCDS répondantaussi � oui � au problème de décision. Considérons l'algorithme de réductionsuivant. Soit S = {x1, ..., xn}, C = {Si|i ∈ I} et K ∈ N0 une instance deSC. Prenons le graphe suivant :

V = (C ∪ A) ∪ (S ∪ {z}) où A = {at|t ∈ S ∪ {z}}

et E = {(s, C)|s ∈ S,C ∈ C , s ∈ C} ∪ {(at, t)|t ∈ S ∪ {z}} ∪ {(z, Si)|i ∈ I}.En d'autres termes, les éléments de S et de C sont modélisés par des sommets,et un sommet s de S est voisin à un élément C de C si s ∈ C. Tous lessommets de C sont voisins d'un sommet z, lui-même voisin d'un sommetisolé az. De plus, chaque sommet s de S est voisin d'un sommet isolé as.La Figure 4.7 représente une instance de SC et son graphe obtenu par laréduction polynomiale.

s1 s2 s3

s1 s2 s3

z

as1 as2 as3

az

C1 C2 C3 C4

C1 C2 C3 C4

Figure 4.7 � Une instance de SC avec sa réduction polynomiale.

Prenons K ′ = K+n+1n+1

, où n = |S|.Il est clair que ce graphe peut être construit en temps polynomial.Véri�ons maintenant que (S,C ) a une SC de taille au plus K si et seule-

ment si le graphe G correspondant a un PoCDS majoré par K ′.(⇒) Supposons que (S,C ) possède une SC de taille au plus K. Tout

ensemble dominant de G = (V,E) contiendra au moins soit t, soit at, pourtout t ∈ S ∪ {z}, puisque le degré de tous les sommets de A vaut 1. Enfait, S ∪ {z} est un ensemble dominant. Par conséquent, c'est un ensembledominant minimum. De plus, pour trouver un ensemble dominant connexe, ilsu�t de connecter les éléments de S ∪ {z}, c'est-à-dire trouver une SC dans(S,C ). Puisque (S,C ) en possède une d'au plus K éléments, nous pouvonsmajorer le PoCDS par K+n+1

n+1= K ′.

85

(⇐) Soit (G,K ′) une instance de PoCDS calculée à partir de (S,C , K)par l'algorithme de réduction. Supposons que G possède un PoCDS majorépar K+n+1

n+1. Nous savons que S ∪ {z} est un ensemble dominant minimum,

d'où |DS(G)| = n + 1. De plus, G a un ensemble dominant connexe D, detaille au plus K+n+1. Puisque tous les éléments a de A sont de degré 1, soita, soit le voisin de a qui se trouve dans S∪{z} est/sont dansD. PuisqueD estconnexe, si a appartient à D alors son voisin v appartient aussi à D. Or D estde cardinalité minimale, d'où v ∈ D et a /∈ D. Par conséquent, S ∪{z} ⊆ D.Et nous savons qu'il faut au plus K sommets pour connecter ces sommets.Par ailleurs, connecter ces sommets revient exactement à trouver un SC dans(S,C ), par dé�nition de G. Donc (S,C ) possède une SC de taille au plusK.

Le théorème suivant, conséquence du théorème précédent, nous montrela di�culté du calcul du PoC.

Théorème 4.20. Le Problème de décision PoCDS 6 K ′ est NP -complet.

Démonstration. Nous avons déjà vu dans le chapitre 2 que le Problème SCest NP -complet. Nous allons utiliser la Proposition 2.11 : puisque SC estNP -complet et que SC 6p PoCDS, il su�t de véri�er que PoCDS est dansNP pour que PoCDS soit aussi NP -complet. En e�et, il su�t de considérerl'Algorithme 8 en temps polynomial.

Nous avons déjà vu dans le Chapitre 2 que trouver un ensemble dominantminimum est un problème NP -complet mais son problème d'optimisationcorrespondant est approximable avec un rapport de 1 + ln(|G|). De plus, ceproblème d'optimisation n'est pas (1 − ε) log(|G|)-approximable, pour toutε > 0, sans que NP ⊆ Time(nlog(logn)). Par ailleurs, Haynes [HHS98], Ko-walik et Asano [KA06] a�rment que le Problème de l'Ensemble DominantConnexe Minimum est aussi NP -complet. Cependant, il existe un algorithmepolynomial permettant de trouver un ensemble dominant connexe à partird'un ensemble dominant minimum, et ceci avec une certaine garantie sur lacardinalité de l'ensemble dominant connexe. Le théorème suivant énonce ceprincipe.

86

Algorithme 8: Algorithme non-déterministe véri�ant qu'un graphe aun PoCDS majoré par K ′

Entrées : G graphe connexe, K ′ ∈ [1, 3] un rationnelSortie : Vrai si et seulement si PoCDS(G) 6 K ′

débutSoient D et CD deux ensembles de sommets de G tels que|CD||D| 6 K ′ et CD est un ensemble connexe;

ds←− faux;pour tous les sommets v de G faire

si v /∈ D alors

pour tous les voisins u de v fairesi u ∈ D alors

ds←− vrai;�n

�n

si ¬ds alorsretourner faux ;

�n

ds←− faux;�n

�n

cds←− faux;pour tous les sommets v de G faire

si v /∈ CD alors

pour tous les voisins u de v fairesi u ∈ CD alors

cds←− vrai;�n

�n

si ¬cds alorsretourner faux ;

�n

cds←− faux;�n

�n

retourner vrai ;�n

87

Théorème 4.21. Dans tout graphe, trouver un ensemble dominant à partird'un ensemble dominant minimum est 3-approximable.

Démonstration. Considérons l'Algorithme 9 qui est polynomial.Il est évident que la solution retournée est un ensemble dominant connexe.

Algorithme 9: Algorithme 3-approximable permettant de trouver unCDS à partir d'un DS minimum.Entrées : un graphe connexe G = (V,E), un ensemble dominant

minimum DSortie : un ensemble dominant connexe CD

débutColorier chaque composante connexe de D via une exploration degraphe;CD ←− D;tant que CD a plusieurs composantes connexes faire

Soit C une composante connexe de CD;Trouver un plus court chemin P entre C et les autrescomposantes connexes de CD en parcourant les voisins desvoisins des éléments de C;CD ←− CD ∪ V (P );Colorier d'une même couleur C, P et la composante connexeadjacente à P .

�n

retourner CD ;�n

De plus, l'algorithme utilise le principe suivant, qui est énoncé par le Lemme4.2 : dans un ensemble dominant, une composante connexe est séparée desautres composantes par un chemin contenant au plus deux sommets. Le Théo-rème 4.1 utilise cette construction et a�rme que

|CD||D|

6 3, (⊕)

où CD est la solution retournée par l'Algorithme 9 et D est un ensembledominant minimum. Puisqu'un ensemble dominant minimum a une car-dinalité inférieure à celle d'un ensemble dominant connexe, en particulier|D| 6 |CDS|, où CDS est un ensemble dominant connexe minimum, alorsnous déduisons de l'inégalité (⊕) :

|CD| 6 3|D| 6 3|CDS|,ce qui prouve la 3-approximabilité de l'Algorithme 9.

88

Chapitre 5

Conclusion

Ce mémoire étudie le concept récent du Prix de la Connexité dans laThéorie des Graphes. Le concept a été analysé dans le cadre du Problèmede Couverture des Arêtes par des Sommets par Cardinal et Levy. Vu lesimportantes applications de l'Ensemble Dominant, il est naturel de se poserla question suivante : quel est le Prix de la Connexité pour le problème del'Ensemble Dominant d'un graphe ou d'une classe de graphes ?

Dans un premier temps, nous avons trouvé un encadrement du Prix dela Connexité de n'importe quel graphe pour le problème de l'Ensemble Do-minant. Ce prix appartient en fait à l'intervalle [1, 3[. Ensuite, nous avonsmené une étude plus approfondie en fonction du degré minimum et de l'ordred'un graphe. Nous avons montré qu'un graphe avec un grand degré minimumpossède un ensemble dominant minimum qui soit connexe. De plus, il existeun graphe possédant un petit degré minimum et dont le Prix de la Connexitéest proche de 3.

Nous avons également examiné la complexité du calcul du Prix de laConnexité pour l'Ensemble Dominant. Il s'avère que ce calcul est di�cilepuisque nous avons établi que le calcul du rapport entre la cardinalité d'unensemble dominant minimum et celle d'un ensemble dominant minimumconnexe est NP -complet.

Par ailleurs, ce mémoire expose, dans les grandes lignes, la théorie dela complexité Par ailleurs, ce mémoire aborde la notion d'algorithme d'ap-proximation, algorithme de complexité polynomiale fournissant une solutionproche d'une optimale pour un problème d'optimisation. Les problèmes del'Ensemble Dominant et de Couverture par des Ensembles sont liés par deuxrelations particulières, dites réductions linéaires. Il existe deux réductionslinéaires entre le Problème de l'Ensemble Dominant et le Problème de Cou-verture par des Ensembles telles que le premier problème est α-approximablesi et seulement si le second l'est aussi. Ces réductions permettent donc de

89

translater tout résultat d'(in)approximation d'un problème vers le second.Ce mémoire o�re aussi l'opportunité de s'intéresser à d'autres questions

telles que l'étude du Prix de la Connexité pour d'autres familles de graphesou encore l'étude du Prix de la Connexité en fonction de di�érents paramètrescomme le diamètre, ...

90

Bibliographie

[ACG+99] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation :Combinatorial optimization problems and their approximabilityproperties. Springer Verlag, 1999.

[BS99] A. Brandstädt and J.P. Spinrad. Graph classes : a survey. Societyfor Industrial Mathematics, 1999.

[Car08] O. Carton. Langages formels, calculabilité et complexité, 2008.

[CL08] Jean Cardinal and Eythan Levy. Connected Vertex Covers inDense Graphs. In Approximation, Randomization and Combina-torial Optimization. Algorithms and Techniques : 11th Internatio-nal Workshop, APPROX 2008 and 12th International Workshop,RANDOM 2008, Boston, MA, USA, August 25-27, 2008, page 35.Springer-Verlag New York Inc, 2008.

[Coo71] S.A. Cook. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory ofcomputing, page 158. ACM, 1971.

[Die00] R. Diestel. Graph theory, Graduate Texts in Mathematics Vol.173, 2000.

[FM09] H. Fernau and D.F. Manlove. Vertex and edge covers with cluste-ring properties : Complexity and algorithms. Journal of DiscreteAlgorithms, 7(2) :149�167, 2009.

[GJ+79] M.R. Garey, D.S. Johnson, et al. Computers and Intractability :A Guide to the Theory of NP-completeness. wh freeman SanFrancisco, 1979.

[HHS98] T.W. Haynes, ST Hedetniemi, and P.J. Slater. Fundamentals ofdomination in graphs. CRC, 1998.

[KA06] L. Kowalik and T. Asano. of Proceedings : Algorithms and Com-putation : 17th International Symposium, ISAAC 2006. 2006.

[Kan92] V. Kann. On the approximability of NP-complete optimizationproblems. 1992.

91

[KR08] S. Khot and O. Regev. Vertex cover might be hard to approximateto within 2-[epsilon]. Journal of Computer and System Sciences,74(3) :335�349, 2008.

[KZ98] M. Karpinski and A. Zelikovsky. Approximating dense cases ofcovering problems. In Network design : connectivity and facilitieslocation : DIMACS Workshop, April 28-30, 1997, page 169. AmerMathematical Society, 1998.

[Lev09] E. Levy. Approximation Algorithms for Covering Problems inDense Graphs. 2009.

[Mél08] H. Mélot. Facet de�ning inequalities among graph inva-riants : The system GraPHedron. Discrete Applied Mathematics,156(10) :1875�1891, 2008.

[Pie] W. Pierre. Introduction à la calculabilité : cours et exercicescorrigés, 2e cycle (Sciences SUP).

[PP94] C.H. Papadimitriou and CH Papadimitriou. Computational com-plexity. Addison-Wesley Reading, MA, 1994.

[Rob87] F.S. Roberts. Graph theory and its applications to problems ofsociety. Society for Industrial Mathematics, 1987.

[RS97] G. Rozenberg and A. Salomaa. Handbook of Formal Languages :Linear modeling : background and application. Springer Verlag,1997.

[Sav82] C. Savage. Depth-�rst search and the vertex cover problem. In-formation Processing Letters, 14(5) :233�235, 1982.

[TH04] C. Teuscher and D.R. Hofstadter. Alan Turing : Life and legacyof a great thinker. Springer Verlag, 2004.

[Vaz04] V.V. Vazirani. Approximation algorithms. Springer, 2004.

[WB10] Valika K. Wan and Khanh Do Ba. Set Cover and Applica-tion to Shortest Superstring. http://www.cs.dartmouth.edu/

~ac/Teach/CS105-Winter05/Notes/wan-ba-notes.pdf, 22 mai2010.

[WL99] J. Wu and H. Li. On calculating connected dominating set fore�cient routing in ad hoc wireless networks. In Proceedings of the3rd international workshop on Discrete algorithms and methodsfor mobile computing and communications, page 14. ACM, 1999.

92