these

Informations

• Publié par: Shaen
• Nombre de lectures: 58
• Langue: Français

Extrait

N d’ordre : 438
N attribué par la bibliothèque : 07ENSL0438
ÉCOLE NORMALE SUPÉRIEURE DE LYON
Laboratoire de l’Informatique du Parallélisme
THÈSE
présentée et soutenue publiquement le 17 décembre 2007 par
Laurent LYAUDET
pour l’obtention du grade de
Docteur de l’École Normale Supérieure de Lyon
spécialité : Informatique
au titre de l’École doctorale de mathématiques et d’informatique fondamentale de Lyon
Graphes et hypergraphes :
complexités algorithmique et algébrique
Directeurs de thèse : Jacques MAZOYER
Ioan TODINCA
Après avis de : Pierre FRAIGNIAUD
Stéphan THOMASSÉ
Devant la commission d’examen formée de :
Alain BRETTO Membre
Arnaud DURANDe
Pierre FRAIGNIAUD Membre/Rapporteur
Jacques MAZOYERe
Stéphan THOMASSÉ Membr
Ioan TODINCA MembreÀ Arnaud et Vincent.Remerciements
Je tiens tout d’abord à remercier Vincent Bouchitté pour la qualité des en-
seignements qu’il m’a donné en cryptologie et en théorie des graphes, pour
m’avoir accepté comme stagiaire de DEA puis comme doctorant. Ce mémoire
est dédié à la sienne ainsi qu’à celle de mon frère Arnaud.
Je veux aussi remercier mes deux directeurs de thèse : Jacques Mazoyer
pour m’avoir garanti dès le décés de Vincent que je pourrai finir ma thèse
et Ioan Todinca pour avoir suivi de son mieux depuis Orléans mes avancées
scientifiques ainsi que pour ses relectures précises de mes articles et de ce ta-
puscrit. Votre aide à tous deux m’a été précieuse.
Je remercie Stéphan Thomassé et Pierre Fraigniaud d’avoir accepté d’être
les rapporteurs de cette thèse, ainsi qu’Alain Bretto et Arnaud Durand qui ont
accepté d’être membres de mon jury de thèse.
Jeg takker Uffe Flarup, forbi han havde tilladet mig hen til hjælp mine graf
teori sikkerhed i algebraisk “complexity”. Jeg er tilfreds jeg mødte Uffe og vi
arbejder sammen. Mange tak Uffe ! Je remercie aussi Pascal Koiran de m’avoir
permis de découvrir la complexité algébrique et d’avoir partagé sa probléma-
tique avec moi.
Je remercie Guillaume Malod pour sa relecture et ses nombreux commen-
taires sur la partie complexité algébrique de ce mémoire ainsi que pour nos
discussions sur ce sujet.
Il est temps d’attaquer la longue liste des remerciements de mes amis
thésards. Je commence par Sylvain Périfel qui m’a autorisé à plagier honteuse-
ment son chapitre de définitions et de rappels des classes de bases de complex-
ité pour le transférer de sa thèse à la mienne. Je poursuis avec Florent Becker
qui a tenté vainement de me ravir le titre de mec le plus classe de l’équipe
à l’aide de ressources internet telles tubgirl (google image – même moi j’au-
rai pas osé... enfin seulement après le repas), Damien Regnault pour ses pains
au chocolat, Jean-Baptiste Rouquier pour son harmonographe, Sylvain Sené
pour sa bonne humeur, Stéphane Leroux pour avoir réussi à faire des blagues
plus mauvaises que les miennes et m’avoir enseigné un peu de QiGong, Victor
Poupet pour avoir sauvé la langue anglaise de mes phrases les plus moches en
me corrigeant parfois, Vincent Nesme pour les séances de musique classique et
l’incitation à la concentration (conscience ou « awareness » comme dirait Van
Damme : il a une paire de ciseaux à la main !), ...
Je remercie aussi les autres membres de l’équipe MC2 et notamment Eric
iii Remerciements
Thierry pour des discussions scientifiques qui m’ont permis de partager cer-
taines de mes interrogations.
Je remercie Maurice Tchuente pour m’avoir invité au Cameroun (pour le
travail, si, si) et son accueil. Je remercie Paulin Melatagia, René Ndoundam
et les autres membres du laboratoire d’informatique de Yaoundé pour leur
chaleureux accueil.
Je remercie les membres de ma famille et les amis qui sont venus assister
à ma soutenance de thèse. Je remercie ma mère pour avoir fait une relecture
ortho-grammatico-typographique de ce document et m’avoir aidé à préparer
le pot (l’épreuve la plus dure d’une thèse).
Je remercie les membres du Taekwondo Club du parc. Votre companie et les
entraînements ont souvent été mon rocher. Je remercie Frédéric Bendahmane
d’avoir vaincu sa leucémie ; je n’aurai pas aimé que ma thèse finisse comme
elle avait commencée.
Toutes les personnes que j’ai injustement oubliées peuvent m’envoyer un
courrier (électronique ou non) de protestation :).Table des matières
Introduction 1
I Complexité algébrique 9
1 Classes de complexité 11
1.1 Classes booléennes, partie 1 . . . . . . . . . . . . . . . . . . . . . 11
1.2 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Classes partie 2 . . . . . . . . . . . . . . . . . . . . . 19
1.4 Modèle de Valiant . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Largeurs et couvertures de graphes 31
2.1 Largeurs linéaire et arborescente . . . . . . . . . . . . . . . . . . 31
2.2 Largeurs de clique, NLC et MC . . . . . . . . . . . . . . . . . . . 35
2.3 Couvertures de graphe . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Expressivité des couvertures de graphes de largeur arborescente
bornée 45
3.1 Des formules vers les couvertures des graphes de largeur ar-
borescente bornée . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Des couvertures des graphes de largeur arborescente bornée
vers les formules . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 Expressivité des couvertures de graphes de largeur linéaire bornée 59
4.1 Des circuits de largeur bornée vers les couvertures des graphes
de largeur linéaire bornée . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Des couvertures des graphes de largeur linéaire bornée vers les
circuits de largeur bornée . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Relations entre les différents circuits de largeur bornée et les for-
mules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5 Expressivité des couvertures de graphes de largeur de clique
pondérée bornée 71
5.1 Des formules vers les couvertures de graphes de largeur de
clique pondérée bornée . . . . . . . . . . . . . . . . . . . . . . . . 72
iiiiv Remerciements
5.2 Des couvertures de graphes de largeur de clique pondérée
bornée versVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6 Expressivité des couvertures de graphes planaires 83
6.1 Permanent et hamiltonien des graphes planaires . . . . . . . . . 83
6.2 Somme des poids des couplages parfaits des graphes planaires 84
II Complexité algorithmique 91
7 Variantes linéaires et NP-difficiles de partitionnement d’hyper-
graphes 93
7.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.2 Complexité du problème sur des hypergraphes arbitraires . . . 96
7.2.1 Le cas polynomial . . . . . . . . . . . . . . . . . . . . . . 96
7.2.2 Le casNP-complet . . . . . . . . . . . . . . . . . . . . . . 96
7.3 Complexité du problème sur les hypergraphes ayant des hyper-
arêtes disjointes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.3.1 Le casNP-complet . . . . . . . . . . . . . . . . . . . . . . 99
7.3.2 Le cas linéaire : premiers cas simples . . . . . . . . . . . . 100
7.3.3 Le case : structure des solutions . . . . . . . . . . 103
7.3.4 Applications de l’algorithme . . . . . . . . . . . . . . . . 112
7.4 Résultats partiels de complexité en épaisseur 2 . . . . . . . . . . 113
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Conclusion et perspectives 117
A Un peu plus de NP-complétude 121
B Liens entre les largeurs pondérées 127
B.1 Liens entre largeur arborescente et largeur de clique pondérée . 127
B.2 Liens entre largeur linéaire et largeur de clique pondérée . . . . 129
Bibliographie 133
Index 137Introduction
L’ubiquité des graphes ou hypergraphes en algorithmique et en complex-
ité est notoirement connue depuis l’origine de ces problématiques. On peut
citer les nombreuses structures de données ayant recours à des graphes –
et plus souvent à des arbres –, les algorithmes de flots, les nombreux prob-
lèmes d’optimisation sur des graphes dont la variante décisionnelle est NP-
complète (Coloration propre, clique maximum, . . .), la preuve de polynomial-
ité de2 SAT, les matroïdes vus comme hypergraphes héréditaires munis d’un
axiome d’échange, . . .
Cette ubiquité est ambivalente dans la complexité des problèmes qu’elle
engendre et des solutions qu’elle apporte. Ainsi, l’exubérance de structures
nouvelles pouvant apparaître dans les graphes aléatoir