Séminaires 2013 - 2014

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.

• Jeudi 10 juillet 2014 (à 14h30): André Bouchet (Le Mans) : Semis enchaînés et semis parallèles sur un wari ouvert
  
  Les wari sont des jeux traditionnels en Afrique et en Asie. On y joue avec des pions répartis dans des trous disposés selon un ordre circulaire. Un coup du jeu consiste à ramasser les pions contenus dans un trou pour les semer un par un dans les trous qui suivent. Nous nous intéressons à une version ouverte du wari où les trous sont disposés le long d'une courbe ouverte orientée de gauche à droite, chaque trou ayant un voisin à gauche et un voisin à droite. Nous étudions comment évolue la distribution des pions dans les trous lorsqu'une suite de semis enchaînés est appliquée. Nous étudions aussi des semis effectués en parallèle.
  
  
• Jeudi 19 juin 2014 (à 14h30): Jan Hladky (Warwick, Royaume-Uni) : An approximate version of the tree packing conjecture
  
  A family of graphs packs into a graph G if there exist pairwise edge-disjoint copies of its members in G. We prove a theorem about packing trees into a complete graph. The result implies asymptotic versions of the Tree Packing Conjecture of Gyárfás and of the Ringel Conjecture for the class of trees with bounded maximal degree. The core of the proof is a random process controlled by the nibbling method.
  
  This is a joint work with Julia Böttcher, Diana Piguet, and Anusch Taraz.
  
  
• Jeudi 15 mai 2014 (à 14h30): Christophe Crespelle (LIP, Lyon) : A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph With Regard to the Cartesian Product
  
  We design the first linear-time algorithm for computing the prime decomposition of a digraph G with regard to the cartesian product. A remarkable feature of our solution is that it computes the decomposition of G from the decomposition of its underlying undirected graph, for which there exists a linear-time algorithm. First, this allows our algorithm to remain conceptually very simple and in addition, it provides new insight into the connections between the directed and undirected versions of the cartesian product of graphs.
  
  Joint work with Thomas Lambert and Eric Thierry.
  
  
• Jeudi 27 mars 2014 (à 14h30): Eglantine Camby (Université Libre de Bruxelles, Belgique) : Connected dominating set in graphs without long paths and cycles
  
  In this talk, we investigate the ratio of the connected version of a problem to the original problem in graphs, called the Price of Connectivity (PoC). We study the PoC for the domination problem.
  
  Firstly, the ratio of the connected domination number, γc, and the domination number, γ, is strictly bounded from above by 3. It was shown by Zverovich that for every connected (P5,C5)-free graph, γc = γ. We investigate the interdependence of γ and γc in the class of (P_k,C_k)-free graphs, for k at least 6. We prove that for every connected (P6,C6)-free graph, γc is at most γ + 1, and there is a family of (P6,C6)-free graphs with arbitrarily large values of γ attaining this bound.
  Moreover, for every connected (P8,C8)-free graph, γc / γ is at most 2, and there is a family of (P7,C7)-free graphs with arbitrarily large values of γ attaining this bound.
  In the class of (P9,C9)-free graphs, the general bound γc / γ < 3 is asymptotically sharp.
  
  Secondly, we prove that the following decision problem is Theta_2^p-complete, for every fixed rational 1 < r < 3: Given a graph G, is γc(G) / γ(G) at most r? Loosely speaking, this means that deciding whether the ratio of γc(G) and γ(G) is bounded by some constant (apart from 1) is as hard as computing both γc(G) and γ(G) explicitly.
  
  This is joint work with Oliver Schaudt
  
  
• Jeudi 20 mars 2014 (à 14h30): Sylvia Boyd (Université d'Ottawa, Canada) : Using circulations for approximation algorithms for the minimum size 2-edge-connected spanning subgraph problem.
  
  In this paper we study the NP-hard problem of finding a minimum size 2-edge-connected spanning subgraph (henceforth 2EC) in cubic and subcubic multigraphs. We present a new 5/4-approximation algorithm for 2EC for subcubic bridgeless graphs, improving upon the current best approximation ratio of 5/4 + epsilon. Our algorithm involves an elegant but simple new method based on circulations which we feel has great potential to be more broadly applied. We also study the closely related integrality gap problem, i.e. the worst case ratio between the ILP for 2EC and its LP relaxation, both theoretically and computationally. We show this gap is at most 9/8 for all subcubic bridgeless graphs with up to 16 nodes. Moreover, we present a family of graphs that demonstrate the integrality gap is at least 8/7, even when restricted to subcubic bridgeless graphs. This represents an improvement over the previous best known bound of 9/8.
  
  Joint work with Yao Fu and Yu Sun (University of Ottawa).
  
  
• Jeudi 13 mars 2014 (à 14h30): Samuel Fiorini (Université Libre de Bruxelles, Belgique) : Exponential lower bounds for polytopes in combinatorial optimization
  
  Linear programming is a powerful and widely used tool for tackling problems throughout Computer science and Mathematics. Despite the importance of linear programming, both in practice and theory, we do not have a good understanding of what problems can be efficiently expressed as linear programs (LPs). I will lift part of the veil and explain how to prove that there exist problems, such as the traveling salesperson problem (TSP), that need exponential size LPs.
  More precisely, our result states that every polytope that projects to the TSP polytope is defined by an exponential number of linear constraints. This result solves a 20-year old problem posed by Yannakakis. It was discovered through a new connection that we made between one-way quantum communication protocols and semidefinite programming reformulations of LPs.
  In the talk, I will completely bypass the quantum aspects and give a complete proof that is both short and fully combinatorial. (The shortening is a recent result of Kaibel and Weltge.)
  
  This is is joint work with S. Massar (Brussels), S. Pokutta (Georgia Tech), H.R. Tiwary (Brussels), R. de Wolf (CWI).
  
  
• Jeudi 20 février 2014 (à 14h30): David Cattaneo (LIG, Grenoble) : Bornes et complexité de la domination impaire faible ou Comment allumer un maximum d'ampoules fragiles
  
  Nous considérons une variante du Sigma-game où les ampoules associées aux sommets du graphe sont fragiles : chaque ampoule a 3 états : éteinte, allumée ou HS. Jouer sur une ampoule la brise (HS) et change l'état allumée/éteinte de ses voisines encore en service. Au départ toutes les ampoules sont éteintes, l'objectif est d'allumer un maximum d'ampoules. Ce nombre maximum est appelé Kappa(G). De façon plus abstraite, il s'agit d'étudier des propriétés de domination impaire. L'étude d'une famille de protocoles de cryptographie quantique à base de graphes nous a amené à étudier cette variante du Sigma-game : Kappa(G) (resp. KappaQ(G) := max( Kappa(G); kappa(complémentaire de G)) ) est le seuil du protocole décrit par le graphe G quand le secret est classique (resp. quantique). En particulier, il est crucial pour l'étude et le développement de cette famille de protocoles d'obtenir des bornes sur ces seuils et d'étudier la complexité des problèmes de décision.
  
  
• Jeudi 13 février 2014 (à 14h30): Yohann Benchetrit (G-SCOP) : Propriété de décomposition entière du polytope des stables de certains graphes h-parfaits sans griffes
  
  Un sous-ensemble de sommets d'un graphe est stable si ses éléments sont deux-à-deux non-adjacents. Le polytope des stables S(G) d'un graphe G est l'enveloppe convexe des vecteurs caractéristiques des stables de G.
  Chvátal a démontré que les facettes non-triviales de S(G) sont données par des inéquations de cliques exactement lorsque G est parfait. Dans ce cas, le lemme de réplication de Lovász signifie que le nombre chromatique pondéré de G est identique à sa version fractionnaire.
  Un graphe G est h-parfait s'il suffit de rajouter les inéquations de cycles impairs à celles des cliques pour décrire S(G). Peut-on encore obtenir le nombre chromatique d'un graphe h-parfait à partir de son nombre chromatique fractionnaire ? Un exemple dû à Seymour et Laurent montre que la réponse est non en général, mais Kilakos et Marcotte ont prouvé que cela reste vrai dans la classe des graphes séries-parallèles.
  Je présenterai deux nouveaux exemples de classes de graphes h-parfaits sans griffes pour lesquelles le nombre chromatique pondéré s'obtient en arrondissant le nombre chromatique fractionnaire correspondant. Cela revient à dire que leur polytope des stables a la propriété de décomposition entière: pour tout entier naturel k, tout vecteur de kS(G) est la somme de k vecteurs caractéristiques de stables de G.
  Cela implique notamment l'existence d'un algorithme polynomial de coloration pondérée pour ces graphes (par les ellipsoïdes) ainsi qu'une nouvelle preuve d'un théorème de coloration de Bruhn et Stein.
  
  Travail effectué sous la supervision d'András Sebő.
  
  
• Jeudi 6 février 2014 (à 14h30): Matej Stehlik (G-SCOP) : Coloration de quadrangulations d'espaces projectifs
  
  Un graphe plongé sur une surface S de façon à ce que toutes les faces soient de taille 4 est appelé une quadrangulation de S. Notre point de départ est un joli théorème de Youngs de 1996, qui dit que toute quadrangulation G du plan projectif P^2 est soit bipartie, soit 4-chromatique.
  On va d'abord étendre la définition de quadrangulation à une dimension n quelconque, puis étendre la borne inférieure du théorème de Youngs comme suit : le nombre chromatique d'une quadrangulation G de P^n, l'espace projectif de dimension n, est soit égal à 2, soit supérieur ou égal à n+2. La preuve utilise des méthodes topologiques, en particulier le théorème de Borsuk-Ulam.
  Les quadrangulations de P^n sont intéressantes du point de vue de la propriété suivante : pour tout n il existe une quadrangulation G de P^(n-2) telle que tous les cycles impairs sont de longueur au moins n et le nombre chromatique de G est supérieur ou égal à n. Autrement dit, le graphe G est localement biparti, mais son nombre chromatique est grand. En général ce type de graphe est très rare, et on connait très peu de constructions de graphes avec cette propriété. Deux familles classiques avec ces propriétés sont les graphes de Mycielski et les graphes de Kneser. Je vais montrer que les graphes de Mycielski sont des quadrangulations des espaces projectifs, et qu'il existe des quadrangulations de P^n qui sont homomorphes aux graphes de Schrijver (des sous-graphes spéciaux des graphes de Kneser). Cela fournit une nouvelle démonstration du théorème de Lovasz-Kneser.
  
  Travail en commun avec Tomas Kaiser.
  
  
• Jeudi 28 novembre 2013 (à 14h30): Fatiha Bendali-Mailfert (Clermont-Ferrand) : Problème de l'indépendant faiblement connexe
  
  Nous présentons dans cet exposé la structure d'Indépendant Faiblement Connexe (IFC). Etant donné un graphe connexe G=(V,E), un indépendant S de V est faiblement connexe si le graphe partiel formé par les arêtes ayant exactement une extrémité dans S est connexe.
  Un IFC de G est aussi un ensemble dominant de G. Cette structure combinatoire a été définie comme une alternative aux dominants faiblement connexes. Rechercher l'IFC de cardinalité minimum est un problème NP-difficile. Nous donnons des bornes sur ce cardinal ainsi que quelques classes de graphes où ce problème est facile.
  Généralement, les algorithmes triviaux d'énumération dans un graphe à n sommets fournissent toutes les solutions avec une complexité de O*(2^n). Grâce à certaines règles d'élagage appliquées dans un algorithme d'énumération implicite, nous obtenons tous les IFC d'un graphe connexe en O*(1.4655^n). Cet algorithme est testé sur des cas issus de la TSPLIB et sur des graphes générés aléatoirement pour plus de 100 sommets.
  
  Travail en commun avec M. Mameri Djelloul.
  
  
• Jeudi 7 novembre 2013 (à 14h30): Kaz Makino (RIMS, Kyoto University) : The complexity issues on stochastic games
  
  Stochastic games were introduced in 1953 by Shapley for the discounted case, and extended to the undiscounted case in 1957 by Gillette. Each such game is a dynamic game with probabilistic transitions played by two players on a finite set of states. The game is played in the infinite sequence of rounds. In the round, the game is in some state. The players choose actions. Then they receive payoffs and the game moves to a new random state, where the payoffs and the transition probability depend on the previous state and the actions chosen by the players. The procedure is repeated at the new state.
  Stochastic games generalize parity games, cyclic games, simple stochastic games, and BWR games, which all belong to NP and coNP, but are not known to be solved in polynomial time.
  
  In this talk, I briefly survey the algorithmic issues on these games, as well as the properties on the optimal strategies for them. I also discuss recent works obtained with Endre Boros, Khaled Elbassioni, and Vladimir Gurvich.
  
  
• Jeudi 10 octobre 2013 (à 14h30): Irena Penev (LIP, ENS de Lyon) : A Composition Theorem for {P5,P5c}-Free Graphs
  
  If HH is a family of graphs, a graph G is said to be HH-free provided that G does not contain (an isomorphic copy of) any graph in HH as an induced subgraph. P5 is a four-edge path, and P5c is its complement. In this talk, I will present some new results on the structure of {P5,P5c}-free graphs.
  
  A graph G is said to be prime if it cannot be obtained by substitution from smaller graphs (equivalently: if it does not contain a proper homogeneous set). Fouquet proved that every prime {P5,P5c}-free graph is either a cycle of length five (denoted by C5), or a {P5,P5c,C5}-free graph. Since P5, P5c, and C5 are all prime graphs, Fouquet's theorem reduces the problem of describing the structure of {P5,P5c}-free graphs to the problem of describing the structure of {P5,P5c,C5}-free graphs.
  
  In this talk, I will first present a decomposition theorem for {P5,P5c,C5}-free graphs, which states that if G is a prime {P5,P5c,C5}-free graph, then either G is a split graph (i.e. a graph whose vertex-set can be partitioned into a clique and a stable set), or G or its complement admits a "split graph divide", a new kind of decomposition, which I will describe in the talk. I will then explain how this new decompositon can be turned into an operation, called "split graph unification" which preserves the property of being H-free for each graph H in {P5,P5c,C5}. This yields a composition theorem for {P5,P5c,C5}-free graphs, which states that a graph G is {P5,P5c,C5}-free if and only if it can be obtained from split graphs by repeatedly applying substitution, complementation, and split graph unification. Together with Fouquet's result, this implies a composition theorem for {P5,P5c}-free graphs, which states that a graph G is {P5,P5c}-free if and only if it can be obtained from split graphs and cycles of length five by repeatedly applying substitution, complementation, and split graph unification.
  
  Even though all operations used in our composition theorem for {P5,P5c}-free graphs are class-preserving, this theorem is not quite a structure theorem for reasons that I will discuss in the talk. Thus, more work is needed in order to fully understand the structure of {P5,P5c}-free graphs, but this new composition theorem might well represent a good starting point.
  
  This is joint work with Maria Chudnovsky and Peter Maceli.
  
  
• Jeudi 26 septembre 2013 (à 14h30): Louis Esperet (G-SCOP, Grenoble) : Coloration des graphes planaires avec 3 couleurs et sans grande composante monochromatique
  
  On montre qu'on peut colorier tout graphe planaire de degré maximum borné avec 3 couleurs, de manière à ce que dans chaque classe de couleurs, les composantes connexes soient de taille bornée.
  C'est optimal (on ne peut ni descendre à 2 couleurs, ni s'affranchir de la condition sur le degré maximum) et cela répond à une question posée par Kleinberg, Motwani, Raghavan, et Venkatasubramanian en 1997. Le résultat s'étend aux graphes de genre borné.
  
  Travail en commun avec G. Joret.
  
  
• Jeudi 19 septembre 2013 (à 14h30): David Défossez (EDF - R&D) : Optimisation du placement des arrêts des tranches nucléaires
  
  Le parc de production électrique français possède la particularité d'être composé en grande partie d'énergie nucléaire. Cette énergie étant moins chère que les moyens de productions thermiques classiques, l'optimisation économique du coût de production consiste à rendre les tranches nucléaires autant disponibles que possible lors des périodes de forte consommation.
  Celles-ci doivent être arrêtées régulièrement pour effectuer leur rechargement en combustible ainsi que différentes opérations de maintenance. Les ressources pour ces opérations de maintenance étant partagées par l'ensemble du parc nucléaire il existe de nombreuses contraintes liant entre elles les dates des différents arrêts de tranches.
  Il en résulte un problème d'optimisation combinatoire complexe qui fut l'objet du challenge ROADEF/EURO en 2010 auquel avaient participé de nombreuses équipes universitaires et/ou industrielles.
  Lors de cet exposé nous verrons comment le problème est traité en opérationnel : processus de décision, méthodes d'optimisation et leurs évolutions, et perspectives de recherche.