Stage M2 MPRI - Les graphes 2-intervallaires (LIAFA, Michel Habib)

(In English)

Graphes 2-intervallaires et séquences arc-annotées

Les graphes 2-intervallaires permettent de représenter un ensemble de paires d'intervalles de réels : les noeuds sont les 2-intervalles, et ils sont reliés par une arête si les 2-intervalles ont une intersection non-vide. Divers problèmes peuvent être étudiés grâce à ces graphes : l'étude de la structure secondaire de l'ARN, ou encore l'ordonnancement sur une machine de tâches séparées en 2, comme celles liées aux radars.

L'approche de ces problèmes par des méthodes de graphes permet d'utiliser la littérature abondante sur le sujet. En effet, on cherche à ramener le problème, ou des variations afin d'obtenir une meilleure complexité, à un problème (typiquement le problème d'ensemble indépendant de taille maximale) sur un graphe d'une certaine classe, bien connue... ou à explorer pour en découvrir les propriétés et la situer dans la hiérarchie des classes de graphes.

Je me suis notamment intéressé à la classe des graphes 2-intervallaires équilibrés (quand les deux intervalles supports d'un même 2-intervalle ont même longueur) qui s'avère strictement incluse dans celle des graphes 2-intervallaires. La preuve du contrexemple exhibé fait intervenir divers outils mathématiques et informatiques, afin de construire un graphe 2-intervallaire dont la réalisation en 2-intervalles est fortement contrainte.

J'ai aussi synthétisé toutes les informations utiles sur la classe des graphes 2-intervallaires, ainsi que sur les diverses variantes d'un problème de plus grand sous-ensemble de 2-intervalles, introduit par Stéphane Vialette sous le nom de 2-Interval Pattern (2-IP). Ce panorama conduit à étudier une restriction des 2-intervalles, quand on impose aux intervalles supports des 2-intervalles une taille unitaire et des bornes entières : les séquences arc-annotées, dont je donne plusieurs méthodes d'énumération. En particulier, la suite du nombre de séquences arc-annotées selon le nombre d'arcs n'était pas présente dans l'encyclopédie en ligne des entiers, mais a été ajoutée indépendemment en fin de stage par Vladeta Jovovic, qui a proposé au passage une nouvelle méthode et une jolie formule d'énumération détaillées dans le mémoire.


Enfin, j'ai buté sur la dernière variante non résolue du problème 2-IP : rechercher dans une séquence arc-annotée l'ensemble maximal d'arcs qui soient seulement croisés, ou successifs (ils n'ont pas d'extrémité commune, et ne sont pas emboîtés). Les efforts pour trouver un algorithme ont été vains, et il semble que la NP-complétude de ce problème soit plus probable, encore que là aussi mes recherches de réductions n'ont pas porté leurs fruits.

Restrictions de la classe des graphes 2-intervallaires équilibrés

Mon travail sur les graphes 2-intervallaire s'est poursuivi pendant un an au LIAFA, je me suis focalisé sur des classes plus restreintes (2-intervallaires équilibrés, unitaires, (x,x)-intervallaires...), étudiant la complexité de leur reconnaissance et les relations d'inclusions avec d'autres classes de graphes plus connues (graphes d'arc circulaires, propres, graphes quasi-adjoints, sans griffe...), ce qui a abouti sur un article présenté à la conférence WG'07.

Documents :

• Un théorème de reconnaissance des graphes (2,2)-intervallaires parmi les bipartis.
• On restrictions of 2-interval graphs (avec Stéphane Vialette), un article présenté à WG'07 (présentation au format PDF, source OpenOffice, son mp3).
• Un BibTex sur les graphes 2-intervallaires.
• Une mise au propre de la page d'ISGCI sur les graphes 2-intervallaires (idem pour les claw-free, et nouvelle page pour les quasi-line).
• Mémoire de master (mis à jour) sur les graphes 2-intervallaires (version présentée au jury le 15/09/2006).
• Une présentation aux Journées Graphes et Algorithmes à Orléans sur les graphes 2-intervallaires, (JGA'06, 10/11/2006, source OpenOffice).
• Une présentation au séminaire thésards LIAFA/PPS, avec en introduction le problème du Duc de Densmore, et l'idée de la preuve de West&Shmoys de NP-complétude de la reconnaissance des 2-intervallaires (08/11/2006, source OpenOffice).
• Transparents de la soutenance devant le jury du MPRI (15/09/2006, source OpenOffice).
• Mon BibTeX, qui s'est bien enrichi lors de ce stage.
• D'autres ressources bibliographiques très utiles :
  • un joli cours de Gabriel Valiente sur certaines classes de graphes d'intersection
  • Les BibTeX de Lorna Stewart
• Le nuage des 100 mots les plus fréquents dans mon mémoire de master (construit avec Freecorp TagBuilder) :
  
  absurde adn algorithme annexe annotées arc arêtes arn astéroïde biparti cas chapitre chemin chromatique circulaires classe clique comparabilité complémentaire complet complexité construire contrexemple cordes coupe couplage couples couverture couvrant cycle degré dénombrement disjoints doit droit droite dynamique éclatement effet ensembles entiers entrelacement équilibrés étiquetés eulérien exemple existe extrémité génération grand graphe inclusion indépendant intersectant intersecter intersection intervallaire intervalle linéaire log max maximale maximum noeuds nombre noté notes np obtenir ordonnancement ordre parcours permet permutation polynomial possibles précédence problème programmation propriété réalisation recherche relation résoudre second section séquences seulement sommets stable structure support taille théorie trapézoïdal trapézoïdes triplet trouver unions unitaire