Visualisation et Algorithmes de Graphes
Séminaire/Groupe de Travail


Archives année 2007-2008 Organisateurs : Emeric Gioan, Alexandre Pinlou


Retour à la page d'accueil du séminaire

Sommaire



26 juin            
Eric Bourreau
Eternity2, un problème de graphe ?

Eternity2 (http://fr.eternityii.com/) est un jeu de plateau (donc en 2 dimensions) qui consiste à assembler 256 pièces carrées de telle sorte que chaque bord coïncide avec son voisin adjacent (principe du puzzle ou edge-matching). Les pièces possédant une vingtaine de couleurs différentes rendent ce jeu assez compliqué d'un point de vue combinatoire. Nous essayerons de donner quelques caractéristiques propre à la problématique et quelques modèles à base de graphe afin de voir si des propriétés globales ou des algorithmes classiques peuvent s'appliquer et apporter des informations supplémentaire pour la résolution.

Transparents de l'exposé

19 juin            
Anders Yeo
A FPT algorithm for the 3-Hitting set problem.

A hitting set in a hypergraph, $H=(V,E)$, is a set of vertices $T \subseteq V$, such that every edge in $E$ contains at least one vertex from $T$. The 3-Hitting set problem is to find a minimum size hitting set in a 3-uniform hypergraph (i.e. all edges have size 3). We will give a FPT algorithm for this problem which by using a new method improves the theoretical bound of all previous algorithms. Our algorithm can also be used in areas such as computational biology (related to phylogenetic trees) and tournaments (where our algorithm beats the tournament specific algorithm for finding a minimum feedback vertex set) and total domination in graphs with maximum degree three. We will also mention several open problems and conjectures.

12 juin            
Mathieu Liedloff (LITA)
Algorithmes exacts pour une généralisation du problème de la domination d'un graphe

Etant donné un graphe, le problème fondamental de la domination demande de déterminer un plus petit sous-ensemble de sommets de sorte que chaque sommet n'appartenant pas à l'ensemble ait un voisin qui y soit. Le problème est NP-complet et seul un algorithme exponentiel peut calculer une solution exacte pour une entrée quelconque, sauf si P=NP. Depuis 2004, plusieurs algorithmes ont été publiés pour le résoudre dans un temps plus rapide que O(poly(n) 2^n). Dans cet exposé, nous considérerons une généralisation du problème: la (sigma,rho)-domination. Ce cadre très général permet de représenter de nombreux problèmes de type domination. Etant donné deux ensembles sigma et rho d'entiers positifs, un ensemble S est dit (sigma,rho)-dominant si (i) pour tout sommet v de S, le nombre de ses voisins dans S est un entier de sigma; (ii) pour tout sommet v de V-S, le nombre de ses voisins dans S est un entier de rho. Nous donnerons un algorithme exponentiel pour énumérer tous les ensembles (sigma,rho)-dominants d'un graphe en temps O(c^n), pour une certaine constante c<2, si l'ensemble sigma ne contient pas deux entiers consécutifs et si, soit sigma et rho sont finis, soit l'un d'eux est fini et leur intersection est vide. Nous regarderons également d'autres ensembles sigma et rho pour lesquels le problème peut être résolu en temps O(poly(n) 2^(n/2)).

Transparents de l'exposé

29 mai            
Pascal Ochem (LRI)
Partitions des sommets d'un graphe en stables et en cliques.

Pour un graphe G à n sommets, on s'intéresse aux couples (s,c) de NxN tels qu'il n'existe pas de partitions des sommets de G en s stables et c cliques. C'est une notion qui se rapproche de la coloration, des partitions en cliques, du nombre cochromatique, et de la théorie de Ramsey. On introduit le paramètre p(G) qui est le nombre de tels couples pour un graphe G.

On montre que:
- p(G) = n si G est un cographe.
- p(G) <= n si G est un graphe parfait.
- p(G) = \Omega(n2/log2(n)).
- p(G) = O(n2/log(n)).
- p(G) >= 3n/4 si G est un graphe biparti.

On conjecture que:
- p(G) = O(n2/log2(n)).
- p(G) >= n/2.

22 mai            
Christophe Paul
Décomposition en coupes et reconnaissance des graphes de cordes
(en commun avec Derek Corneil, Emeric Gioan et Marc Tedder)

Nous présenterons un algorithme de décomposition en coupes d'un graphe non-orienté quelconque. L'algorithme utilise le formalisme d'arbres étiquetés par des graphes pour représenter l'arbre de décomposition. La complexité quasi-linéaire est obtenue grâce à une analyse amortie utilisant des techniques de "déchargement". En autre conséquence, nous améliorons la complexité de la reconnaissance des graphes de cordes.

3 avril            
Louis Esperet (LaBRI)
Coloration adaptable des graphes planaires

Étant donnée une coloration F (potentiellement impropre) des arêtes d'un graphe G, une coloration des sommets de G est dite "adaptée" à F si aucune couleur n'apparaît à la fois sur une arête et sur ses deux extrémités. Le nombre chromatique adaptable de G est le plus petit entier k, tel pour toute arête-coloration F de G, G admet une k-coloration adaptée à F. Je ferai un rapide survol des résultats connus sur cette coloration (introduite récemment par Pavol Hell et Xuding Zhu), et j'expliquerai ensuite des résultats que nous avons obtenus avec Mickaël Montassier et Xuding Zhu sur le nombre chromatique adaptable des graphes planaires.

20 mars            
Emeric Gioan
Pseudodroites, dessins de graphes, graphes spatiaux et matroïdes orientés
séminaire commun ARITH / VAG

Les arrangements de pseudodroites, équivalents aux matroïdes orientés de rang 3, sont les ensembles finis de courbes du plan homéomorphes à des droites et se coupant exactement une fois deux à deux.
On commencera par voir leurs axiomatisations logiques.
Puis on verra comment passer aux dessins de graphes, notamment une propriété d'équivalence à mutations de triangles près.
Enfin on verra une application à la vue en projection des graphes complets spatiaux codés par des matroïdes orientés de rang 4.
Et surtout, vous aurez l'occasion inespérée de faire vous-même partie d'un matroïde orienté.

13 mars            
Mamadou Moustapha Kanté (LaBRI)
Etiquetage de propriétés du Premier Ordre en O(log(n))
(Travail en commun avec B. Courcelle et C. Gavoille)

Un graphe est "locally cwd-decomposable" si quelque soit un entier r, on peut couvrir le graphe avec des boules tel que : - pour tout sommet son voisinage de rayon r est inclus dans une boule - le graphe d'intersection des boules est de degré au plus d - chaque boule est de clique-width au plus w - d et w dépendent de r - cette couverture peut etre calculée en temps polynomial Cette classe contient par exemple les planaires, les graphes de degré borné, les unit-interval graphes ou les classes de graphes clos par mineurs et qui ne contiennent pas tous les apex. Cette classe a deja été étudiée par Frick, Grohe, ... Nous allons montrer que pour toute formule du premier ordre, il existe un schéma d'etiquetage de taille O(log(n)) dans la classe de graphes "locally cwd-decomposable". Si on a le temps, je montrerai comment étendre ce résultat au comptage. Pour cela je vais utiliser le théoréme local de Gaifman et une décomposition de certaines formules du premier ordre par Frick.

Transparents de l'exposé

6 mars            
Christophe Paul
Recherche de noyaux polynomiaux


Nous commencerons par présenter les techniques classiques permettant de prouver l'existence de noyaux de taille polynomiale pour les problèmes vertex-cover et 3-hitting set. Puis nous utiliserons ces résultats pour montrer l'existence d'un noyau polynomial pour le probleme de la k-edition de cographe : peut-on modifier k arêtes dans un graphe pour obtenir un cographe.

21 février            
Jean Daligault
Well-quasi-ordering de fonctions de recoloration

Je ferai un survol des définitions, propriétés importantes et théorèmes principaux sur le thème "well-quasi-ordering" de classes de graphes, et je présenterai ensuite un travail commun avec Michael Rao et Stéphan Thomassé. Le but de ce travail est la conjecture de Maurice Pouzet sur la relation sous-graphe induit : "2-wqo est équivalent à n-wqo". Nous présentons à cette fin une restriction (sur les fonctions de recoloration) de la hiérarchie NLC, et caractérisons les telles restrictions qui sont wqo (de manière équivalente n-wqo pour tout n). Nous conjecturons que cette hiérarchie caractérise entièrement les classes 2-wqo, ce qui impliquerait la conjecture de Pouzet.

14 février            
Flavio Guinez (Université Santiago du Chili & équipe VAG)
Decomposition of graphs into disjoint factors

Given a graph G and an integer function f of V(G), an f-factor of G is a set F of edges such that the degree function d_F of the graph induced by F is exactly f. The factor problem, to decide if a graph has or not an f-factor, was completely solved by Tutte as generalization of his perfect matching theorem. Since then many others results and versions of the problem have appeared (for example the (f,g)-factor theorem due to Lovász). Additionally, we can think every f-factor F as a partition of the edges of G into two sets F and E(G)-F, which are realizations of f and d_G - f, respectively. Thus, it is natural to consider another extension of the factor problem by taking an arbitrary number of integer functions of V(G) and to ask if it is possible to decompose E(G) into parts with those prescribed degree functions. We shall discuss the problem of the existence of such decompositions for both different number of parts and classes of graphs. We specially focus our attention in the decomposition into three parts of complete bipartite graphs, problem that has shown interesting properties and which complexity is an open problem in discrete tomography.

7 février            
Christophe Paul
Augmentation sémantique (via LSOM) et largeur arborescente : une nouvelle technique FPT

Les liens entre décompositions arborescentes (en toute généralité), logique du second ordre monadique (LSOM) et la complexité paramétrique sont connus depuis le théorème de Courcelle. Ce théorème nous permet par exemple d'envisager la méthode suivante pour montrer l'existence d'algorithmes FPT pour un problème de décision $(\Pi,k)$ donné:
1- Construire un graphe modèle $G_{\Pi}(I)$ où $I$ est la donnée du problème;
2- Montrer que si la largeur arborescente de $(G_{\Pi}(I)$ n'est pas bornée par une fonction de $k$, alors $(\Pi,k)$ n'est pas une instance positive;
3- Montrer que le problème $\Pi$ est exprimable en LSOM sur $G_{\Pi}(I)$
Nous illustrerons cette méthode sur quelques exemples.

31 janvier            
Binh-Minh Bui-Xuan
La décomposition bidulaire
(Ou "Vous avez aimé les modules et les u-modules, vous adorerez les bi-dules !!")

Il s'agit d'une généralisation stricte de la décomposition modulaire des graphes orientés (et aussi celle des 2-structures). À cette fin, nous allons également voir comment obtenir deux généralisations des familles partitives qui soient, toutes les deux, polynomialement représentables.

24 janvier            
Jean-Francois Pineau
L'impact de l'hétérogénéité sur l'ordonnancement à la volée sur une plate-forme maître-esclave

On s'intéresse ici au problème d'ordonnancement de tâches identiques et indépendantes avec dates d'arrivées sur une plate-forme maître-esclave. Alors que ce problème peut être résolu en temps polynomial sur une plate-forme homogène, il n'existe pas d'algorithme optimal déterministe dès l'ajout d'une source d'hétérogénéité, que cela soit au niveau des calculs ou des communications. On peut trouver ainsi des bornes inférieures de compétitivités pour plus de 3 fonctions objectives, et ce sur des plate-formes ayant différentes sources d'hétérogénéité. Des résultats expérimentaux illustreront également ce problème.

17 janvier            
Stéphane Bessy
Road Coloring Problem, la preuve de A.N. Trahtman

La Conjecture du Road Coloring Problem date d'une trentaine d'années et a récemment été résolue. Je présenterai cette conjecture ainsi que la preuve de Trahtman, s'appuyant principalement sur des arguments de théorie des graphes.
Une présentation du problème est disponible ici : http://www.lirmm.fr/~bessy/SujetTERM1RCP.html

21 décembre            
V. Patel (LSE, London)
Partitioning Posets

Let P=(X,<) be a poset. A down-set of P is a subset, A of X such that if a is in A and b<a, then b is also in A. For A a down-set of P and B its complement, define E(A,B) = {(a,b): a is in A, b is in B, and a<b}.
This defines an analogue of cuts for posets. In this talk we address the following natural questions: how large can |E(A,B)| be and how difficult is it to maximise |E(A,B)|?
We also generalise this notion to partitions of P into more than two sets and ask the same questions.

13 décembre            
Peter Allen (LSE, London)
Sparse Ramsey problems


Lehel conjectured that the vertices of any two-edge-coloured complete graph can be covered by two vertex-disjoint cycles of opposite colours. A proof that this is true for all sufficiently large graphs was given by Luczak, Rödl and Szemerédi. We give an alternative proof avoiding the Regularity lemma. By a similar method we find a new linear bound on the Ramsey number of the k-th power of a cycle.

6 décembre            
Benjamin Lévêque (G-SCOP, Grenoble)            
Coloration de graphes parfaits par contraction

De nombreux problèmes appliqués peuvent être modélisés par le problème de la coloration des sommets d'un graphe, qui est NP-complet en général mais polynomial sur la classe des graphes parfaits introduite par Berge. L'algorithme de coloration des graphes parfaits, de Grötschel, Lovasz et Schrijver, n'est pas réellement efficace d'un point de vue pratique et il est toujours intéressant de trouver un algorithme ``purement'' combinatoire permettant de colorier les graphes parfaits en temps polynomial.
Nous donnons plusieurs algorithmes simples et rapides permettant de colorier des sous-classes de graphes parfaits. Ces algorithmes utilisent en particulier la notion de contraction de paire d'amis, introduite par Fonlupt et Uhry, à propos de laquelle plusieurs conjectures sont encore ouvertes. Nous utilisons aussi des algorithmes de parcours comme LexBFS, de Rose, Tarjan et Lueker, pour prouver des résultats structuraux sur les graphes considérés.

Transparents de l'exposé

22 novembre            
Nancy Rodriguez            
Structures multi-échelle pour la synthèse d'images



15 novembre            
Stéphan Thomassé
Stables transversaux dans les graphes partitionnés

Dans cet exposé au pied levé, je tenterai de faire un petit survol sur les résultats du type suivant:
Entrée: G un graphe et P=V_1,...,V_k une partition de ses sommets.
Sortie: VRAI s'il existe un ensemble stable de G qui touche toutes les classes de G. FAUX s'il n'existe pas.

18 octobre            
Stéphane du Rocher (McGill, Montréal)
Kinetic Maintenance of Mobile k-Centres on Trees
(joint work with Christophe Paul)

Let $C$ denote a set of $n$ mobile clients, each of which follows a continuous trajectory on a weighted tree $T$. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of $C$. When each client in $C$ moves with linear motion along a path on $T$ we derive a tight bound of $\Theta(n)$ on the complexity of the motion of the 1-centre and corresponding bounds of $O(n2 \alpha(n))$ and $\Omega(n2)$ for a 2-centre, where $\alpha(n)$ denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of $C$: the 1-centre can be found in optimal time $O(n \log n)$ when the distance function between mobile clients is known or $O(n2)$ when the function must be calculated, and a 2-centre can be found in time $O(n2 \log n)$. These algorithms lend themselves to implementation within the framework of kinetic data structures, resulting in structures that are compact, efficient, responsive, and local. I will provide some background, a discussion, and more general examples on kinetic data structures.

11 octobre            
Philippe Gambette
Graphes 2-intervallaires, classes voisines et sous-classes

(en collaboration avec Michel Habib et Stéphane Vialette)

Les graphes 2-intervallaires ont été introduits comme généralisation des graphes d'intervalles à la fin des années 70 pour modéliser des problèmes d'ordonnancement. Ils ont plus récemment attiré l'attention des bioinformaticiens pour l'étude de la structure secondaire et la comparaison d'ARN. Nous présenterons tout d'abord comment le problème de détermination de la structure secondaire et diverses variantes se rapportent à l'étude du stable maximum sur des classes de graphes d'intersection. Puis nous nous intéresserons à des sous-classes des graphes d'intervalles dont l'introduction est justifiée biologiquement, et présenterons des résultats sur leur complexité et leurs liens avec d'autres classes de graphes : d'arcs circulaires propres, quasi-adjoints, sans griffe (ou plus classiquement : proper circular arc, quasi-line, claw-free)...

4 octobre            
Daniel Gonçalves
Les graphes planaires et leur modèle d'intersection de segments

(en collaboration avec J.Chalopin)

Étant donné un graphe G et un ensemble S de segments du plan, S est un modèle de G s'il y a une bijection b entre V(G) et S telle que : uv est une arête de G ssi les segments b(u) et b(v) s'intersectent. Dans sa thèse Scheinerman a conjecturé que tout graphe planaire a un tel modèle. Différents travaux ont porté sur des familles restreintes de graphes planaires telles que les graphes planaires bipartis ou sans triangles. Dans cet exposé, nous présenterons une preuve de cette conjecture pour tous les graphes planaires.

27 septembre            
Alexandre Pinlou
Coloration orientée des graphes planaires


Il est bien connu que, dans le cas non orienté, colorier les sommets d'un graphe G avec k couleurs est équivalent à montrer que G admet un homomorphisme vers un graphe H à k sommets (généralement une clique). Il est naturel d'étendre cette définition au cas des graphes orientés. Ainsi, une coloration d'un graphe orienté G avec k couleurs sera définie comme un homomorphisme de G vers un graphe orienté H à k sommets.
Ce type de coloration est étudié depuis bientôt 15 ans et de nombreuses bornes du nombre chromatique orienté ont été obtenue pour diverses classes de graphes.
Une des classes de graphes particulièrement intéressante est la classe des graphes planaires. En effet, Raspaud et Sopena ont montré en 1994 que le nombre chromatique orienté de cette classe est d'au plus 80. Cette borne supérieure semble particulièrement élevée, mais malgré de nombreuses tentatives, personne n'a réussi à la réduire. Durant l'exposé, je vous présenterai la preuve de Raspaud et Sopena.
Un certain nombre d'auteurs se sont alors intéressés aux graphes planaires de maille donnée, espérant ainsi obtenir de meilleures bornes pour ces sous-classes de graphes planaires. Divers résultats ont été obtenu et notamment le suivant dû à Borodin et al. en 1999 : Tout graphe planaire de maille au moins 5 possède un nombre chromatique orienté d'au plus 19. Je vous montrerai comment améliorer cette borne et montrer que 16 couleurs sont suffisantes.

20 septembre            
Michaël Rao
Décompositions et unicité


Les décompositions de graphes basées sur les familles (bi-)partitives possèdent différentes propriétés intéressantes; on peut citer l'unicité de l'arbre de décomposition, et l'assurance d'obtenir un algorithme polynomial de décomposition à partir du moment où on sait trouver un motif de base en temps polynomial.
Dans un premier temps, on présentera différentes décompositions (déjà connues ou nouvelles) basés sur des familles bi-partitives. Ces décompositions sont des généralisations de la décomposition modulaire. On peut citer la décomposition en coupes, la décomposition bi-join, ainsi que des généralisations sur les graphes orientés.
La largeur NLC est une variante de la largeur de clique (clique-width). Dans la deuxième partie, on verra comment certaines des décompositions cités précédemment peuvent servir pour obtenir un algorithme simple, en temps O(n2 m), pour calculer une décomposition canonique des graphes de largeur NLC 2. Cette décomposition canonique permet en particulier de tester l'isomorphisme entre deux graphes le largeur NLC 2 en temps O(n2 m).

Transparents de l'exposé