Cette thèse est consacrée à une étude d'un point de vue général de jeux d'accessibilité dans des systèmes munis de compteurs. Dans ce type de jeux, l'objectif de l'un des deux joueurs est d'atteindre une configuration particulière, qui est composée d'un sommet de l'arène où le jeu se déroule et d'un n-uplet de valeurs pour les compteurs. Ces valeurs de compteurs sont mises à jour, généralement par des additions de vecteurs, lorsqu’un arc est emprunté. Le problème de décision associé à un jeu d’accessibilité est de savoir si le joueur en question a une stratégie gagnante depuis une configuration donnée. Lorsque ce problème est décidable, on s’intéresse à la possibilité de décrire l’ensemble de ces configurations dites gagnantes. Au cours de l’étude, des caractéristiques des jeux d’accessibilités avec des compteurs sont mises en parallèle, en cherchant des similarités, ou au contraire des différences, au niveau de la décidabilité et de la complexité du problème de décision, quand l’une de ces caractéristiques est modifiée. On retiendra en tant que caractéristique majeure le comportement quand un compteur devrait devenir négatif. Nous nous focalisons principalement sur trois sémantiques. Nous considérons également d’autres caractéristiques selon lesquelles il était possible de comparer décidabilité et complexité. Nous nous penchons sur un modèle intitulé « robot games », sur lequel nous obtenons des résultats majeurs : un algorithme de complexité asymptotiquement optimale en dimension un et une preuve d’indécidabilité en dimension trois. / This thesis is devoted to a general study of a reachability games on systems with counters. In this kind of games, the objective of one of two players is to reach a particular configuration, which is a pair composed of a vertex of the game arena and a tuple of values for the counters. The values of the counters are updated, usually by vector additions, when a edge is taken. The decision problem associated with a reachability game is whether a player has a winning strategy for the game from a given configuration, in other words whether the configuration is winning. When the problem of determining the winner from a given configuration is decidable, we wonder whether it is even possible to describe the set of winning configurations. In our study, we look at various features of counter reachability games, finding similarities or, on the contrary, differences with regard to decidability or complexity of the decision problem, when one of the features is modified. The main feature that we consider is what happens when a counter should become negative. We focus primarily on three semantics. We also consider other features that allow to compare decidability and complexity. We introduce a model, called “robot games”, on which we obtain our main results: an algorithm with an optimal complexity for dimension one, and undecidability for dimension three.

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques. / This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

Cette thèse étudie la détection de communautés dans le contexte des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes représentent les relations entre les membres. En particulier, j'étudie quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes. / This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.

Cette thèse aborde deux sujets de recherche dans le cadre du même projet. La première voie de recherche, expliquée en détail au chapitre 3, est une approche de modélisation relative à la dynamique de confiance dans une société en réseau. La seconde voie de recherche, décrite au chapitre 4, est une approche expérimentale visant w étudier les décisions humaines lors de l’échange d’un actif avec une croissance moyenne positive par période dans un environnement de laboratoire contrôlé. Un des liens communs entre ces deux thèmes est l’action collective, qui joue un rôle déterminant dans de nombreux phénomènes, par exemple la dynamique de la panique, les faillites et par conséquent le risque systémique. C’est pourquoi, j’espère que ce travail contribuera à l’étude des phénomènes d’actions collectives, en particulier dans la finance quantitative, où les conclusions spécifiques du modèle de confiance et l’expérience de trading en laboratoire mentionnés ci-dessus pourront être utilisées dans leur état actuel. / This thesis reports on two different research topics belonging to the same project. The first research avenue, which is thoroughly explained in chapter 3, is a modelling approach to the dynamics of trust in a networked society. The second, whose description can be found in chapter 4, is an experimental approach to study human decisions when people trade an asset with a positive average growth per period in a controlled laboratory environment. One of the common links between these two topics is collective action, which is a key player in a number of phenomena, for example in the dynamics of panic, bankruptcies and, consequently, systemic risk. Therefore, the author hopes that this work will contribute to the study of collective action phenomena, especially in the field of quantitative finance, in which it is more likely that the specific findings from the above mentioned trust model and trading experiment can be used in their present form.

Le thème de l’individuation et de la persistance des entités vivantes constitue l’une des problématiques centrales de la philosophie de la biologie. Dans les sciences du vivant, l’organisme représente traditionnellement l’exemple paradigmatique de l’individu biologique. Toutefois, malgré le lien intuitif entre l’organisme et l’individu, la biologie contemporaine a su faire un usage plus large du concept d’individu. Ainsi, la circonscription de ce qui était appréhendé comme appartenant au vivant a été élargie par la reconnaissance de plusieurs types d’individus biologiques, parmi lesquels nous trouvons non seulement les organismes dits « traditionnels », mais également toute une variété d’entités telles que des protistes, des molécules d’ARN, des prions, des virus et des bactéries de toutes sortes. Par ailleurs, cette nouvelle vision de l’individu biologique a été utilisée afin d’illustrer les différents niveaux de l’organisation biologique. En ce sens, la discussion porte principalement sur le niveau – gènes, cellules, organismes, superorganismes, espèces, écosystèmes – où la sélection agit, dans lequel l’organisme, en tant qu’exemple paradigmatique d’individu, peut être considéré comme un simple niveau entre une diversité de niveaux de sélection. Par conséquent, l’extension des limites de l’ontologie biologique a permis, d’une part, d’interroger le concept d’individu en le libérant de la référence à l’organisme, et d’une autre, de relativiser l’importance de l’organisme au sein du discours biologique. Pourtant, nous soutenons que, pour contribuer au développement de la thématique de l’individu biologique, il faut donner voix à un autre discours sur l’individualité, qui émerge des discussions sur l’ontologie des organismes. C’est vers la tradition systémique qu’il convient de tourner le regard, dans le but d’étendre les recherches sur la nature de l’individualité biologique sous l’angle d’une définition renouvelée de l’organisme. Notre démarche suppose d’établir une distinction importante entre deux tendances biologiques à propos du problème de l’individu biologique : l’individu darwinien et l’individu ontogénétique. Dans une approche ontogénétique, un individu correspond à l’entité qui s’autodétermine au cours de son temps de vie individuel. Ainsi, cette position repose sur une conception davantage physiologique, centrée sur l’organisation biologique. / The theme about individuation and persistence of living entities is one of the central issues in the philosophy of biology. In the life sciences, the organism represents traditionally the paradigmatic example of the biological individual. However, despite the intuitive connection between the organism and the individual, contemporary biology has been able to make wider use of the concept of the individual. Thus, the contours of what was apprehended as belonging to the living world has been enlarged by the recognition of several types of biological individuals, among which we find not only so-called "traditional" organisms, but also a variety of entities such as protists, RNA molecules, prions, viruses and bacteria of all kinds. In addition, this new vision of the biological individual has been used to illustrate the different levels of biological organization. In this sense, the discussion focuses on the level - genes, cells, organisms, superorganisms, species, ecosystems - where selection acts, in which the organism can be considered a simple level between a variety of levels of selection. Consequently, the extension of the limits of biological ontology allowed, on the one hand, to question the concept of the individual by releasing it from the reference to the organism, and on the other hand, to relativize the importance of the organism within the biological discourse. However, we argue that, to contribute to the development of biological individuality theme, we must give voice to another discourse on individuality, which emerges from discussions on the ontology of organisms. It is towards the systemic tradition that we must turn our attention, in order to extend research on the nature of biological individuality in the light of a renewed definition of the organism. Thus, we assumes an important distinction between two non-exclusive biological tendencies about the problem of the biological individual: the Darwinian individual and the ontogenetic individual. In an ontogenetic approach, an individual corresponds to the entity that self-determines during its individual life time. Thus, this approach is on a physiological conception, centered on biological organization.

Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.

Plusieurs cadres théoriques ont tenté de rendre compte des processus de synchronisation interpersonnelle. Les théories cognitivistes suggèrent que la synchronisation est réalisée par le biais d’une correction discrète et mutuelle des asynchronies entre les deux partenaires. Les théories dynamiques reposent sur l’hypothèse d’un couplage continu des deux systèmes, conçus comme oscillateurs auto-entretenus. Enfin le modèle du complexity matching repose sur l’hypothèse d’une coordination multi-échelle entre les deux systèmes en interaction. Dans un premier temps, nous développons des tests statistiques permettant de repérer dans les données expérimentales les signatures typiques de ces trois modes de coordination. Nous proposons notamment une signature multifractale, basée sur l’analyse des corrélations entre les spectres multifractals caractérisant les séries produites par les deux systèmes en interaction. Nous développons également une analyse de cross-corrélation fenêtrée, qui permet de dévoiler les processus locaux de synchronisation mis en œuvre. Ces études nous permettent de revisiter un certain nombre de travaux antérieurs. Nous montrons notamment que si la synchronisation de tâches discrètes telles que le tapping repose en effet sur des processus de correction discrète des asynchronies, la synchronisation de tâches continues telles que les oscillations de pendules est essentiellement basée sur les mêmes principes de correction discrète, et non sur un couplage continu des effecteurs. Nos résultats indiquent également que la synchronisation peut révéler des mécanismes hybrides mixant notamment correction des asynchronies et complexity matching. Enfin nous mettons en évidence que la marche synchronisée met en œuvre un effet dominant de complexity matching, d’autant plus prégnant que les deux partenaires sont étroitement couplés (marche bras-dessus-bras-dessous). Nous proposons dans un second temps d’exploiter ce résultat pour tester la possibilité d’une restauration de la complexité chez les personnes âgées. Le vieillissement a en effet été caractérisé comme un processus de perte graduelle de complexité, et cet effet a été notamment documenté dans le domaine de la locomotion. Il a notamment été montré que la perte de complexité corrélait avec la propension à la chute. La théorie du complexity matching suppose que deux systèmes en interaction tendent à aligner leurs niveaux de complexité. Elle suppose également que lorsque deux systèmes de niveaux différents de complexité interagissent, le système le plus complexe tend à attirer le moins complexe, engendrant un accroissement de la complexité chez le second. Nous montrons, dans un protocole au cours duquel des personnes âgées sont invitées à marcher bras-dessus-bras-dessous avec un accompagnant jeune, que la synchronisation entre les deux partenaires est réalisée au travers d’un effet d’appariement des complexités, et que l’entrainement prolongé en marche synchronisée permet une restauration de la complexité de la locomotion chez les personnes âgées. Cet effet perdure lors d’un post-test réalisé deux semaines après la fin de l’entraînement. Ce résultat, outre le fait qu’il conforte un des aspects essentiels de la théorie du complexity matching, ouvre de nouvelles voies de recherche pour la conception de stratégies de réhabilitation et de prévention de la chute. / Several theoretical frameworks have attempted to account for interpersonal synchronization processes. Cognitive theories suggest that synchronization is achieved through discrete and mutual corrections of asynchronies between the two partners. The dynamic theories are based on the assumption of a continuous coupling between the two systems, conceived as self-sustained oscillators. Finally, the complexity matching model is based on the assumption of a multi-scale coordination between the two interacting systems. As a first step, we develop statistical tests in order to identify, in experimental data, the typical signatures of these three modes of coordination. In particular, we propose a multifractal signature, based on the analysis of correlations between the multifractal spectra characterizing the series produced by the two interacting systems. We also develop a windowed cross-correlation analysis, which aims at revealing the nature of the local synchronization processes. These studies allow us to revisit a number of previous works. We show that if the synchronization of discrete tasks such as tapping relies on discrete correction processes of asynchronies, the synchronization of continuous tasks such as pendulum oscillations is essentially based on the same principles of discrete correction, and not on a continuous coupling of effectors. Our results also indicate that synchronization could be sustained by hybrid mechanisms mixing notably asynchronies correction and complexity matching. Finally we highlight that synchronized walking is based on a dominant effect of complexity matching, especially when partners are closely coupled (arm-in-arm walking). We propose in a second step to exploit this result to test the possibility of a restoration of complexity in the elderly. Aging has indeed been characterized as a process of gradual loss of complexity, and this effect has been particularly documented in the field of locomotion. In particular, it has been shown that the loss of complexity correlates in older people with the propensity to fall. Complex matching theory assumes that two interacting systems tend to align their complexity levels. It also assumes that when two systems of different levels of complexity interact, the more complex system tends to attract the less complex, causing an increase in complexity in the second. We show, in a protocol in which older people are invited to walk arm-in-arm with a younger companion, that synchronization between the two partners is achieved through a complexity matching effect, and that prolonged training in such synchronized walking allows a restoration of the complexity of locomotion in the elderly. This effect persists during a post-test conducted two weeks after the end of the training sessions. This result, in addition to reinforcing one of the essential aspects of the theory of complexity matching, opens new avenues of research for the design of rehabilitation and fall prevention strategies.

Il a été observé que l'exécution des heuristiques de recherche aléatoire dépend d'un ou de plusieurs paramètres. Un certain nombre de résultats montrent un avantage des paramètres dynamiques, c'est-à-dire que les paramètres de l'algorithme sont modifiés au cours de son exécution. Dans ce travail, nous montrons que la complexité de la boîte noire sans biais de la classe de fonction de référence OneMax est $n ln(n) - cn pm o(n)$ pour une constante $c$ comprise entre $0.2539$ et $0.2665$. L'exécution peut être réalisé avec un algorithme simple de type-(1+1) utilisant une puissance de mutation fitness dépendant. Une fois traduite dans le cas du budget fixe, notre algorithme trouve des solutions plus proches de l'optimum de 13% que celles des meilleurs algorithmes connus.Basé sur la puissance de mutation optimale analysée pour OneMaX, nous montrons qu'un choix auto-ajusté du nombre de bits à retourner atteint le même temps d'exécution (excepté $o(n)$ termes inférieurs) et le même (asymptotique) 13% amélioration de la fitness-distance par rapport au RLS. Le mécanisme d'ajustement doit apprendre de manière adaptative la puissance de mutation actuellement optimale des itérations précédentes. Cela vise à la fois à exploiter le fait que des problèmes généralement différents peuvent nécessiter des puissances de mutation différentes et que, pour un problème fixe, différentes puissances peuvent devenir optimales à différentes étapes du processus d'optimisation.Nous étendons ensuite notre stratégie d'auto-ajustement aux algorithmes évolutifs basés sur la population dans des espaces discrets de recherche. Grosso modo, il consiste à créer la moitié de la descendance avec un taux de mutation qui est deux fois plus élevé que le taux de mutation actuel et l'autre moitié avec la moitié du taux actuel. Le taux de mutation est ensuite mis à jour au taux utilisé dans cette sous-population qui contient la meilleure descendance. Nous analysons comment l'algorithme d'évolution $(1+lambda)$ avec ce taux de mutation auto-ajustable optimise la fonction de test OneMax. Nous montrons que cette version dynamique de $(1+lambda)$~EA trouve l'optimum dans un temps d'optimisation attendu (nombre d'évaluations de la fitness) de $O(nlambda/loglambda+nlog n)$. Le temps est asymptotiquement plus petit que le temps d'optimisation de l'EA classique $(1+lambda)$. Des travaux antérieurs montrent que cette performance est la meilleure possible parmi tous les algorithmes de boîtes noires sans biais unaire basés sur des mutations $lambda$-parallèles.Nous proposons et analysons également une version auto-réglage de l'algorithme évolutionnaire $(1,lambda)$ dans lequel le taux de mutation actuel fait partie de l'individu et donc également sujet à mutation. Une analyse d'exécution rigoureuse sur la fonction de référence OneMax révèle qu'un simple schéma de mutation pour le taux conduit à un temps d'optimisation attendu du meilleur $O(nlambda/loglambda+nlog n)$. Notre résultat montre que l'auto-réglage dans le calcul évolutif peut trouver automatiquement des paramètres optimaux complexes. En même temps, cela prouve qu'un schéma d'auto-ajustement relativement compliqué pour le taux de mutation peut être remplacé par notre schéma endogène simple. / It has been observed that the runtime of randomized search heuristics depend on one or more parameters. A number of results show an advantage of dynamic parameter settings, that is, the parameters of the algorithm are changed during its execution. In this work, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n ln(n) - cn pm o(n)$ for a constant $c$ which is between $0.2539$ and $0.2665$. This runtime can be achieved with a simple (1+1)-type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13% closer to the optimum than those of the best previously known algorithms.Based on the analyzed optimal mutation strength for OneMax, we show that a self-adjusting choice of the number of bits to be flipped attains the same runtime (apart from $o(n)$ lower-order terms) and the same (asymptotic) 13% fitness-distance improvement over RLS. The adjusting mechanism is to adaptively learn the currently optimal mutation strength from previous iterations. This aims both at exploiting that generally different problems may need different mutation strengths and that for a fixed problem different strengths may become optimal in different stages of the optimization process.We then extend our self-adjusting strategy to population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+lambda)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+lambda)$~EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(nlambda/loglambda+nlog n)$. This time is asymptotically smaller than the optimization time of the classic $(1+lambda)$ EA. Previous work shows that this performance is best-possible among all $lambda$-parallel mutation-based unbiased black-box algorithms.We also propose and analyze a self-adaptive version of the $(1,lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time of the best possible $O(nlambda/loglambda+nlog n)$. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate can be replaced by our simple endogenous scheme.

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque. / We introduce a new communication complexity model in which we want to determine how much time of communication is needed by two players in order to execute arbitrary tasks on a channel with delay d. We establish a few basic lower and upper bounds and compare this new model to existing models such as the classical and quantum two-party models of communication. We show that the standard communication complexity of a function, modulo a factor of d/ lg d, constitutes an upper bound to its communication complexity on a delayed channel. We introduce a few examples on which a clever strategy depending on the delay procures a significant advantage over the naïve implementation of an optimal communication protocol. We then show that a delayed channel can be used to implement a cryptographic bit swap, but is insufficient on its own to implement an oblivious transfer scheme.

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^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où 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 Sigma et Rho, 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é.