Equipes concernées

Montpellier: Equipe VAG du LIRMM

• Stéphane Bessy Maitre de Conférences
• Binh-Minh Bui-Xuan, Doctorant
• Jean Daligault, Doctorant
• Emeric Gioan, Chargé de Recherche
• Daniel Goncalves, Chargé de Recherche
• Christophe Paul, Chargé de Recherche
• Alexandre Pinlou, Post-Doctorant
• Stéphan Thomassé, Professeur

Sophia-Antipolis: Projet Mascotte (projet commun I3S/INRIA)

• Marie Asté, Doctorante
• Jean-Claude Bermond, Directeur de Recherche
• Frédéric Havet, Chargé de Recherche
• Florian Huc, Doctorant
• Christelle Molle, Doctorante
• Stéphane Pérennes, Chargé de Recherche
• Ignasi Sau-Valls, Doctorant

Objectifs scientifiques

    Les graphes sont largement utilisés aussi bien comme modèles que comme outils dans de nombreux domaines des mathématiques et de l’informatique. Un des principaux problèmes en théorie des graphes consiste à capturer la complexité de leur structure à travers certaines décompositions. Une des facons les plus simples de le faire est de partitionner l’ensemble des sommets sous certaines contraintes. Par exemple, si on exige que chaque partie soit un ensemble indépendant, on cherche une coloration du graphe. Une autre manière de partitionner le graphe consiste à maximiser ou minimiser le nombre d’arêtes entre deux parties (problèmes MaxCut et MinCut). Pour ce genre de questions, il existe des méthodes exactes et des heuristiques comme les flots [5], la programmation semi-définie positive [2], les méthodes probabilistes [1,4]… Cependant, lorsque les problèmes de partition concernent non plus les graphes mais les graphes orientés, la situation devient beaucoup plus difficile — et souvent aucune des méthodes existantes ne semble fonctionner. Nous comptons nous attaquer à différentes questions ouvertes concernant les partitions de graphes orientés, dans le but d’essayer de développer de nouvelles méthodes, les questions suivantes notamment qui ont été choisies de manière à couvrir différents aspects. Grossièrement, pour la première question, la contrainte porte sur les sommets, pour la seconde sur les arêtes et pour la dernière sur les circuits.

     Le degré minimum est un des invariants de graphes les plus simples. Son analogue orienté, le “degré sortant minimum”, est, malgré sa simplicité, l’un des invariants de graphes orientés les moins bien compris. Par exemple, le problème suivant du à M. Stiebitz et popularisé par N. Alon, est toujours ouvert:
Existe-t-il une fonction f telle que tout graphe orienté de degré sortant minimum f(k) ait une partition des sommets en deux graphes orientés, chacun d’entre eux ayant degré sortant minimum au moins k?
Très peu de choses sont connues sur cette question. L’existence même de f(2) n’est pas établie. Cependant, on peut remarquer que pour la question similaire où on remplace le degré sortant par le degré sortant et le degré entrant, l’existence d’une telle fonction est une application directe du Lemme Local de Lovasz. Prouver ne serait-ce que f(2) ≤ 10¹⁰ serait déjà un accomplissement puisqu’aucune méthode ne semble pouvoir l’établir.

     Un autre aspect des graphes orientés qui est très mal compris concerne les orientations équilibrées. Le problème consiste à orienter un graphe de manière à ce que pour toute partition des sommets en deux ensembles X et Y, il y ait à peu près le même nombre d’arêtes orientées de X vers Y (e(X,Y)) que d’arêtes orientées de Y vers X (e(Y,X)). Une conjecture très difficile, connue comme la Conjecture du 5-flot de Tutte, affirme que tout graphe sans pont (ou 2-arête-connexe) admet une orientation telle que e(X,Y) ≤ 4e(Y,X) pour toute partition (X,Y). Récemment, C. Thomassen a demandé si tout graphe G d’arête-connexité assez grande admet une orientation telle que e(X,Y) ≤ 2e(Y,X) pour toute partition (X,Y). Une intuition raisonnable est que pour tout ε > 0, il existe un entier N_ε_ pour lequel tout graphe N_ε_-arête connexe admet une orientation telle que e(X,Y) ≤ (1+ε)e(Y,X) pour toute partition (X,Y).
Il s’avère que l’existence d’une telle orientation est impliquée par celle d’une partition équilibrée particulière du graphe. Plus précisément, on aimerait montrer qu’il existe une fonction g telle que tout graphe pair g(k)-arˆte connexe ait une partition équilibrée (X,Y) telle qu’il y ait k couplages de chemins entre X et Y. Mais de nouveau, aucune méthode ne semble\ fonctionner et l’existence de g(3) n’est pas connue.

     Une autre jolie question, originellement posée par V. Neumann-Lara, concerne les partitions de graphes orientés planaires: ‘’Tout graphe planaire orienté admet une partition de ses sommets en deux sous-graphes acycliques.’‘ En d’autres termes, tout graphe orienté planaire admet une partition dont la coupe associée intersecte tous les circuits. Ceci implique qu’un graphe orienté planaire à n sommets possède un ensemble d’ar&ecric;tes qui intersecte tous les circuits (feed-back arc set) de taille inférieure à 4n car un graphe biparti planaire a moins de 4n arêtes. Ceci n’est pas optimal comme le montre un résultat très proche, le théorème de Lucchesi-Younger [4]: Le nombre maximum de circuits arête-disjoints dans un graphe planaire est égal au nombre minimum d’arêtes intersectant tous les circuits. Ce résultat de dualité est bien compris mais ne semble malheureusement pas s’appliquer pour cette conjecture.

Il serait optimiste de prétendre obtenir une avancée importante sur l’un de ces problèmes. Cependant, tout progrès, nouvelle méthode ou heuristique serait un premier pas intéressant.

[1] N. Alon and J. H. Spencer, The probabilistic method. Second edition. Wiley-Interscience [John Wiley \& Sons], New York, 2000. xviii+301 pp. ISBN: 0–471–37046–0

[2] M. X. Goemans and D. P. Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J. Comput. System Sci. 68 (2004), no. 2, 442-−470.

[3] C. L. Lucchesi and H. Younger, A minimax theorem for directed graphs, Journal London Mathematical Society, 17 (1978), 369-−374.

[4] M. Molloy and B. Reed, Graph colouring and the probabilistic method. Algorithms and Combinatorics, 23. Springer-Verlag, Berlin, 2002. xiv+326 pp. ISBN 3–540–42139–4

[5] A. Schrijver, Paths and flows---a historical survey. CWI Quarterly 6 (1993), no. 3, 169-−183.