AlGCo : algorithmique, graphes et combinatoire
Séminaire/Groupe de Travail

Laurent Beaudou ISIMA (Université Blaise-Pascal, Clermont-Ferrand)
Homomorphismes des cubes projectifs

L'exposé tourne autour des homomorphismes de graphes et en particulier des cubes projectifs (cubes dont on identifie les sommets antipodaux) vers des cubes de dimensions inférieures. Nous prouvons que les homomorphismes du cube projectif de dimension 6 dans celui de dimension 4 sont toujours surjectifs.

Annegret Wagler ISIMA (Université Blaise-Pascal, Clermont-Ferrand)
Computing clique and chromatic number for circular-perfect graphs

Le résumé en pdf.

Marthe Bonamy, Rémi Watrigant (étudiants Master 2 R) LIRMM (Université Montpellier 2)
Présentation de leurs sujets de Master 2 Recherche

• Marthe Bonamy : Colorier à distance 2 des graphes peu denses
  On s'intéresse aux conditions suffisantes sur la densité du graphe et sur son degré maximal d pour que le nombre chromatique de son carré atteigne la borne inférieure, d+1. On présente notamment des résultats pour d>3 qui améliorent des bornes existantes, de Dolama et Sopena ainsi que de Borodin et al.
  
  
• Rémi Watrigant : Bornes inférieures pour la kernelization (méthodes et outils)
  Après un rappel sur la complexité paramétrée et les noyaux, je vais donc parler des méthodes pour montrer des bornes inférieures sur ceux-ci (typiquement des résultats négatifs sur l'existence de noyau polynomial pour des problèmes) : compositions, transformations, cross-composition. Je montrerai une cross-composition simple pour le problème de l'ensemble dominant qui simplifie une preuve déjà connue, et je terminerai en parlant de paramétrisations non triviales pour des problèmes de graphes, et des hiérarchies de paramètres.

Eunjung Kim LIRMM (Université Montpellier 2)
Algorithms and Complexity Results for Persuasive Argumentation

The study of arguments as abstract entities and their interaction as introduced by Dung (Artificial Intelligence 177, 1995) has become one of the most active research branches within Artificial Intelligence and Reasoning. A main issue for abstract argumentation systems is the selection of acceptable sets of arguments. Value-based argumentation, as introduced by Bench-Capon (J. Logic Comput. 13, 2003), extends Dung's framework. It takes into account the relative strength of arguments with respect to some ranking representing an audience: an argument is subjectively accepted if it is accepted with respect to some audience, it is objectively accepted if it is accepted with respect to all audiences.
Deciding whether an argument is subjectively or objectively accepted, respectively, are computationally intractable problems. In fact, the problems remain intractable under structural restrictions that render the main computational problems for non-value-based argumentation systems tractable. We identify nontrivial classes of value-based argumentation systems for which the acceptance problems are polynomial-time tractable. The classes are defined by means of structural restrictions in terms of the underlying graphical structure of the value-based system. Furthermore we show that the acceptance problems are intractable for two classes of value-based systems that where conjectured to be tractable by Dunne (Artificial Intelligence 171, 2007).

Stéphan Thomassé LIRMM (Université Montpellier 2)
Tournaments and colouring

A tournament is a complete graph with its edges directed, and colouring a tournament means partitioning its vertex set into transitive subtournaments. For some tournaments H there exists c such that every tournament not containing H as a subtournament has chromatic number at most c (we call such a tournament H a hero); for instance, all tournaments with at most four vertices are heroes.
In this paper we explicitly describe all heroes.

Travail réalisé en commun avec E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott et P. Seymour

Journée en l'honneur de Jean-Claude Bermond

Les exposés se dérouleront dans l'amphithéatre Saint-Priest.

10h : Stéphane Bessy (LIRMM)
La conjecture de Jean-Claude/Carsten dans le cas des tournois: une condition pour trouver des circuits disjoints.

En 1981, J.C. Bermond et C. Thomassen ont proposé la conjecture suivante concernant les graphes orientés: pour tout entier k, tout digraphe ayant un degré sortant minimum d'au moins 2k-1 possède k circuits disjoints.
On sait que la conjecture est vraie pour de petites valeurs de k (1,2,3) et que le digraphe complet doublement orienté fourni un exemple extrémal. Avec J. Bang-Jensen et S. Thomassé, nous avons montré quelle est vraie pour la classe des tournois, ce qui n'était pas connu précédemment.
Au cours de l'exposé, je présenterai certains résulats connus ayant des liens avec cette conjecture, je donnerai le schéma de la preuve que nous avons obtenue, j'indiquerai aussi une amélioration du résultat que nous avons prouvé et je finirai en mentionnant quelques questions ouvertes en rapport avec cette problématique.

11h15: Pause café

11h : Ignasi Sau (LIRMM)
Groupage de trafic dans les anneaux bidirectionnels WDM

Dans cet exposé nous étudions une variante du groupage de trafic dans les réseaux optiques, qui est un des problèmes sur lesquels Jean-Claude Bermond a le plus travaillé pendant les dernières 10 années. Notamment, nous parlerons du premier problème de recherche auquel je me suis affronté : la minimisation du nombre d'ADMs ("Add-Drop Multiplexers") dans les anneaux bidirectionnels WDM avec groupage de trafic. Nous supposons que le routage est symétrique et utilise des plus courts chemins, et que l'ensemble de requêtes est "all-to-all". Nous exprimons le problème en termes de décompositions de graphes et établissons des bornes inférieures et supérieures (parfois, optimales) en utilisant des outils combinatoires.

12h: Repas (buffet froid) - L'inscription est obligatoire !

14h15: Jean-Claude BERMOND (Projet Mascotte, commun I3S (CNRS/UNS) et INRIA Sophia-Antipolis Méditerranée)
Graphes, hypergraphes et réseaux

Le but de la conférence est d'exposer des problèmes simples de conception de réseaux qui m'ont intrigué pendant de nombreuses années (et continuent de m'intriguer). Les réseaux de télé communications mais aussi les réseaux routiers ou sociaux se modélisent bien avec des graphes. Les sommets représentent les routeurs (abonnés, villes, individus, ...) et les arêtes des liaisons ou des relation. Je partirai d'un problème simple à énoncer mais difficile à résoudre : construire des réseaux (graphes) de degré maximum donné et de diamètre donné. J'essaierai de montrer l'imagination débordante dans les outils utilisés (géométries finis, graphes probabilistes, groupes, constructions récursives, constructions sur alphabets, arithmétique, opérations de graphes, configurations,...) et comment utiliser cela pour un tour de cartes.
Je parlerai aussi s'il reste du temps de l'extension aux hypergraphes (réseaux par bus ou groupes) où quasi tout reste à trouver ....

Mickaël Montassier LaBRI, Bordeaux
Partitions des sommets d'un graphe en forêts d'étoiles et cographes

Dans cet exposé, nous parlerons de partition des sommets d'un graphe où le graphe induit par chaque ensemble de la partition est une forêt d'étoiles ou un cographe. Dans un premier temps, nous montrerons qu'il existe des graphes planaires de maille au moins 4 qui n'admettent pas de partitions en deux cographes ; nous montrerons ensuite que le problème "décider si un graphe planaire de maille au moins 4 admet une partition en deux cographes" est un problème NP-complet, répondant ainsi à une question de Gimbel et Nesetril sur le sujet. Ce travail est réalisé en commun avec Paul Dorbec (LaBRI) et Pascal Ochem (LRI).

George B. Mertzios Caesarea Rothschild Institute for Computer Science, University of Haifa, Haifa, Israel
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely multitolerance graphs, two tolerances are allowed for each interval -- one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval -- together with their convex hull -- define an infinite number of the so called tolerance-intervals, which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called trapezoepipeds. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with n vertices and m edges, we present algorithms that compute a minimum coloring and a maximum clique in optimal O(n log n) time, and a maximum weight independent set in O(m + n log n) time. Moreover, our results imply an optimal O(n log n) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs. The resulting hierarchy of classes of perfect graphs is complete, i.e. all inclusions are strict.

The preliminary conference version of this work appeared in SODA 11.

Louis Esperet G-SCOP, Grenoble
Couplages parfaits dans les graphes cubiques

On montre que tout graphe cubique sans isthme à n sommets a au moins 2^(n/3656) couplages parfaits. Cela confirme une conjecture de Lovasz et Plummer.

Christophe Paul LIRMM, Montpellier
Un algo FPT pour l'extraction un graphe bipartie en peu de contractions d'arêtes
Un travail avec P. Heggernes, P. van't Hof et D. Lokshtanov

Le problème Contraction-to-Bipartite consiste à contracter un ensemble d'arêtes d'un graphe pour obtenir un graph biparti. Nous montrons que Contraction-to-Bipartite est FPT s'il est paramétré par k le nombre d'arêtes à contracter.

Bien que ce problème semble similaire au problème classique "traversal des cycles impairs" (OCT), les techniques utilisé pour le résoudre sont très différentes. Nous utilisons d'abord une étape de compression itérative, puis l'application de la technique de réduction basée sur des "ensembles importants" et les sommets/arêtes "inutiles" nous permet de reduire le problème à une instance de treewidth bornée. Une formulation MSO permet de conclure.

Christophe Paul et Remi Watrigant LIRMM, Montpellier
Cross-composition : "nouvelle" technique FPT pour montrer des bornes inf de noyaux.

Cette semaine, le séminaire habituel laisse place à une séance de travail sur la cross-composition. Toute l'équipe est conviée à cette séance.

Vincent Limouzy LIMOS, Clermont-Ferrand
Complémentation de Seidel et graphes permutations

Je présenterai dans cet exposé un opérateur local de graphe, nommé complémentation de Seidel. Cet opérateur permet d'obtenir une nouvelle caractérisation des graphes de permutations en termes de motifs interdits. Je montrerai les liens qu'il y a avec la décomposition modulaire. Je montrerai également que le problème de décider si deux graphes sont équivalents vis à vis de cette opération est ISO-complet.

Dieter Kratsch LITA, Metz
Colorings with few colors

Exact exponential algorithms for enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings with few colors are presented. For all those problems the decision version is NP-complete even for a fixed and small number of available colors.
The talk mainly considers edge 3-colorings.
(i) There is a branching algorithm to enumerate all edge 3-colorings of a connected cubic graph in time O^*(2^{5n/8}).
(ii) This implies that the maximum number of edge 3-colorings in an n-vertex connected cubic graph is O^*(2^{5n/8}).
(iii) The maximum number of edge 3-colorings in an n-vertex connected cubic graph is lower bounded by 2^{n/2}.
(iv) For any epsilon > 0, the number of edge 3-colorings of a graph can be counted in time O^*(3^{(1/6+epsilon)n}),
Related results for total colorings and L(2,1)-labelings will be mentioned.

Ioan Todinca LIFO, Orléans
Ajouter un arbitre à un réseau d'interconnexion : que (ne) peut-on (pas) calculer en une étape de communication ?

Nous considérons un modèle de communication formé d'un graphe non orienté quelconque G, plus un sommet "arbitre" qui peut communiquer avec tous les autres. Chaque sommet a une vue locale du réseau: il connaît son identifiant et les identifiants de ses voisins. Les communications sont synchrones et par chaque arête on peut faire passer une petite quantité d'information, O(log n). Nous montrons que, après un seul round de communication, l'arbitre peut décider si le graphe G est un arbre ou même s'il est de dégénerescence bornée (en particulier on reconnaît les graphes planaires, les graphes de largeur arborescente bornée...). Du côté négatif, nous montrons qu'il n'existe pas de protocole en un round pour décider si le graphe G possède un triangle ou si G est de petit diamètre. De nombreux problèmes restent ouverts, comme l'existence d'un protocole "frugal" en un round pour vérifier la connexité du graphe G.

Emmanuel Jeandel LIF, Marseille
Fixed Parameter Intractability for Tilings

Le modèle des pavages par tuiles de Wang a été introduit en 1961 pour comprendre certains fragments de la logique du premier ordre. Son doctorant Berger a ensuite prouvé l'indécidabilité de la pavabilité pour ce modèle.

Bien entendu, si on fixe le nombre de tuiles ou le nombre de couleurs, le problème devient décidable pour des raisons triviales (nombre fini de cas). Dans cet exposé, on s'intéressera à trouver un paramètre naturel associé à un jeu de tuiles et on montrera l'indécidabilité à paramètre fixé. Un ingrédient important de la preuve est l'étude du cas (décidable) en dimension 1, et les liens qu'il possède avec la théorie des graphes.

Jean-Sébastien Sereni LIAFA, Paris 7
Gurvits's proof of the van der Waerden Conjecture.

The van der Waerden Conjecture about permanents of doubly stochastic matrices was stated in 1926, and proved in 1981 by Egorychev and, independently, Falikman. In 2008, Gurvits found a simple, beautiful and elementary proof of both this conjecture and an extension of a theorem of Schrijver (whose original proof was most complicated).

The goal of the talk is to convey the main ideas used by Gurvits. After a presentation of van der Waerden's Conjecture and its links with other problems, we will introduce the ideas used by Gurvits, state its theorem and derive from it the two aforementioned results. Last, we shall formally prove the theorem, as much as time permits.

Omid Amini DMA, ENS Ulm
Questions de théorie des graphes issues de la géométrie tropicale

Philip Geevarghese The Institute of Mathematical Sciences, Chennai, India
Connected Dominating Set in Graphs with (no) Small Cycles
This is joint work with Neeldhara Misra, Venkatesh Raman, and Saket Saurabh, accepted at FSTTCS 2010.

In the CONNECTED DOMINATING SET problem we are given as input a graph G and a positive integer k, and are asked if there is a set S of at most k vertices in G such that (1) S is a dominating set of G, and, (2) the subgraph of G induced by S is connected. This is a basic connectivity problem that is known to be NP-complete. In this talk we explore the effect of excluding short cycles, as a subgraph, on the kernelization complexity of CONNECTED DOMINATING SET.
Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer k (the parameter) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function g(k). The new instance is called a g(k) kernel for the problem. If g(k) is a polynomial, then we say that the problem admits a polynomial kernel. The girth of a graph G is the length of a shortest cycle in G.
It turns out that CONNECTED DOMINATING SET is "hard" on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we arrive at the following interesting trichotomy:

CONNECTED DOMINATING SET
• does not have a kernel of any size on graphs of girth 3 or 4 unless FPT = W[2];
• admits a g(k) kernel, where g(k) is roughly k^{O(k)} , on graphs of girth 5 or 6, but has no polynomial kernel on these graphs unless NP ⊆ coNP/Poly;
• has a cubic (O(k^3)) kernel on graphs of girth at least 7.

While there is a large and growing collection of parameterized complexity results known for problems on graph classes characterized by excluded minors, these results add to the very few known in the field for graph classes characterized by excluded subgraphs.

Fabien Mercier Univ. Paris 6
Switching reconstruction for oriented and colored graphs
(avec J.A. Bondy)

Stanley defined in 1981 a new reconstruction problem, called the switching reconstruction problem, in which switching at a vertex consists in replacing all non-edges incident to that vertex with edges and vice-versa.
We define a new reconstruction problem for oriented graphs and colored graphs, and prove results similar to those of Stanley, Ellingham and Royle, with a new approach that uses the "switching matrix". This new approach also applies to Stanley's original problem, and to other reconstruction problems.

David Coudert INRIA, Sophia-Antipolis
Des algorithmes à paramètre fixé dans les groupes de ressources partageant un risque.

Un groupe de ressources partageant un même risque de panne (shared risk resources group, SRRG) est un ensemble de ressources (noeuds, liens) qui peuvent être affectés simultanément par un panne. Dans un réseau WDM, c'est typiquement un ensemble de fibres optiques enterrées dans une même tranchée (coups de pelleteuse), ou des liens distants affectés par un même tremblement de terre. Dans ce contexte, la qualité d'un chemin se mesure par le nombre le groupes de risques auxquels il appartient, et nous cherchons des paires de chemins ne partageant pas les mêmes risques.
Dans cet exposé, nous ferons un état de l'art des principaux résultats de complexité et d'(in)approximabilité des problèmes classiques d'optimisation combinatoire (chemin, coupes,...) dans ce contexte. Nous présenterons les deux notions principales dans ces études: la propriété d'étoile et le span. Nous montrerons dans quels cas certains problèmes peuvent être résolus par des algorithmes polynomiaux ou à paramètre fixé (FPT).

Gwénael Joret Université Libre de Bruxelles, Belgique
Small Minors in Dense Graphs
(Joint work with Samuel Fiorini, David R. Wood, and Dirk O. Theis.)

A well-known result of Mader in graph minor theory is that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions f and g such that every graph with n vertices and average degree at least f(t) contains a K_t-model with at most g(t)log n vertices. For t<=4, we determine the least value of f(t).

Transparents de l'exposé

Kevin Sol LIRMM, Univ. Montpellier 2
Orientation de simplexes selon des ordres sur les coordonnées des sommets
En collaboration avec Emeric Gioan et Gérard Subsol

L’orientation d’un simplexe (généralisation d’un tétraèdre en dimension quelconque) se calcule en cherchant le signe d’un déterminant. Nous nous intéressons à des simplexes pour lesquels, pour chaque coordonnée de l'espace, un ordre est fixé entre les différents sommets.
Nous avons montré, pour les cas en 2D et 3D, que le signe de ce déterminant est constant si et seulement si il existe un développement adéquat du déterminant permettant d'en déterminer directement le signe à partir des ordres donnés, et sans calcul numérique. Autrement dit, nous avons un algorithme combinatoire qui décide si un déterminant est de signe constant quelles que soient les coordonnées des points, uniquement à partir d’un ensemble d’ordres imposés sur les coordonnées des points.
Nous conjecturons que cette méthode de caractérisation combinatoire se généralise en dimensions supérieures.

Transparents de l'exposé

Bruno Grenet ENS Lyon
Représentations de polynômes par des déterminants symétriques
En collaboration avec Erich L. Kaltofen, Pascal Koiran et Natacha Portier

Dans un papier influent de 1979, Leslie Valiant a prouvé l'universalité du déterminant : tout polynôme sur un corps K donné par une formule peut être représenté par le déterminant d'une matrice "de petite taille" dont les coefficients sont des variables et des éléments de K. Ce résultat a ensuite été étendu aux circuits faiblement asymétriques indépendamment par Toda et Malod. Dans ce travail, nous montrons que si la caractéristique de K est différente de 2, le déterminant de matrices symétriques est également universel. Le cas de la caractéristique 2 reste ouvert.
Dans l'exposé, nous rappellerons les constructions de Valiant, Toda et Malod, basées sur des constructions de graphes orientés, avant de présenter nos constructions, qui font appel à des graphes non orientés. Enfin, nous discuterons un peu le cas de la caractéristique 2.