Academic literature on the topic 'Graphes paramétrés'

International audience We construct and study an embedded weighted balanced graph in $\mathbb{R}^{n+1}$ parametrized by a strictly increasing sequence of $n$ coprime numbers $\{ i_1, \ldots, i_n\}$, called the $\textit{tropical secant surface graph}$. We identify it with the tropicalization of a surface in $\mathbb{C}^{n+1}$ parametrized by binomials. Using this graph, we construct the tropicalization of the first secant variety of a monomial projective curve with exponent vector $(0, i_1, \ldots, i_n)$, which can be described by a balanced graph called the $\textit{tropical secant graph}$. The combinatorics involved in computing the degree of this classical secant variety is non-trivial. One earlier approach to this is due to K. Ranestad. Using techniques from tropical geometry, we give algorithms to effectively compute this degree (as well as its multidegree) and the Newton polytope of the first secant variety of any given monomial curve in $\mathbb{P}^4$. On construit et on étude un graphe plongé dans $\mathbb{R}^{n+1}$ paramétrisé par une suite strictement croissante de $n$ nombres entiers $\{ i_1, \ldots, i_n\}$, premiers entre eux. Ce graphe s'appelle $\textit{graphe tropical surface sécante}$. On montre que ce graphe est la tropicalisation d'une surface dans $\mathbb{C}^{n+1}$ paramétrisé par des binômes. On utilise ce graphe pour construire la tropicalisation de la première sécante d'une courbe monomiale ayant comme vecteur d'exponents $(0, i_1, \ldots, i_n)$. On représente cette variété tropicale pour un graphe balancé (le $\textit{graphe tropical sécante}$). La combinatoire qu'on utilise pour le calcul du degré de ces variétés sécantes classiques n'est pas triviale, et a été developpée par K. Ranestad. En utilisant des techniques de la géométrie tropicale, on donne des algorithmes qui calculent le degré (même le multidegré) et le polytope de Newton de la première sécante d'une courbe monomiale de $\mathbb{P}^4$.

International audience We study polytopes that are convex hulls of vectors of subgraph densities. Many graph theoretical questions can be expressed in terms of these polytopes, and statisticians use them to understand exponential random graph models. Relations among their Ehrhart polynomials are described, their duals are applied to certify that polynomials are non-negative, and we find some of their faces. For the general picture we inscribe cyclic polytopes in them and calculate volumes. From the volume calculations we conjecture that a variation of the Selberg integral indexed by Schur polynomials has a combinatorial formula. We inscribe polynomially parametrized sets, called curvy zonotopes, in the polytopes and show that they approximate the polytopes arbitrarily close. Nous étudions les polytopes qui sont les enveloppes convexes des vecteurs des densités de sous-graphe. Beaucop de questions théoriques de graphe peuvent être exprimées en termes de ces polytopes, et les statisticiens les utilisent pour comprendre les modèles de graphes aléatoires exponentielles Des relations parmi leurs polynômes d'Ehrhart sont décrites leurs duals sont appliqués pour certifier que les polynômes sont non négatifs, et nous trouvons certaines de leurs faces. Pour la description générale nous inscrivons les polytopes cycliques dans eux et calculons les volumes. D'après les calculs de volume, nous conjecturons qu'une variation de l'intégrale de Selberg indexés par des polynômes de Schur a une formule combinatoire. Nous inscrivons polynomialement les ensembles paramétrisés appelés ``curvy zonotopes'' dans les polytopes et montrons qu'ils sont arbitrairement proches de polytopes.

International audience An associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon and whose edges correspond to flips between them. J.-L. Loday gave a particularly elegant realization of the associahedron, which was then generalized in two directions: on the one hand to obtain realizations of graph associahedra, and on the other hand to obtain multiple realizations of the associahedron parametrized by a sequence of signs. The goal of this paper is to unify and extend these two constructions to signed tree associahedra. Un associaèdre est un polytope dont les sommets correspondent aux triangulations d’un polygone convexe et dont les arêtes correspondent aux flips entre ces triangulations. J.-L. Loday a donné une construction particulièrement élégante de l’associaèdre qui a été généralisée dans deux directions : d’une part pour obtenir des réalisations des associaèdres de graphes, et d’autre part pour obtenir de multiples réalisations de l’associaèdre paramétrées par une suite de signes. L’objectif de ce travail est d’unifier et d’étendre ces constructions aux associaèdres d’arbres signés.

Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courtschemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multidimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergiedoit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueurs
We are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players

My thesis focusses on two applications of network flow problems. We emphasize on networks modelling energy or fluid distribution and telecommunication services. We study two differents aspects:The first aspect consists of the sensitivity analysis of flows in distribution networks. That is the analysis of the effects of one or more capacity variations on the all pairs maximum flow values. Moreover, we evaluate the importance of an edge in the network. Our contributions begin with a correction of the unique method in the literature that dealed with the case of a single capacity variation. We then propose simple and efficient algorithms to solve the same case, before proposing a generalization to the case of more than one capacity variation. Our algorithms and methods are based on Gomory-Hu cut trees. Given an undirected network in which capacities lambda_1, \lambda_2, \lambda_3, \ldots \lambda_k are varying. We show that ^k Gomory-Hu cut tree computations are sufficient in order to determine the all pairs maximum flow values. As far as link importance analysis is concerned, we show that two Gomory-Hu cut tree computations are sufficient to determine the set of all vertex pairs for which any maximum flow saturates the studied link. The second aspect concerns resource allocation in a telecommunicationnetwork with an objective of demands satisfaction. To do so, we study this problem using pricing in order to handle network congestion while taking into account users behaviour and the operator's profit maximization objective. We use a bi-level programming approach to solve the problem. With an Augmented Lagrangian method, we solve the resource allocation problem by associating the Lagrangian multipliers to the network link prices. We then use the Karush-Kuhn-Tucker optimality conditions to verify about the multipliers (prices) unicity. In case the multipliers are not unique, we show that a second optimization problem over the multipliers (prices) can be solved in order to improve the network revenu
La thèse se focalise sur des applications des problèmes de flots dans des réseaux modélisant, d'une part des réseaux de distribution de fluide ou d'énergie et d'autre part des réseaux de télécommunication. Nous nous sommes intéressés à deux aspects :Le premier aspect consiste en une analyse de sensibilité des flots sur les réseaux de distribution, c'est à dire, l'étude de l'impact de la variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble des valeurs de flot maximum entre toutes les paires de sommets du réseau. En outre, nous nous sommes intéressés à la rentabilité d'une arête donnée dans un réseau. Nous avons d'abord apporté des corrections à l'unique méthode qui existait dans le cas d'une capacité d'arête qui varie et nous avons proposé des algorithmes simples et efficaces pour résoudre le cas de plusieurs capacités qui varient. Nos méthodes sont basées sur les arbres de coupes de Gomory et Hu. 'Etant donné un réseau non orienté ayant capacités qui peuvent varier avec des paramètres lambda_1,\lambda_2, \lambda_3, \ldots \lambda_k, nous avons montré que 2^k calculs d'un arbre de coupes de Gomory et Hu étaient suffisants pour déterminer les valeurs de flot maximum entre toutes les paires de sommets dans le réseau. En ce qui concerne le problème de la rentabilité d'un lien, nous avons montré que juste 2 calculs d'un arbre de coupes de Gomory et Hu suffisaient pour déterminer l'ensemble des paires de sommets pour lesquelles tout flot maximum sature le lien cible. Le second aspect concerne l'allocation de ressources dans un réseau de télécommunication pour la satisfaction de requêtes d'utilisateurs. Pour ce faire, nous avons étudié ce problème par le biais de la tarification pour gérer la congestion tout en tenant compte du comportement des utilisateurs et de la volonté de profit del'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre le problème. Avec la méthode du Lagragien augmenté, nous résolvons le problème d'allocation de ressources en associant les multiplicateurs de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les ultiplicateurs (prix) sont uniques ou pas. Au cas de non unicité nous montrons comment on peut résoudre un deuxième problème d'optimisation sur ces multiplicateurs (prix) afin d'améliorer le revenu sur le réseau

Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes
This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille k dans un graphe à n sommets peut être décidée en temps f(k) ∗ poly(n). Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en k. Nous donnons un algorithme en temps O∗(3.72k) pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que 2n). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les s−t numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées.

Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir
In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer

Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qui consiste à rechercher des motifs dits fonctionnels dans ce type de graphes. La modélisation de systèmes biologiques sous la forme de graphes peut également être appliquée em spectrométrie de masse. Ainsi, on introduit le problème MAXIMUM COLORFUL ARBORESCENCE (MCA) dans le but de déterminer de novo la formule moléculaire de métabolites inconnus. Dans la deuxième partie de ce manuscrit, on réalise une étude algorithmique du problème MCA. Alors que MCA est algorithmiquement difficile à résoudre même dans des classes de graphes très contraintes, notre modélisation nous permet notamment d'obtenir de nouveaux algorithmes d'approximation dans ces mêmes classes, ainsi que de déterminer une nouvelle classe de graphes dans laquelle MCA se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce problème, que l'on compare ensuite à ceux de la littérature sur des instances issues de données biologiques
Ln order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux
The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms

Dans cette thèse, nous étudions la complexité algorithmique de problèmes d'optimisation impliquant un processus de diffusion dans un graphe. Plus précisément, nous nous intéressons tout d'abord au problème de sélection d'un ensemble cible. Ce problème consiste à trouver le plus petit ensemble de sommets d'un graphe à "activer" au départ tel que tous les autres sommets soient activés après un nombre fini d'étapes de propagation. Si nous modifions ce processus en permettant de "protéger" un sommet à chaque étape, nous obtenons le problème du pompier dont le but est de minimiser le nombre total de sommets activés en protégeant certains sommets. Dans ce travail, nous introduisons et étudions une version généralisée de ce problème dans laquelle plus d'un sommet peut être protégé à chaque étape. Nous proposons plusieurs résultats de complexité pour ces problèmes à la fois du point de vue de l'approximation mais également de la complexité paramétrée selon des paramètres standards ainsi que des paramètres liés à la structure du graphe.

Dans cette thèse, nous étudions diverses largeurs de graphes autour de la largeur arborescente ainsi que de la largeur de clique. Nous commençons avec une étude comparative entre la largeur arborescente d’un graphe et la largeur de clique du graphe d’incidence associé, de laquelle nous extrayons des résultats algorithmiques encourageants. Puis nous présentons quelques propriétés structurelles liées à la largeur arborescente spéciale, largeur relativement récente qui est à mi-chemin entre les deux largeurs précédentes. Enfin nous nous intéressons à une notion plus générale connue sous le nom de fonction de partition sous-modulaire qui englobe, entre autres, les largeurs arborescentes « classique » et spéciale, la largeur de chemin ainsi que la largeur linéaire et les largeurs de branches de coupe et de découpe. Nous présentons alors un algorithme linéaire à paramètre fixé pour le calcul de ces différentes largeurs, lequel généralise un certain nombre de résultats propres à chacune de ces largeurs
In this thesis, we study some width parameters on graphs, beyond tree-width and clique-width. Our first investigation is a comparative study between the tree-width of a graph and the clique-width of the associated incidence graph, from which we extract some strong algorithmic results. Then we present a few structural properties over a recently defined width called special tree-width and which takes its definition through both tree-width and clique-width. Finally, we end our journey with a more general notion named sub-modular partition fonction and which encompass both “classic” and special tree-widths, path-width, branch-width, linear-width, cut-width and carvingwidth among others. So, we introduce a fixed parameter tractable algorithm computing those widths parameters and thus we generalize a number of results specific to each of them

Dans cette thèse, nous nous intéressons à la modélisation pour la commande des systèmes physiques à topologie variable. La modélisation du système physique non commandé, est effectuée par une formulation qui conserve explicitement la représentation de l’interconnexion et l’énergie, ce qui permettra l’étude des systèmes non-réguliers par une approche modulaire basée sur le concept de l’énergie. Le principal objectif est alors de représenter de manière structurée toutes les configurations du système, en terme de comportement physiquement possible. Les résultats présentés dans ce mémoire ont pour support un formalisme réseau dynamique pour lequel la théorie des graphes fournit plusieurs représentations mathématiques. Celles-ci permettent la formulation des structures d’interconnexion du système sous forme d’une famille paramétrée de Dirac. Une formulation Hamiltonienne à ports est donc établie à partir de cette expression pour les systèmes physiques à topologie variable incluant des sources d’énergie, des éléments en excès ou des éléments dissipatifs. Cette méthode de modélisation permet d’obtenir un modèle des dynamiques du système mais aussi de ces interconnexions. La représentation sous forme de graphes dynamiques facilite l’analyse des configurations admissibles et des configurations contraintes du système