Séminaires 2011 - 2012

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 Andras Sebö, n'hésitez pas à les contacter.

• Jeudi 19 juillet 2012 (à 15h30): Ross Kang (CWI, Amsterdam) : Asymptotics of the Erdos-Hajnal conjecture
  
  The aim of the talk is to survey various approaches to a notorious conjecture of Erdös and Hajnal, which is concerned with understanding how the exclusion from G of a fixed graph H as an induced subgraph affects the size of a largest homogenous set (clique or stable set) in G.
  
  This conjecture is related to both extremal and structural graph theory, as well as random graphs. Some of the talk is devoted to describing recent asymptotic formulations, proved using Szemerédi regularity (one of which is joint work with McDiarmid, Reed and Scott).
  
  
• Jeudi 12 juillet 2012 (à 14h30): Giuseppe Mazzuoccolo (G-SCOP) : How many matchings of a given size are necessary to cover the edge-set of a graph?
  
  Let m be a positive integer and let G be a graph. An [m]-covering of G is a set M = {M1,...,Mk} of matchings of size m of G covering E(G), where E(G) denotes the edge-set of G. We will call excessive m-index of G, denoted by chi[m](G), the smallest integer k for which G admits an [m]-covering (set chi[m](G) to be infinite if such a covering does not exist).
  In the first part of this talk we consider the case in which G is cubic and m is the size of a perfect matching of G and we show how this problem is strictly related to an outstanding conjecture of Berge and Fulkerson. More precisely, it is proved that the Berge-Fulkerson conjecture is equivalent to the assertion that each bridgeless cubic graph of order 2n has excessive [n]-index at most five.
  In the latter part we deal about the case in which m is small. The case m = 1 is trivial (chi[1](G) = |E(G)|) and the case m = 2 is an easy exer- cise. Cariolaro and Fu have recently given a general formula to compute the excessive [3]-index of all graphs. Here we address the case m = 4 and we propose a formula for all trees. Furthermore, we conjecture a generalization of this formula to compute chi[4](G) for each graph G.
  
  
• Jeudi 5 juillet 2012 (à 14h30): Stéphan Thomassé (LIP, ENS Lyon) : Graph coloring, communication complexity, and the stubborn problem
  
  In this talk, I will show that the polynomial Alon-Saks-Seymour conjecture (the edge-disjoint union of k complete bipartite graphs has chromatic number O(k^c), for some universal constant c), the polynomial clique-stable separation conjecture (there exists a c such that for any graph G on n vertices, there exists O(n^c) vertex bipartitions of G such that for every disjoint stable set S and clique K, one of the bipartitions separates S from K) and the polynomial stubborn 2-list cover conjecture are equivalent. One of the implications linking the two first problems was already proved by Alon and Haviv.
  
  (joint work with Nicolas Bousquet and Aurélie Lagoutte)
  
  
• Jeudi 7 juin 2012 (à 14h30): Kenjiro Takazawa (G-SCOP, Grenoble) : 2-matchings without short cycles
  
  In an undirected graph, a 2-matching is called k-restricted if it contains no cycle of length k or less. Given an undirected graph G=(V,E), the k-restricted 2-matching problem is to find a k-restricted 2-matching of maximum number of edges. This problem is exactly the classical 2-matching problem if k=2, and it contains the Hamiltonian cycle problem if k=|V|/2. For 2 < k < |V|/2, some cases are proven to be polynomially solvable or NP-hard, and some cases are left open. For instance, a combinatorial algorithm is given by Hartvigsen (1984) for the case k=3, while the problem is NP-hard when k > 4. The complexity for the case k=4 is not known.
  
  The k-restricted 2-matching problem has been studied actively during the last decade. In this talk, we give a survey on the recent progress in the k-restricted 2-matching problem, including the results of the speaker and several special cases which are still open. We also discuss the weighted k-restricted 2-matching problem, and the relation between k-restricted 2-matchings and jump systems.
  
  
• Jeudi 10 mai 2012 (à 14h30): Stefan Hougardy (Université de Bonn, Allemagne) : Rectangle Packing and VLSI Placement
  
  The rectangle packing problem is to decide whether a given set of axis parallel rectangles can be placed without overlap into some larger rectangle. This problem is well known to be NP-hard. Special cases of this problem appear in the macro placement phase of VLSI-chips. Therefore one is interested in efficient algorithms to solve this problem. We will show that in some cases polynomial time algorithms are possible to exactly solve this problem. We also discuss extensions of this problem and present recent progress on an old rectangle packing problem due to Leo Moser from 1966.
  
  
• Jeudi 3 mai 2012 (à 14h30): Matej Stehlik (G-SCOP, Grenoble) : Comment rendre biparti un ballon de foot?
  
  Déterminer le nombre minimum d'arêtes qu'il faut enlever d'un graphe afin de le rendre biparti est un problème classique, étudié par de nombreux chercheurs. Nous considérerons ce problème pour la classe des graphes de fullerène : ce sont des graphes plans cubiques dont les faces sont toutes des pentagones ou des hexagones ; le ballon de football est un joli exemple. Doslic et Vukicevic ont conjecturé que tout graphe de fullerène à n sommets peut être rendu biparti en enlevant au plus sqrt(12n/5) arêtes. Je vais montrer comment on peut prouver cette conjecture en utilisant la théorie des T-joints et T-coupes. On peut déduire quatre autres conjectures sur les graphes de fullerènes, y compris une borne inférieure exacte pour le nombre d'indépendance des graphes de fullerènes.
  
  Travail en collaboration avec Luerbio Faria et Sulamita Klein.
  
  
• Jeudi 19 avril 2012 (à 14h30): Zhentao Li (LIP, ENS Lyon) : The Hardness of Simultaneous Clustering Problems
  
  We study the simultaneous cluster problem where we look for induced subgraphs which are simultaneously "nice" in a set of graphs. These graphs are defined over the same set of vertices, but with different sets of edges among them. This paradigm is very relevant in the biological sciences. While there has been a vast amount of heuristic work on different variants of this problem, little is known on the theoretical side. We present theoretical results that explain why such heuristics typically come without quantitative guarantees. We give hardness (inapproximability) results for different definitions of "nice", such as high density or connectivity.
  
  This is joint work with Manikandan Narayanan and Adrian Vetta
  
  
• Jeudi 12 avril 2012 (à 14h30): Pierre Aboulker (LIAFA, Paris) : Graphs with no 4-wheels
  
  A 4-wheel is a graph formed by a cycle C and a vertex not in C that has at least four neighbors in C. We prove that a graph G that does not contain a 4-wheel as a subgraph is 4-colorable and we describe some structural properties of such a graph.
  
  
• Jeudi 29 mars 2012 (à 15h30): Jens Vygen (Université de Bonn, Allemange) : Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
  
  We prove new results for approximating the graphic TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees.
  For the graphic TSP itself, we improve the approximation ratio to 7/5. For a generalization, the connected-T-join problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the graphic s-t-path-TSP as a special case. Our improved approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3.
  
  The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP relaxations) that we use to deduce the approximation ratios.
  
  This is joint work with Andras Sebo.
  
  
• Jeudi 29 mars 2012 (à 14h): Maurice Queyranne (Sauder, UBC, Canada) : Modeling convex subsets of points
  
  A subset S of a given set of points in a vector space is convex if every given point in the convex hull of points in S must also be in S.
  We are interested in modelling such discrete convexity restrictions which arise, usually in a low-dimensional space and subject to additional constraints, in many applications (e.g., mining, forestry, location, data mining, political districting, police quadrant design).
  This is well understood in one dimension, where optimization can be solved in time that is linear (in the number of given points); a complete (but exponential-size) polyhedral description in the natural variables and a linear-time separation algorithm are known, as well as a linear-sized ideal extended formulation. On the other hand the optimization problem (find a maximum weight convex subset of given points with weights of arbitrary signs) is NP-hard in dimensions three and higher, and inapproximable when the dimension is part of the input.
  In the two-dimensional plane, the optimization problem is solved in polynomial (cubic) time by dynamic programming [Bautista-Santiago et al., 2011] and, thanks to Carathéodory's Theorem, convexity can be enforced by a polynomial (quartic) number of linear inequalities in the natural binary variables. We seek more compact or tighter formulations and faster separation algorithms in the natural variables, and extended formulations, that can be used as part of more complex optimization models involving convex subsets of given points.
  
  This talk will report on past and current work with numerous co-authors.
  
  
• Jeudi 22 mars 2012 (à 14h30): Dieter Kratsch (Université de Metz) : Exact Exponential Algorithms
  
  Today most computer scientists believe that NP-hard problems cannot be solved by polynomial time algorithms. From the polynomial-time perspective all NP-complete problems are equivalent but their exponential-time properties vary widely. Why do some NP-hard problems seem to be easier than others? What are the algorithmic techniques for solving hard problems significantly faster than the exhaustive brute-force search, trying all possible solutions? The algorithms addressing these questions are known as exact exponential algorithms. The history of exact exponential algorithms for NP-hard problems dates back to the 1960s. Two classical examples are Bellman, Held and Karp's dynamic programming algorithm for the Traveling Salesman problem and Ryser's inclusion-exclusion formula for the permanent. The design and analysis of exact algorithms leads to a better understanding of hard problems and initiates interesting new combinatorial and algorithmic challenges. The last decade has witnessed a rapid development of the area, with many new algorithmic techniques discovered. This has transformed exact algorithms into a very active research field. This talk provides an introduction to the area and explains some of the fundamental algorithmic techniques.
  
  
• Jeudi 8 mars 2012 (à 14h30): Anthony Perez (LIFO, Orléans) : Complexité paramétrée, algorithmes de noyau et Conflict Packing
  
  La complexité paramétrée permet de mesurer la difficulté d'un problème de décision en fonction de la taille de l'instance et d'un paramètre k associé au problème. Un problème paramétré est dit FPT lorsqu'il peut être résolu en temps f(k).poly(n), où f() est une fonction calculable quelconque. De manière équivalente, un problème P est FPT lorsqu'il admet un algorithme de noyau, i.e. un algorithme polynomial qui, étant donnée une instance (I,k) de P, retourne une instance équivalente (I',k') de P telle que |I'| <= g(k) et k' <= k.
  Dans cet exposé, je présenterai un algorithme paramétré (simple) ainsi que différents algorithmes de noyau pour le problème Vertex Cover. Par la suite, je présenterai la notion de Conflict Packing, introduite avec Christophe Paul et Stéphan Thomassé et permettant d'obtenir des algorithmes de noyau polynomial pour de nombreux problèmes de modification de relations. Je décrirai en particulier comment cette méthode peut être appliquée au problème Feedback Arc Set in Tournaments pour obtenir un noyau contenant au plus 4k sommets. Pour conclure, j'expliquerai comment les idées présentées pour FAST peuvent s'appliquer à d'autres problèmes.
  
  
• Jeudi 23 février 2012 (à 14h30): Viet Hang Nguyen (G-SCOP) : Rigidity of direction-length graphs
  
  We study the problem of rigidity of direction-length graphs, i.e., the uniqueness of realizations in Eulidean space of a graph whose edges represent the direction or distance constraints between vertices. This problem has applications in network localization, CAD (Computer-Aided Design)...
  
  Aiming to give a constructive characterization of rigid direction-length graphs, we introduce some operations that preserve the rigidity of direction-length frameworks. Using these operations, we show that if a graph is the union of a spanning tree with only length edges and a spanning tree with only direction edges then the associated frameworks are, in general, (locally) rigid in any dimension.
  
  In dimension 2, we give a min-max formular for the rank of direction-length graphs.
  
  
• Jeudi 16 février 2012 (à 14h30): Nicolas Trotignon (LIP, ENS Lyon) : Détection des "nets"
  
  Un "net" dans un graphe est un cycle muni de trois arêtes pendantes, s'attachant sur le cycle en trois sommets distincts. Donc, un "net" est connexe, possède trois sommets de degré 1, trois sommets de degré 3, et tous les autres sommets (s'il y en a) sont de degré 2. Nous présentons un algorithme en temps polynomial qui décide si un graphe possède un "net" en tant que sous-graphe induit. Cet algorithme combine deux techniques classiques dans le domaine de la détection de sous-graphe : le nettoyage, et la détection par plus courts chemins. La complexité est O(n^16).
  
  Soit H un graphe fixé. Considérons le problème P(H) : décider si un graphe G contient une subdivision de H en tant que sous-graphe induit. Ce problème est polynomial pour quelques rares graphes H, NP-complet pour beaucoup d'autres. Notre algorithme résout P(H) en temps polynomial quand H est le "net" à six sommets. A notre connaissance, on ne connaît aucun graphe H de degré maximum au plus 3 tel que P(H) soit NP-complet, et la complexité de P(H) était inconnue avant ce travail pour tous les graphes H de degré maximum au plus 3 contenant un cycle.
  
  Travail en commun avec Maria Chudnovsky et Paul Seymour.
  
  
• Jeudi 9 février 2012 (à 14h30): Frantisek Kardos (INRIA Sophia-Antipolis) : On computing the minimum 3-path vertex cover and dissociation number of graphs
  
  The dissociation number of a graph G is the number of vertices in a maximum size induced subgraph of G with vertex degree at most 1. A k-path vertex cover of a graph G is a subset S of vertices of G such that every path of order k in G contains at least one vertex from S. The minimum 3-path vertex cover is a dual problem to the dissociation number. Both exact and approximation algorithms for these problems will be presented.
  
  
• Vendredi 20 janvier 2012 (à 11h): Benjamin Lévêque (LIRMM, Montpellier) : Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representation
  
  A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to toroidal maps with application to graph drawing. We prove the existence of these Schnyder woods for toroidal triangulations. We show that Schnyder woods can be used to embed the universal cover of a toroidal map on an infinite and periodic orthogonal surface. Finally we use this embeding to obtain a straight line drawing of any toroidal map in a polynomial size grid.
  
  
• Mardi 17 janvier 2012 (à 14h30): Neil Olver (MIT, Boston) : Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
  
  Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. This changed when Byrka, Grandoni, Rothvoss and Sanità demonstrated a ln(4) approximation algorithm based on a component-based relaxation (one of a family of "hypergraphic" relaxations). Surprisingly, even though their approach is LP based, they do not obtain a matching bound on the integrality gap, showing only a weaker 1.55 bound by other methods.
  
  We show that indeed the integrality gap is bounded by ln(4). In the process, we obtain a much better structural understanding of these hypergraphic LPs, as well as more efficient and simpler algorithms. Techniques from the theory of matroids and submodular functions take a crucial role.
  
  (Joint work with Michel Goemans, Thomas Rothvoss and Rico Zenklusen.)
  
  
• Jeudi 8 décembre 2011 (à 14h30): Olivier Durand de Gevigney (G-SCOP) : Packing de sous-graphes rigides et d'arbres couvrants
  
  Nous montrons que tout graphe simple (6k+2l,2k)-connexe contient k sous-graphes couvrants et l arbres couvrants arête-disjoints. Ce résultat unifie deux extensions du résultat classique de Lovász et Yemini qui stipule que les graphes 6-connexes sont rigides. Il permet aussi d'améliorer deux bornes sur la connexité des graphes ayant des propriétés particulières : (1) tout graphe 8-connexe contient un arbre couvrant et un sous-graphe couvrant 2-connexe arête-disjoints; (2) tout graphe 14-connexe admet une orientation 2-sommet-connexe.
  
  Travail en commun avec Joseph Cheriyan et Zoltan Szigeti.
  
  
• Jeudi 1er décembre 2011 (à 14h30): Christophe-Marie Duquesne (G-SCOP) : Intégration du déploiement de la flotte et du service aux passagers dans la gestion de planification pour compagnie aérienne.
  
  L'affectation de flotte est l'une des étapes clés du processus de planification des compagnies aériennes. Si de nombreuses études ont été réalisées pour améliorer celle-ci, aujourd'hui seuls deux modèles sont effectivement appliqués dans l'industrie. Le premier, très basique, a pour mérites d'être facile à comprendre et rapide à résoudre. Le second, plus élaboré, prend théoriquement de meilleures décisions, mais comporte nettement plus de variables et nécessite de connaître précisément les quantités de voyageurs désirant voyager sur chaque itinéraire du réseau. Nous nous proposons de nuancer cette dernière hypothèse, trop radicale pour être vraie mais suffisament importante pour ne pas être complètement retirée. Le modèle que nous proposons permet de prendre en entrée les demandes des passagers comme une entrée non parfaitement déterminée, en essayant de tirer parti de la loi des grands nombres. Nous montrons que sous un certain nombre d'hypothèses, notre modèle donne de meilleurs résultats que ceux de la littérature.
  
  
• Jeudi 24 novembre 2011 (à 14h30): Gautier Stauffer (Université Bordeaux 1) : A simple and fast 2-approximation algorithm for the one-warehouse multi-retailer problem
  
  We consider two important deterministic inventory control problems: the One-Warehouse Multi-Retailer (OWMR) problem and its special case the Joint Replenishment Problem (JRP). amely we want to optimize the distribution of a single item over a network composed of one warehouse and N different retailers over a discrete finite planning horizon of T periods. Each retailer is facing deterministic demands that have to be fulfilled on time by ordering those units from the warehouse, which in turn have to be ordered from an external supplier of infinite capacity. The objective of the OWMR problem is to find a planning for the orders at each location (i.e. period and quantity) that minimizes the sum of the fixed ordering costs and holding costs in the system. The cost of ordering is fixed, independent of the number of products, while a per-unit holding cost is paid at each location to keep an item in stock. This problem is NP-hard but efficient 1.8- and 2-approximation algorithms have been proposed in the literature. The corresponding algorithms are based on sophisticated LP techniques (randomized rounding and primal dual). In this talk we present a simple 2-approximation algorithm that is purely combinatorial and that can be implemented to run in linear time. While we do not match the best known 1.8-approximation guarantee, we believe however that the simplicity of the method and its computational complexity make it both a valuable theoretical approach and a practical tool.
  
  This is joint work with G. Massonnet, C. Rapine, and J.-P. Gayon.
  
  
• Jeudi 27 octobre 2011 (à 14h30): Jens Vygen (Université de Bonn, Allemange) : Faster resource sharing and global routing in theory and practice
  
  We consider the (block-angular) min-max resource sharing problem, which generalizes well-known combinatorial optimization problems such as multicommodity flows and fractional packing. We present a simple combinatorial fully polynomial approximation scheme which is both faster and more general than all previous algorithms.
  
  Our work was motivated mainly by global routing in chip design. Here the feasible solutions are mixed-integer sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. The result is a packing of Steiner trees subject to edge capacities and various other (also nonlinear) constraints. We implemented the algorithm and present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. We solve them nearly optimally in less than two hours.
  
  This is joint work with Dirk Müller and Klaus Radke.
  
  
• Vendredi 7 octobre 2011 (à 11h): Dieter Rautenbach (Université d'Ulm, Allemange) : The Convexity Space induced by Paths of Order Three
  
  Every set S of paths of a graph G defines a natural convexity space where some set C of vertices of G is considered convex exactly if for every path P in S that starts and ends in C, the set C contains all vertices of P. The well-known geodetic convexity and monophonic convexity for example are obtained in this way considering either the set of all shortest paths or the set of all induced paths of G. In this talk we consider as S the set of all paths of G of order 3, which leads to a convexity notion that was considered in connection with rumour/desease spreading processes in graphs. We survey several of our recent results concerning the classical parameters associated with convexity spaces, namely the hull number, the Caratheodory number and the Radon number.
  
  The presented material is based on three papers and joint work with several coauthors.
  
  
• Jeudi 29 septembre 2011 (à 14h30): Gabor Bacso (MTA SZTAKI, Budapest, Hongrie) : Résultats anciens et applications nouvelles sur les graphes sans P5
  
  Nous montrons des résultats sur les graphes sans P5. Quelques résultats sont anciens, mais récemment des applications notables ont été obtenues. Elles sont reliés au problème de stabilité pour les graphes sans P5.
  
  
• Jeudi 22 septembre 2011 (à 14h): Simone Dantas et Diana Sasaki (Univ. Federal Fluminense, Rio de Janeiro, Brésil) : The hunting of a non 4-total colorable nontrivial snark
  
  Snarks are cubic bridgeless graphs of chromatic index 4. In 2003, Cavicchioli et al. proved that all nontrivial snarks with less than 30 vertices have total chromatic number 4, and proposed the problem of finding, if one exists, the smallest nontrivial snark which is not 4-total colorable.
  
  In this talk, we study operations for constructing snarks, obtaining properties of 4-total colorings that help the construction of 4-total colorings of several infinite snark families. Finally, we show trivial snarks of total chromatic number 5.
  
  
• Lundi 29 août 2011 (à 14h30): Michael Tarsi (Université de Tel-Aviv, Israel) : Fano flows and short cycle covers of graphs
  
  Pas de résumé, il fallait être là!
  
  
• Lundi 29 août 2011 (à 11h): Nati Linial (Hebrew University of Jerusalem, Israel) : What are high-dimensional permutations? How many are there?
  
  Pas de résumé, il fallait être là!