Abstract (FR)

De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah.