Séminaires 2010 - 2011

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

• Lundi 18 juillet 2011 (à 10h30): Joseph Cheriyan (Université de Waterloo, Canada) : On orienting graphs for connectivity
  
  Nash-Williams (1960) proved some remarkable results on orientations of (undirected) graphs that "preserve" the edge connectivity; in more detail, there is a way to replace each undirected edge by one directed edge such that the resulting directed graph has half the edge connectivity of the original undirected graph. Over the years, analogous results have been conjectured for orientations that "preserve" node connectivity, or element connectivity, or the edge connectivity of hypergraphs, respectively. These conjectures appear to be difficult and profound. The talk will survey some of the previous results and conjectures, prove some special cases of the conjectures, and explore some avenues for proving "loose" versions of the conjectures
  
  
• Mardi 21 juin 2011 (à 14h30): Guyslain Naves (Université McGill, Montréal, Canada) : Chemins disjoints avec congestion dans les graphes à mineur exclu
  
  Nous étudions le problème de trouver un nombre maximum de chemins disjoints dans des classes de graphes fermées par mineur. En général, ce problème est très difficile à approximer, même dans des classes très simple comme les graphes planaires, avec des ratios d'approximations en Omega(n). Pour contourner cette difficulté, plusieurs travaux autorisent l'utilisation de congestion: sous congestion c, on autorise c chemins à utiliser la même arête. Ainsi, Chekuri et Shepherd ont pu trouver un algorithme avec ratio d'approximation constant et congestion 2, dans le cas des graphes planaires. Nous souhaitons généraliser ce résultat, et nous prouvons que pour les graphes à largeur d'arbre bornée, et pour les graphes plongeables dans une surface fixée, il existe des algorithmes avec ratio et congestion constants. Ces deux types de classes de graphes étant fermées par mineur, nous conjecturons que toute classe de graphes ayant un mineur exclu admet de tels algorithmes.
  
  Travail en commun avec Chandra Chekuri et Bruce Shepherd.
  
  
• Jeudi 9 juin 2011 (à 14h30): Andras Gyarfas (Académie des Sciences, Hongrie) : Covering many vertices by monochromatic pieces
  
  The typical problem in Ramsey theory is to find the order of the largest monochromatic member of a family F (for example matchings, paths, cycles, connected subgraphs) that must be present in any edge t-coloring of a complete graph K_n. Another area is to find the minimum number of monochromatic members of F that partition (or cover) the vertex set of every edge t-colored complete graph.
  
  Here I address the problem that connects these areas: for fixed s\le t at least how many vertices can be covered by no more than s monochromatic members of F in every edge t-coloring of K_n?
  
  
• Mercredi 1er juin 2011 (à 14h45): Nicolas Trotignon (LIP, Lyon) : Decomposition theorems for classes of graphs defined by constraints on connectivity
  
  A graph is minimallly 2-connected if it is 2-connected and if the removal of any edge yields a graph that is not 2-connected. A graph is critical ly 2- connected if it is 2-connected and if the removal of any vertex yield a graph that is not 2-connected. Minimally and critically 2-connected graphs were studied in the 1960s. The goal of this talk is to present decomposition theorems related to these classes. Each of these theorems will have the following form: any graph in some class is either basic (i.e. has a very simple structure) or is decomposable, (i.e. can be cut into pieces in some useful way). Applications will be presented: reproving well known results, recognitions algorithms, vertex- and edge-coloring problems.
  
  
• Mercredi 1er juin 2011 (à 14h): Raphael Machado (Institut National de Métrologie, Normalisation et Qualité Industrielle, Brésil) : Edge-colouring and total-colouring of unichord-free graphs
  
  A unichord is an edge that is the unique chord of a cycle in the graph. The class of unichord-free graphs was recently studied by Trotignon and Vuskovic, who proved for these graphs strong structure results and used these results to solve the recognition and vertex-colouring problems (among other problems). The purpose of the work is to investigate whether such structure results could yield polynomial-time edge-colouring and total-colouring algorithms. We prove that both edge-colouring and total-colouring are NP-complete problems when restricted to unichord-free, but we determine subclasses where those problems are polynomial:
  - unichord-free that do not have a square are optimaly total-colourable in polynomial-time;
  - unichord-free that do not have a square and have maximum degree different of 4 are optimaly edge-colourable in polynomial-time;
  - graphs whose all cycles are induced are edge-colourable and total-colourable in polynomial time.
  
  This is a joint work with Celina de Figueiredo, Nicolas Trotignon and Kristina Vuskovic.
  
  
• Mardi 31 mai 2011 (à 14h30): Antoine Deza (Université McMaster, Ontario, Canada) : More Colourful Simplices
  
  A point p \in R^d has simplicial depth q relative to a set S if it is contained in q closed simplices generated by d+1 sets of S. More generally, we consider colourful simplicial depth, where the single set S is replaced by d+1 sets, or colours, S_1,...,S_{d+1}, and the colourful simplices containing p are generated by taking one point from each set. Assuming that the convex hulls of the S_i's contain p in their interior, Barany's colourful Carathéodory Theorem (1982) shows that p must be contained in some colourful simplex. We are interested in determining the minimum number of colourful simplices that can contain p for sets satisfying these conditions. That is, we would like to determine mu(d), the minimum number of colourful simplices drawn from S_1,..., S_{d+1} that contain p \in R^d given that p \in int(conv(S_i)) for each i. Without loss of generality, we assume that the points in bigcup_i S_i \cup p are in general position. The quantity mu(d) was investigated in Deza et al (2006), where it is shown that 2d \leq mu(d) \leq d^2+1, that mu(d) is even for odd d, and that mu(2)=5. This paper also conjectures that mu(d)= d^2+1. Subsequently, Barany and Matousek (2007) verified the conjecture for d=3 and provided a quadratic lower bound for mu(d), while Stephen and Thomas (2008) independently provided a stronger quadratic lower bound of mu(d). We further strengthen the previously known lower bounds for mu(d).
  
  Joint work with Tamon Stephen (Simon Fraser) and Feng Xie (McMaster).
  
  
• Jeudi 12 mai 2011 (à 14h30): François Margot (Carnegie Mellon University, USA) : Intersection Cuts with Infinite Split Rank
  
  We consider mixed integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a bounded convex set P is finite if and only if the integer points on the boundary of P satisfy a certain ''2-hyperplane property''. The Dey-Louveaux characterization is a consequence of this more general result.
  
  Joint work with A. Basu and G. Cornuejols
  
  
• Jeudi 21 avril 2011 (à 14h30): Marwane Bouznif (G-SCOP) : Algorithmes pour les fasciagraphes et rotagraphes
  
  Un fasciagraphe de taille n consiste en une séquence de n copies d'un même graphe, chaque copie étant liée à la suivante de la même manière. Dans un rotagraphe, la dernière copie est aussi reliée à la première.
  
  Nous nous sommes intéressés à la caractérisation de problèmes d'optimisation pour lesquels cette structure répétitive peut être exploitée de manière à obtenir des algorithmes plus performants que dans le cas de graphes quelconques.
  
  Nous avons ainsi déterminé une classe C de problèmes ayant la propriété suivante : il existe un algorithme générique qui, pour un problème P dans C et un motif répété M, construit dans un temps qui ne dépend que de P et M, un vecteur tau(M) à partir duquel on peut calculer simplement, pour tout n, la valeur d'une solution optimale de P pour le rotagraphe de motif M et de taille n. Ces résultats généralisent ceux déjà obtenus pour certains cas particuliers (dominant minimum et stable maximum : Zerovnik 1996 et 1999, Livingston et Stout 1994...).
  
  Nous décrirons la classe et l'algorithme, puis nous décrirons comment celui-ci nous a permis de montrer que la densité minimum d'un code identifiant dans une bande infinie de hauteur 3 est de 7/18, alors que jusqu'à présent la meilleure borne connue était égale à 2/5.
  
  
• Jeudi 14 avril 2011 (à 14h30): Gwenaël Joret (Université Libre de Bruxelles) : Sorting under Partial Information (without the Ellipsoid Algorithm)
  
  We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. In this talk, we describe a simple and efficient algorithm for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithm differs in essential ways from theirs: Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed in a restricted class of graphs, permitting the use of a simpler algorithm. Furthermore, we compute or approximate the entropy at most twice, instead of doing it at each iteration.
  
  Joint work with J. Cardinal, S. Fiorini, R. M. Jungers, and J. I. Munro
  
  
• Jeudi 7 avril 2011 (à 14h30): Louis Esperet (G-SCOP) : Un nombre exponentiel de 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.
  
  (travail en commun avec F. Kardos, A. King, D. Kral, et S. Norine)
  
  
• Jeudi 31 mars 2011 (à 14h30): Grégory Morel (G-SCOP) : Algorithmes linéaires pour les graphes sans P₅ 3-coloriables
  
  La classe des graphes sans P₅ est la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle la complexité du problème du stable maximum est inconnue. Des algorithmes polynomiaux existent pour de nombreuses sous-classes (graphes (P₅, chaise)-libres, graphes (P₅, maison)-libres, etc.). Nous nous intéressons dans cet exposé aux graphes sans P₅ 3-colorables ; en particulier, nous montrons qu'il est possible de résoudre les problèmes du stable maximum et de la coloration en temps linéaire dans cette classe de graphes. Nous caractérisons également ces graphes en donnant une liste de douze sous-graphes induits minimaux interdits, et montrons qu'il est possible de décider si un graphe appartient à cette classe en temps linéaire.
  
  
• Vendredi 25 mars 2011 (à 11h): Tom McCormick (University of British Columbia, Canada) : A Combinatorial Polynomial Algorithm for Weighted Abstract Cut
  
  Hoffman and Schwartz developed the Lattice Polyhedron model and proved that it is totally dual integral (TDI), and so has integral optimal solutions. The model generalizes many important combinatorial optimization problems such as polymatroid intersection, cut covering polyhedra, min cost aborescences, etc., but has lacked a combinatorial algorithm. The problem can be seen as the blocking dual of Hoffman's Weighted Abstract Flow (WAF) model, or as an abstraction of ordinary Shortest Path and its cut packing dual, so we call it Weighted Abstract Cut Packing (WACP). We develop the first combinatorial algorithm for WACP, based on the Primal-Dual Algorithm framework. The framework is similar to that used by Martens and McCormick for WAF, in that both algorithms depend on a relaxation by a scalar parameter, and then need to solve an unweighted ``restricted'' subproblem. The subroutine to solve WACP's restricted subproblem is quite different from the corresponding WAF subroutine. The WACP subroutine uses an oracle to solve a restricted abstract cut packing/shortest path subproblem using greedy cut packing, breadth-first search, and an update that achieves complementary slackness. This plus a standard scaling technique yields a polynomial combinatorial algorithm.
  
  
• Jeudi 24 mars 2011 (à 15h30): Gérard Cornuéjols (Carnegie Mellon University, USA) : Cutting planes: A convex analysis perspective
  
  This talk will be based on joint work with Borozan, Basu, Conforti and Zambelli. We extend a theorem of Lovasz characterizing maximal lattice-free convex sets. Our result characterizes maximal S-free convex sets, where S is the intersection of a lattice with a (possibly unbounded) rational polyhedron. This result has implications in integer programming. In particular we show a ono-to-one correspondance between these sets and minimal valid inequalities.
  
  
• Jeudi 24 mars 2011 (à 14h): Laura Sanita (EPFL, Lausanne) : Set covering with ordered replacement
  
  We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system. Many variants of Bin Packing that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with ordered replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved. Joint work with: Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoss.
  
  
• Jeudi 17 mars 2011 (à 14h): Andras Sebo (G-SCOP) : Collapse of the VPN Pyramid
  
  The celebrated VPN Tree Conjecture raised by Fingerhut, Suri and Turner and then again by A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yenerhas has been proved by N. Goyal, N. Olver, and B. Shepherd using an intermediate station, the equivalence of the so called ``Pyramidal Conjecture'' by F. Grandoni, V. Kaibel, G. Oriolo, and M. Skutella (later a shortcut has been observed using a result of Padberg and Rao).
  
  The problem consists in designing paths between a given set of terminals so as to minimize the cost of capacities to be bought when routing a demand function -- satisfying certain linear constraints -- between terminals through the designed paths. Until now the results have been built as a pyramid using bricks from previous work as black boxes (or black bricks). In this note we redigest the subject with a geometric insight that leads to a simpler proof and sharpening the results. The black boxes are opened, the proof pyramid collapses to determining the extreme points of a polytope. (Incidentally the ``pyramidal conjecture'' turns out to lose its pyramidal character.)
  
  It turns out that the problem has a natural formulation as optimizing on a convex set whose vertices correspond to Steiner-trees of the network. Besides the simple proof and the connexion to polyhedral combinatorics, this new look on the problem yields - besides the known polynomial algorithms - to simple proofs and sharper results.
  Joint work with Nicola Apollonio, Fabrizio Grandoni, Gianpaolo Oriolo.
  
  
• Jeudi 17 février 2011 (à 14h30): Matej Stehlik (G-SCOP) : Coloration simultanée dans les graphes planaires
  
  Dans une coloration simultanée d'un graphe planaire G = (V,E,F), les éléments d'un sous-ensemble de {V,E,F} sont coloriés de manière à ce que des éléments adjacents ou incidents reçoivent des couleurs distinctes. Ce concept a été introduit en 1965 par Ringel, qui a considéré la coloration simultanée de sommets et faces. Le problème général est de déterminer le nombre minimum de couleurs qui permettent une coloration simultanée du graphe. Après une introduction générale je présenterai des résultats obtenus récemment en collaboration avec Ross Kang et Jean-Sébastien Sereni.
  
  
• Jeudi 10 février 2011 (à 14h30): Olivier Durand de Gevigney (G-SCOP) : Orientations des graphes et connexité
  
  Dans un graphe la connexité entre deux sommets u et v est le nombre de chemins disjoints qui permettent d'aller de u à v. La question est de savoir si on peut orienter un graphe avec des bornes inférieures sur la connexité. Nous aurons une approche structurelle et algorithmique de ce problème, notamment par le biais des théorèmes de Nash-Williams.
  
  
• Jeudi 27 janvier 2011 (à 14h30): Zoltan Zigeti (G-SCOP) : Orientations et Sandwich
  
  Le Problème du Sandwich pour une propriété P est défini de la façon suivante: Étant donnés deux graphes G_1 = (V,E_1) et G_2 = (V,E_2) tels que E_1 \subseteq E_2, existe-t-il un graphe G=(V,E) tel que E_1 \subseteq E \subseteq E_2 et G satisfasse la propriété P? Nous allons présenter une caractérisation et un algorithme polynomial pour le Problème du Sandwich où la propriété P est "avoir une orientation avec degré entrant donné pour chaque sommet".
  
  (travail en commun avec Olivier Durand de Gevigney, Sulamita Klein, et Viet Hang Nguyen)
  
  
• Jeudi 20 janvier 2011 (à 14h30): Jan van den Heuvel (London School of Economics, UK) : Circular Arboricity of Graphs and Matroids
  
  The arboricity of a graph G is the minimum number of forests in G whose union is the edge set of G. A classical result of Nash-Williams allows us to determine this number precisely. Recently, Daniel Gonçalves defined the related concept of circular arboricity. For this we want to map the edges of G to a circle with circumference d so that for every unit interval, the edges mapped into that interval induce a forest. We show that the minimum value of d for which this is possible is equal to the fractional arboricity of the graph. (In particular this means we have an explicit expression for the circular arboricity.)
  The proof of this result uses a more general weighted version of the concept of circular arboricity. This general result is related to, and has corollaries for, several problems of the following type: When is it possible to have a cyclic ordering of the edges of a graph G with n vertices, so that every n-1 cyclically consecutive elements give a spanning tree of G?
  All results and questions extend to matroids (but no knowledge about matroids will be needed to follow the talk).
  
  Talk based on joint research with Stéphan Thomassé.
  
  
• Jeudi 16 décembre 2010 (à 14h30): Yuri Orlovich (Belarus State University, Minsk, Belarus) : On maximal dissociation sets in graphs
  
  A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. A dissociation set is maximal if no other dissociation set contains this set. We consider the complexity and inapproximability results for the problem of finding a dissociation set of maximum size and the problem of finding a maximal dissociation set of minimum size within some hereditary classes of graphs.
  
  
• Jeudi 16 décembre 2010 (à 14h): Vladimir Kotov (Belarus State University, Minsk, Belarus) : Algorithms for partitioning and packing problems
  
  The partition problem is one of the basic NP-complete problems. A set A = {1,..., n} of items is given such that item i has weight ai. Can A be partitioned into 2 subsets such that the weights of the subsets are equal? In general in the optimization version the problem of partitioning items into m sets is equivalent to the classical multiprocessor scheduling problem on m machines. In multiprocessor scheduling n independent jobs have to be scheduled on m identical, parallel machines with the objective to minimize the makespan (maximum completion time). We consider some online and semi online versions for this problem. The bin packing problem asks to pack a list of items from (0, 1] into the smallest possible number of bins having unit capacity. We consider some online and semi online versions for this problem.
  
  
• Mardi 7 décembre 2010 (à 15h): Sulamita Klein (Universidade Federal do Rio de Janeiro, Brésil) : Well covered graphs with few P4's
  
  A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this work we shall use modular and primeval decomposition techniques to decide well coveredness of graphs such that, either all their P4- connected components are separable, or they belong to well known classes of graphs that, in some local sense, contain few P4's.
  
  
• Jeudi 2 décembre 2010 (à 14h30): David Pritchard (EPFL, Lausanne) : The Hypergraphic Tutte/Nash-Williams Theorem via Integer Decomposition, Total Dual Laminarity, and Power Matroids
  
  We reprove the hypergraphic generalization of the Tutte/Nash-Williams theorem, which gives sufficient conditions for a hypergraph to contain k disjoint connected hypergraphs. First we observe the theorem is equivalent to the natural LP relaxation having the integer decomposition property. Then we give a new proof of this property using LP uncrossing methods. We discover that "total dual laminarity" precisely characterizes g-polymatroids, and we note that hypergraphic matroids can be viewed as a special case of "power matroids."
  
  
• Jeudi 25 novembre 2010 (à 14h30): Frédéric Havet (I3S, Sophia-Antipolis) : Finding an induced subdivision of a digraph
  
  We consider the following problem for digraphs and oriented graphs: Given a digraph (or an oriented graph) G, does it contain a subdivision of a prescribed digraph D as an induced subgraph? We give a number of examples of polynomial instances as well as several NP-completeness proofs.
  
  This is a joint work with J. Bang-Jensen and N. Trotignon.
  
  
• Jeudi 4 novembre 2010 (à 14h30): Ryan Hayward (University of Alberta, Canada) : Solving Hex: Beyond Humans
  
  For the first time, automated solvers have surpassed humans in their ability to solve Hex positions: they can now solve many 9x9 Hex openings. We summarize the methods that attained this milestone, and examine the future of Hex solvers.
  
  
• Jeudi 14 octobre 2010 (à 14h30): Reza Naserasr (Institut Fourier, Grenoble) : Mapping planar graphs into projective cubes
  
  Projective cube of dimension k (PC(k)) is a the image of hypercube of dimension k+1 under identification of antipodal vertices. Projective cube of dimension 2k has odd girth 2k+1. We propose the following question:
  
  Given l \geq k, what is the smallest subgraph of PC(k) to which every planar graph of odd girth 2l+1 admits a homomorphism.
  
  We show how special cases of this question capture many well know problems.
  
  
• Jeudi 30 septembre 2010 (à 14h30): Bhalchandra Thatte (Oxford University, UK) : Graph reconstruction problems
  
  Ulam (1942) conjectured that every unlabelled finite simple graph on at least 3 vertices can be constructed (up to isomorphism) from the collection of its unlabelled induced proper subgraphs. Harary (1964) proposed an analogous conjecture for reconstruction of graphs from their edge-deleted subgraphs. I will survey some results, and present some my ideas based on the classic results of Lovasz, Muller and Nash-Williams (from 1970s). I will then give an overview of how these ideas may be useful in the problem of reconstructing population pedigrees.