Les décompositions de graphes, lorsqu’elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d’obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d’obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l’étude du problème ENSEMBLE [σ, ρ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d’entiers σ et ρ. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l’est pas toujours, et que pour certains cas d’ensembles σ et ρ, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d’un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k ≥ 4 fixé, tandis qu’il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. / Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions’ construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [σ, ρ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers σ and ρ. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k ≥ 4, while it can be solved in polynomial time on trees for any k.

L’affectation de fr´equences (AFP) consiste `a attribuer des fr´equences radio aux liens de communications d’un r´eseauen respectant un spectre de fr´equences donn´e et des contraintes d’interf´erence ´electromagn´etique sur les liens. Vu lalimitation des ressources spectrales pour chaque application, les ressources en fr´equences sont souvent insuffisantespour d´eployer un r´eseau sans interf´erence. Dans ce cas, le r´eseau est surcontraint et le probl`eme est irr´ealisable.R´esoudre le probl`eme consiste alors `a identifier les zones surcontraintes pour en revoir la conception.Le travail que nous pr´esentons concerne la recherche d’une de ces zones surcontraintes avec une approche algo-rithmique bas´ee sur la mod´elisation du probl`eme par un CSP. Le probl`eme de l’affectation de fr´equences doit doncˆetre mod´elis´e comme un probl`eme de satisfaction de contraintes (CSP) qui est repr´esent´e par un tripl´e : un ensemblede variables (les liens radio), un ensemble de contraintes (les interf´erences ´electromagn´etiques), et un ensemble dedomaines (les fr´equences admises).Sous forme de CSP, une zone perturb´ee peut ˆetre consid´er´ee comme un sous-ensemble irr´ealisable irr´eductible duprobl`eme (IIS pour Irreductible Infeasible Subset). Un IIS est un sous probl`eme de taille minimale qui est irr´ealisable,c’est-`a-dire que tous les sous-ensembles d’un IIS sont r´ealisables. L’identification d’un IIS dans un CSP se rapporte `a deux r´esultats g´en´eraux int´eressants. Premi`erement, en localisant un IIS on peut plus facilement prouver l’irr´ealisabilit´ed’un probl`eme donn´e car l’irr´ealisabilit´e d’un IIS, qui est suppos´e ˆetre petit par rapport au probl`eme complet, est plusrapidement calculable que sur le probl`eme entier. Deuxi`emement, on peut localiser la raison de l’irr´ealisabilit´e; dansce cas, sur un probl`eme r´eel, le d´ecideur peut proposer des solutions pour relˆacher des contraintes de l’IIS, et peut-ˆetre aboutir `a une solution r´ealisable pour son probl`eme. La recherche d’IIS consiste donc `a r´esoudre un probl`emefondamental qui fait partie des outils de prise de d´ecision.Ce travail propose des algorithmes pour identifier un IIS dans un CSP incoh´erent. Ces algorithmes ont ´et´e test´essur des instances connues du probl`eme de l’affectation des fr´equences et du probl`eme de k-coloration de graphe. Lesr´esultats ont montr´es d’une grande am´elioration sur des instances du probl`eme de l’affectation des fr´equences parrapport aux m´ethodes connues. / The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.