Faculté des sciences de base SB, Section de mathématiques, Institut de mathématiques IMA (Chaire de recherche opérationnelle SE ROSE)

Generalized vertex coloring problems using split graphs

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3629.

Add to personal list

Export as

Summary
Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. For mathematicians, it is interesting for an additional reason: it is extremely hard to solve it in an efficient way. In this thesis, we introduce several problems generalizing the usual vertex coloring problem, and hence, extending its application domain. We say that a graph is (p, k)-colorable if its vertex set can be partitioned into p cliques and k stable sets. Then, for a given p (respectively k), one may ask the following questions: how to choose p cliques (respectively k stable sets) to be removed from the graph such that the number of stable sets (respectively cliques) partitioning the remaining vertices is minimized? These are called (p, k)-coloring problems. We also introduce Min Split-coloring which is, given a graph G, the problem of minimizing k such that G is (k, k)-colorable. Along the saine line, given a graph G, the objective of the problem Min Cocoloring is to minimize p + k such that G is (p, k)-colorable. All these problems, called together generalized coloring problems, are obviously at least as difficult as Min Coloring. The purpose of this dissertation is to study generalized coloring problems in nome restricted classes of graphs in order to bring a new insight on the relative difficulties of these problems. To this end, we detect in a more precise way the limits between NP-hard and polynomially solvable problems. Chapter 1 introduces generalized coloring problems by emphasizing nome preliminary results which will guide the questions to handle in the following chapters. Chapter 2 exposes the first clans of graphs, namely cacti, where Min Split-coloring is shown to be polynomially solvable. We also observe that generalized coloring problems can be polynomially solved in triangulated graphs. The main result of Chapter 3 is a new characterization of cographs: it is equivalent to say that G is a cograph, and to state that, for every subgraph G' ⊆ G, G' is (p, k)-colorable if and only if G' [V \ K] is (p – 1, k)-colorable, where K induces a maximum clique of G'. This result implies simple combinatorial algorithme to solve all generalized coloring problems; the one for Min Cocoloring improves the best time complexity known so far. In Chapter 4, we handle the recognition of polar graphs which can be seen as a particular (p, k)-coloring, where p cliques are independent (i.e., not linked at all) and k stable sets form a complete k-partite graph. It is known that the recognition of polar graphs is NP-complete. Here, we determine the first clans of graphs, namely cographs, where the polar graphs can be recognized in polynomial time, more precisely in time O(n log n). We also give a characterization by forbidden subgraphs. In the came manner, we characterize monopolar cographs, i.e., cographs admitting a polar partition with at most one clique or at most one stable set. Chapter 5 is devoted to generalized coloring problems in line graphs. Here, we detect the first classes of graphs, namely line graphs of trees, line graphs of bipartite graphs and line graphs of line-perfect graphs, where generalized coloring problems diverge in terms of NP-hardness. In Chapter 6 we study the approximability of generalized coloring problems in line graphs, in comparability graphs and in general graphs. We derive approximation algorithms with a performance guarantee using both the standard approximation ratio and the differential approximation ratio. We show that both Min Split-coloring and Min Cocoloring are at least as hard as Min Coloring to approximate from the standard approximation ratio point of view, whereas, they admit a polynomial time differential approximation scheme and Min Coloring only a constant differential approximation ratio. We also show that Min Cocoloring reduces to Min Split-coloring in all classes of graphs closed under addition of disjoint cliques and under join of a complete k-partite graph. In Chapter 7, we handle two different applications of Min Split-coloring in permutation graphs. They give birth to a new problem, called Min Threshold-coloring, that we study in the came spirit as the other generalized coloring problems. In the last chapter, we present several open questions arising from this thesis.
Résumé
La théorie des graphes a eu un essor remarquable dans la communauté scientifique pendant les dernières décennies. Le problème de coloration de sommets (Min Coloration) mérite une attention particulière puisqu'il a de nombreuses applications. Il intéresse les mathématiciens pour une raison de plus : il est extrêmement difficile à résoudre de manière efficace. Dans cette thèse, nous introduisons plusieurs problèmes qui généralisent le problème usuel de coloration de sommets, et par conséquent, étendent son domaine d'application. Un graphe est (p, k)-colorable si son ensemble de sommets peut être partitionné en p cliques et k ensembles stables. Pour un p (respectivement k) donné, nous considérons les problèmes suivants : comment choisir les p cliques (respectivement k ensembles stables) à enlever du graphe de manière à minimiser le nombre d'ensembles stables (respectivement cliques) qui partitionnent les sommets restants? Ces problèmes sont appelés les problèmes de (p, k)- coloration. Nous introduisons aussi le problème Min Coloration Scindée qui consiste, pour un graphe G donné, à minimiser k tel que G soit (k, k)-colorable. Par ailleurs, pour un graphe G donné, l'objectif du problème Min Cocoloration est de minimiser la somme p+k tel que G soit (p, k)-colorable. Tous ces problèmes qui se nomment problèmes de coloration généralisée, sont évidemment au moins aussi difficiles que Min Coloration. Le but de cette thèse est d'étudier les problèmes de coloration généralisée dans des classes de graphes restreintes afin de pouvoir mettre en évidence les difficultés relatives de ces problèmes. Pour y parvenir, on détermine de façon précise les limites entre les problèmes NP-difficiles et ceux qui sont solubles polynomialement. Le premier chapitre présente les problèmes de coloration généralisée en mettant en évidence certains résultats préliminaires qui vont guider les questions considérées dans les chapitres suivants. Le second chapitre présente la première classe de graphes, à savoir les cactus, où on peut résoudre Min Coloration Scindée en temps polynomial. De plus, nous observons que les problèmes de coloration généralisée peuvent être résolus en temps polynomial dans les graphes triangulés. Le résultat principal du troisième chapitre est une nouvelle caractérisation des cographes: il est équivalent de dire que G est un cographe et d'affirmer que, pour tout sous-graphe G' ⊆ G, G' est (p, k)-colorable si et seulement si G' [V \ K] est (p – 1, k)-colorable, où K est une clique maximum de G'. Ce résultat implique des algorithmes combinatoires simples pour résoudre tous les problèmes de coloration généralisée ; celui proposé pour Min Cocoloration améliore la meilleure complexité de temps connue jusqu'à présent. Dans le quatrième chapitre, nous considérons la reconnaissance des graphes polaires que l'on peut également voir comme une (p, k)-coloration particulière, où les p cliques forment une union disjointe de cliques (i.e., sans aucune arête entre elles) et les k ensembles stables forment un graphe k-parti complet. Il a déjà été démontré que la reconnaissance des graphes polaires est NP-complète. Nous déterminons la première classe de graphes, à savoir les cographes, où les graphes polaires peuvent être reconnus en temps polynomial, plus précisément en temps O(n log n). Nous caractérisons également les cographes polaires par des sous-graphes interdits. De la même manière, nous caractérisons les cographes monopolaires, i.e., les cographes qui admettent une partition polaire avec au plus une clique ou au plus un ensemble stable. Le cinquième chapitre est consacré aux problèmes de coloration généralisée dans les graphes aux arêtes. Nous déterminons les premières classes de graphes où les problèmes de coloration généralisée divergent en termes de NP-complétude. Ces classes sont les graphes aux arêtes des arbres, les graphes aux arêtes des graphes bipartis et les graphes aux arêtes des graphes arête-parfaits. Dans le sixième chapitre, nous étudions l'approximabilité des problèmes de coloration généralisée dans les graphes aux arêtes, les graphes de comparabilité et les graphes généraux. Nous proposons des algorithmes d'approximation avec une garantie de performance en utilisant les rapports d'approximation classique et différentiel. Nous montrons que Min Coloration Scindée et Min Cocoloration sont tous les deux au moins aussi difficiles à approcher que Min Coloration du point de vue du rapport d'approximation standard. Par contre, ils admettent un schéma d'approximation différentiel en temps polynomial et Min Coloration admet seulement un rapport d'approximation différentiel constant. Nous montrons également que Min Cocoloration se réduit à Min Coloration Scindée dans toutes les classes de graphes fermées par les opérations d'adjonction de cliques disjointes et de liaison complète avec un graphe k-parti complet. Dans le septième chapitre, nous considérons deux applications de Min Coloration Scindée dans les graphes de permutations. Elles donnent naissance à un nouveau problème, appelé Min Coloration avec Seuil, que nous abordons avec la même méthodologie que celle utilisée pour les autres problèmes de coloration généralisée. Dans le dernier chapitre, nous présentons plusieurs questions ouvertes qui surgissent de cette thèse.