Résumé de séminaire

Résumé :

De nombreux problèmes pratiques (affectation de fréquences, conception d'emplois du temps ...) peuvent être modélisés par des problèmes de coloration de graphes. Malheureusement, pour les graphes en général, le problème de la coloration des sommets est considéré comme difficile, il est NP-complet [garjoh79].
Au début des années 1960, Berge a introduit la classe des graphes parfaits [ramree01] qui est apparue par la suite comme étant une classe de graphes assez générale pour laquelle plusieurs problèmes classiques d'optimisation pouvaient être résolus efficacement. Grötschel, Lovàsz et Schrijver [grolov84] ont montré en 1984 qu'il était possible de colorier optimalement les sommets d'un graphe parfait en temps polynomial. Mais leur algorithme, basé sur l'algorithme de l'ellipsoïde de Khachiyan, n'est pas réellement efficace d'un point de vue pratique. Cependant, l'existence de cet algorithme est une bonne motivation pour chercher des algorithmes polynomiaux efficaces pour colorier les graphes parfaits ou des sous-classes de graphes parfaits.

Nous nous sommes intéressés particulièrement à la classe de graphes dont tous les cycles impairs de longueurs au moins cinq ont au moins deux cordes. Meyniel [mey84] a montré qu'ils étaient parfaits, nous les appelons depuis les graphes de Meyniel. Les graphes bipartis, les graphes triangulés, les graphes de parité et les graphes i-triangulés sont des exemples de graphes de Meyniel.

Hoàng [hoa87] a donné un algorithme de coloration de graphes de Meyniel, de complexité O(n8). Cet algorithme utilise la décomposition appelée amalgame de Burlet et Fonlupt [burfon84]. La notion de paire d'amis [eve01] a permis à Hertz [her90] de trouver un algorithme de coloration des graphes de Meyniel en temps O(nm). A chaque étape, l'algorithme de Hertz trouve une paire d'amis dans le graphe et la contracte. Ensuite, Roussel et Rusu [rourus01] ont défini l'algorithme de coloration LexColor (pour Lexicographic Color). L'algorithme de Roussel et Rusu permet de colorier les graphes de Meyniel en temps O(n2) sans utiliser la contraction de paire d'amis. L'algorithme « simule » une telle contraction. Son optimalité découle de l'optimalité de l'algorithme de Hertz. L'algorithme LexColor est basé sur l'algorithme LexBFS (pour Lexicographic Breath First Search) de Rose, Tarjan et Leuker [rostar76]. LexBFS sert à obtenir un ordre d'élimination simpliciale dans les graphes triangulés.

Nous proposons un algorithme linéaire que nous baptisons MCColor (pour Maximum Constraint Color) qui colore les graphes de Meyniel de manière optimale en temps O(n+m) [levmaf04]. De la même manière que l'algorithme LexColor, l'algorithme MCColor « simule » une contraction de paires d'amis. Cet algorithme est basé sur l'algorithme MCS (pour Maximum Cardinality Search) de Tarjan et Yannakakis [taryan84] qui est une simplification apportée à l'algorithme LexBFS et qui peut aussi être utilisé pour trouver un ordre d'élimination simpliciale dans les graphes triangulés.
L'algorithme MCColor peut être étendu pour trouver en temps linéaire une clique de taille maximum dans un graphe de Meyniel. Cette extension permet aussi à l'algorithme d'être robuste. L'entrée de l'algorithme peut être un graphe quelconque, en sortie on a soit « voici une coloration optimale et une clique de taille maximum », soit « le graphe n'est pas de Meyniel ».

Travail réalisé par Benjamin Lévêque (benjamin.leveque@imag.fr) et Frédéric Maffray (frederic.maffray@imag.fr).

Références :

[ber84] C. Berge et V. Chvàtal, Topics on Perfect Graphs, Ann. Discrete Math. 21 (1984), North-Holland, Amsterdam.

[burfon84] M. Burlet et J. Fonlupt, Polynomial algorithm to recognize a Meyniel Graph, Dans [ber84] 225-252.

[eve01] H. Everett, C.M.H. de Figueiredo, C. Linhares Sales, F. Maffray, O. Porto, B.A. Reed, Even pairs, Dans [ramree01] 67-92.

[garjoh79] M.R.Garey, D.S.Johnson, Computers and intractability, A Guide to the Theory of NP-Completeness, Freeman, San-Francisco, 1979.

[grolov84] M. Grötschel, L. Lovàsz, A. Schrijver, Polynomial algorithms for perfect graphs, dans [ber84] 325-356.

[her90] A. Hertz, A fast algorithm for coloring Meyniel graphs, J. Combin. Theory Ser. B 50 (1990) 231-240.

[hoa87] C.T. Hoàng, On a conjecture of Meyniel, J. Combin. Theory Ser. B 42 (1987) 302-312.

[levmaf04] B. Lévêque, F. Maffray, Coloring Meyniel graphs in linear time, http://hal.ccsd.cnrs.fr/ccsd-00001574.

[mey84] H. Meyniel, The graphs whose odd cycles have at least two chords, Dans [ber84] 115-119.

[ramree01] J.L. Ramirez-Alfonsin, B.A. Reed, Perfect Graphs, Wiley Interscience, 2001.

[rourus01] F. Roussel et I. Rusu, An O(n2) algorithm to color Meyniel graphs, Discrete Math. 235 (2001) 107-123.

[rostar76] D.J. Rose, R.E. Tarjan and G.S. Leuker, Algorithmic aspects of vertex elimination of graphs, SIAM J. Comput. 5 (1976) 266-283.

[taryan84] R.E. Tarjan et M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput. 13 (1984) 566-579.