京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20516号 / 情博第644号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 永持 仁, 教授 太田 快人, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles. / Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs.

Dans cette thèse, nous avons présenté trois méthodes différentes pour l’énumération de sousréseauxparticuliers d’un réseau métabolique: les histoires métaboliques, les ensembles minimaux deprécurseurs et les organisations chimiques. Pour chacune de ces trois méthodes, nous avons présentédes résultats théoriques, et pour les deux premières, nous avons en outre fourni une illustration surcomment les appliquer afin d’étudier le comportement métabolique des organismes vivants. Les histoiresmétaboliques sont définies comme des graphes acycliques dirigés maximaux dont les ensemblesde sources et de cibles sont limités à un sous-ensemble des noeuds. La motivation initiale de cette définitionétait d’analyser des données expérimentales de métabolomique, mais la méthode a égalementété explorée dans un contexte différent. Les ensembles de précurseurs métaboliques sont des ensemblesminimaux de nutriments qui permettent de produire des métabolites d’intérêt. Nous présentons troisméthodes différentes pour l’énumération de tels ensembles minimaux de précurseurs, et nous illustronsleur application dans une étude des échanges métaboliques dans un système symbiotique. Les organisationschimiques sont des ensembles de métabolites qui à la fois sont fermés et s’auto-maintiennent,ce qui reflète des caractéristiques de stabilité dans le sens où aucun nouveau métabolite ne peut êtreproduit et qu’aucun des métabolites déjà présents dans le système ne peut disparaître. / In this thesis, we presented three different methods for enumerating special subnetworks containedin a metabolic network: metabolic stories, minimal precursor sets and chemical organisations. Foreach of the three methods, we gave theoretical results, and for the two first ones, we further providedan illustration on how to apply them in order to study the metabolic behaviour of living organisms.Metabolic stories are defined as maximal directed acyclic graphs whose sets of sources and targets arerestricted to a subset of the nodes. The initial motivation of this definition was to analyse metabolomicsexperimental data, but the method was also explored in a different context. Metabolic precursor setsare minimal sets of nutrients that are able to produce metabolites of interest. We present threedifferent methods for enumerating minimal precursor sets and we illustrate the application in a studyof the metabolic exchanges in a symbiotic system. Chemical organisations are sets of metabolites thatare simultaneously closed and self-maintaining, which captures some stability feature in the

In this thesis, we presented three different methods for enumerating special subnetworks containedin a metabolic network: metabolic stories, minimal precursor sets and chemical organisations. Foreach of the three methods, we gave theoretical results, and for the two first ones, we further providedan illustration on how to apply them in order to study the metabolic behaviour of living organisms.Metabolic stories are defined as maximal directed acyclic graphs whose sets of sources and targets arerestricted to a subset of the nodes. The initial motivation of this definition was to analyse metabolomicsexperimental data, but the method was also explored in a different context. Metabolic precursor setsare minimal sets of nutrients that are able to produce metabolites of interest. We present threedifferent methods for enumerating minimal precursor sets and we illustrate the application in a studyof the metabolic exchanges in a symbiotic system. Chemical organisations are sets of metabolites thatare simultaneously closed and self-maintaining, which captures some stability feature in the

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