Paramètres structurels, bornes serrées et approximation paramétrée
06/02/2026 à 14h00
M. Emmanouil VASILAKIS présente ses travaux en soutenance le 06/02/2026 à 14h00
À l'adresse suivante : Université Paris Dauphine - PSL Place du Maréchal de Lattre de Tassigny, 75016 Paris Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Paramètres structurels, bornes serrées et approximation paramétrée
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d'Analyse et de Modélisation de Systèmes d'Aide à la Décision
Section CNU
9 - Sciences et technologies de l'information et de la communication
Directeur(s)
Michail LAMPIS
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Michail LAMPIS | Maître de conférences | Université Paris Dauphine - PSL | Directeur de these |
| M. Stefan KRATSCH | Full professor | Humboldt-Universität zu Berlin | Rapporteur |
| M. Bruno ESCOFFIER | Professeur des universités | Sorbonne Université | Rapporteur |
| Mme Cristina BAZGAN | Professeur des universités | Université Paris Dauphine - PSL | Examinateur |
| M. Christophe PAUL | Directeur de recherche | Université de Montpellier | Examinateur |
| M. Pierre ABOULKER | Maître de conférences | École Normale Supérieure - PSL | Examinateur |
Résumé
Cette thèse étudie des problèmes sur les graphes NP-difficiles au travers de
la paramétrisation structurelle et d'une analyse fine.
Pour les problèmes considérés, nous (i) localisons la frontière entre la
tractabilité à paramètres fixes (FPT) et la W[1]-dureté, en proposant des
réductions d'intractabilité améliorées et en concevant de nouveaux
algorithmes FPT ; (ii) faisons correspondre des algorithmes naturels de
programmation dynamique à des bornes inférieures serrées fondées sur SETH
ou pw-SETH ; (iii) établissons des bornes inférieures serrées sous ETH pour
des paramétrisations au-delà de la largeur d'arbre ; et (iv) montrons que
l'approximation permet, dans certains cas, de franchir des barrières du
calcul exact, tandis que dans d'autres elle ne le peut pas.
Pour atteindre ces résultats, nous développons de nouvelles techniques de
réductions de dureté et de conception d'algorithmes, susceptibles d'intérêt
indépendant. En particulier, nous introduisons (i) une nouvelle variante de
textsc{Unary Bin Packing} qui conduit à des résultats de W[1]-dureté
renforcés ; (ii) des techniques pour obtenir des bornes inférieures
améliorées pour des problèmes paramétrés par la profondeur d'arbre et la
couverture de sommets ; et (iii) une construction simple pour
concevoir des schémas d'approximation FPT. Nous mettons à profit ces
techniques pour obtenir un ensemble de nouveaux résultats sur plusieurs
problèmes sur les graphes NP-difficiles bien étudiés.