Séminaires 2016 - 2017
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 20
juillet 2017 (à 14h30):
Myriam Preissmann (G-SCOP) : New results on variants of the Majority problem
The variant of the Majority problem we are considering is the following. A colorblind player is given a set of N colored balls. He knows that each ball is colored either red or green, and that there are less green than red balls, but he cannot distinguish the two colors. For any two balls he can ask whether they are colored the same. His goal is to determine the color of each of the balls, asking as few questions as possible. In the case where there are at most p (respectively exactly p) green balls the minimum number of questions that guarantees the determination of the colors is denoted by Q(N,p,\le) (respectively Q(N,p,=)). We extend results of Aigner on exact values of Q(N,p,\le), and we provide lower and upper bounds as well as exact values for Q(N,p,=), depending on the values of N and p. Our results lead to several new questions.
Joint work with Paul-Elliot Anglès d'Auriac, Francis and Vivien Maisonneuve and Emmanuel Preissmann.
- Jeudi 29
juin 2017 (à 14h30):
Moritz Mühlenthaler (TU Dortmund) : Reconfiguration of Common
Independent Sets of Partition Matroids
We investigate the complexity of reconfiguring common independent sets of two or more partition matroids. In particular, we show that deciding the connectivity of two common independent sets of two partition matroids is easy, while for three or more matroids the task becomes PSPACE-complete, even for very restricted cases. It turns out that the former task can be reduced to calling an oracle for Bipartite Matching Reconfiguration once. The reduction used for the latter result also implies PSPACE-completeness of restricted versions of Stable Set Reconfiguration and 3-CNF Reconfiguration.
- Jeudi 18
mai 2017 (à 14h30):
François Dross (LIRMM, Montpellier) :
Décompositions des sommets de graphes peu denses
Le degré moyen d'un graphe est la moyenne de ses degrés. Le degré moyen maximum d'un graphe G est le maximum du degré moyen de tous les sous-graphes de G. En particulier, les graphes planaires de maille (i.e. de plus petit cycle de taille) au moins g ont un degré moyen d'au plus 2g/(g-2). Plus le degré moyen maximum est bas, moins le graphe est dense, et de même pour un graphe planaire, plus la maille est élevée, moins le graphe est dense.
Comme généralisation de la coloration propre, on s'intéresse aux partitions des sommets des graphes en indépendants, forêts, graphes de degrés bornés, graphes dont les composantes connexes sont bornées... Dans la lignée de résultats de colorations de graphes plongés dans des surfaces (theorème des 4 couleurs...), on s'attaque aux partitions de graphes peu denses en deux graphes d'une des classes nomées précédemment. On utilise la méthode du déchargement pour prouver de tels résultats.
- Jeudi 4
mai 2017 (à 14h30):
Claire Pennarun (LaBRI, Bordeaux) : Dessins non-alignés de graphes planaires
Dans cet exposé, nous présenterons les dessins non-alignés de graphes. Un dessin non-aligné d'un graphe G à n sommets est un dessin de G sur une grille régulière à m lignes et l colonnes (m,l <= n) dans lequel toute ligne et colonne de la grille contient au plus un sommet du graphe. Ces dessins ont des propriétés intéressantes et sont notamment utilisés pour la visualisation de grands graphes. Ici, nous nous restreindrons au cas de graphes planaires, et nous souhaitons que le dessin final soit également planaire.
Si le dessin est restreint à une grille "minimale" (n x n), on verra que beaucoup de graphes planaires ne possèdent pas de dessins non-alignés planaires avec arêtes droites. Nous nous intéresserons donc à deux pistes de recherche : l'augmentation de la taille de la grille support du dessin, et l'autorisation d'arêtes brisées dans le dessin. Nous montrerons deux algorithmes générant des dessins planaires non-alignés avec des arêtes droites dans une grille d'aire O(n^4). Ces algorithmes sont basés sur les méthodes classiques de dessin de graphes planaires dans des grilles proposés par Schnyder et par de Fraysseix et al. Enfin, nous verrons qu'il est possible de dessiner en "non-aligné" un graphe planaire sur une grille n x n avec un nombre limité de brisures d'arêtes autorisées dans le dessin.
- Jeudi 13
avril 2017 (à 14h30):
Jean-Florent Raymond (LIRMM, Montpellier et MIMUW, Varsovie) : Cutwidth: obstructions and algorithmic aspects
Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for graphs of cutwidth at most k.
In this talk, I will show how lean orderings, which are similar to lean tree decompositions, can be used to upper-bound the size of these obstructions and to compute cutwidth.
This is joint work with Archontia Giannopoulou, Michal Pilipczuk, Dimitrios Thilikos, and Marcin Wrochna.
- Jeudi
23 mars 2017 (à 14h30):
Frédéric Meunier (Ponts et
Chaussées, Marne-la-Vallée) : Graphes de Kneser généralisés, borne de Dol'nikov et nombre chromatique circulaire
A tout hypergraphe H, on associe un graphe de Kneser généralisé KG(H) de la manière suivante : les arêtes de H en constituent les sommets et les paires d'arêtes disjointes de H en constituent les arêtes. Un théorème de Dol'nikov assure que le nombre chromatique de KG(H) est toujours plus grand que la « 2-colorability defect » de H, invariant combinatoire basé sur la taille du plus grand sous-hypergraphe 2-colorable de H. En utilisant un lemme récent de topologie combinatoire (Chen's lemma), nous montrons que lorsqu'il y a égalité entre le nombre chromatique et la « 2-colorability defect », il y a aussi égalité entre le nombre chromatique usuel et le nombre chromatique circulaire (forme affinée du nombre chromatique usuel), ce qui ajoute donc de nouveaux graphes à la famille très étudiée des graphes possédant des nombres chromatiques usuel et circulaire égaux. Au cours de cet exposé, nous discuterons également de généralisations de ce résultat et de quelques questions ouvertes afférentes, en particulier celle-ci : peut-on reconnaître les H tels que le nombre chromatique de KG(H) est égal à la « 2-colorability defect » de H en temps polynomial ?
- Jeudi 23 février 2017 (à 14h30):
Cong Bang Huynh (Institut Fourier, Grenoble) : Une mesure de probabilité sur l'ensemble des chemins auto-évitants infinis
On cherche à définir une mesure de probabilité naturelle sur l'ensemble des chemins auto-évitants infinis (noté SAW_infty) dans le demi-plan H. Cette question a été étudiée par Kesten et Lawler à partir de mesures sur des chemins auto-évitants finis. Notre méthode construit directement une famille à un paramètre de mesures sur SAW_\infty, (P_\lambda)_{\lambda>\lambda_c}. Quand \lambda\to\lambda_c on espère obtenir une limite qui ressemble à la mesure de Kesten et Lawler. Je décrirai quelques propriétés de cette famille de mesures.
- Mardi 21 février 2017 (à 11h):
Seffi Naor (Technion, Haifa, Israël) : Multi-label classification with pairwise relations
Motivated by various applications in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics, we introduce the metric multi-labeling problem. The input is a set of objects with pairwise relations, given as a weighted graph over the objects, together with a label set and assignment costs of labels to objects. Departing from classical work on the metric labeling problem, assignment costs may be either positive or negative, reflecting a recommendation given by a local learning process which infers label preferences of objects. However, the learning process ignores pairwise relations of objects. Clearly, the labeling cost for completely agreeing with this recommendation is the minimum possible, and this is our benchmark labeling. The objective is to find an assignment of (multiple) labels to objects, at least one for each object, minimizing the sum of the following two terms: (1) the deviation cost from the benchmark labeling, and (2) the separation cost between pairs of similar objects receiving different label sets. Thus, the goal is to globally optimize the assignment of label sets to objects, while taking into account local preferences of objects. We obtain a (tight) 2-approximation for this problem.
Additionally, in many natural applications a bound is given on the number of labels that can be assigned to an object. This leads to a very interesting problem of simultaneous rounding of many (fractional) points contained in a uniform matroid polytope, while bounding pairwise distances. We achieve a true O(log k)-approximation for this problem (k is the number of labels).
Joint work with Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, and Roy Schwartz.
- Jeudi 2 février 2017 (à 14h30):
Ararat Harutyunyan (Université de Toulouse) : List Coloring Digraphs
The dichromatic number of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann-Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs. In this talk, we will focus on the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We show that the list dichromatic number of a digraph can be arbitrarily larger than its dichromatic number, a property that is well-known for graphs. Moreover, we show that other results known on graphs describing the relationship between the chromatic and list chromatic numbers generalize naturally in the setting of digraphs.
Based on joint work with Julien Bensmail (Nice, Sophia-Antipolis) and Khang Le (ENS de Lyon).
- Jeudi 12 janvier 2017 (à 14h30):
Marthe Bonamy (LaBRI, Bordeaux) : Reed's conjecture and strong edge coloring
The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex "sees few edges" in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.
This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).
- Jeudi 8 décembre 2016 (à 14h30):
Eric Fusy (LIX, Palaiseau) : Bijections pour cartes planaires à bords
Nous présentons une méthode bijective générale pour les cartes planaires, basée sur certaines orientations. Cette méthode peut être adaptée pour les cartes planaires à bords et nous montrerons en particulier comment elle s'applique aux triangulations à bords et comment contrôler le paramètre de maille (triangulations à bords sans boucle, ou sans boucle ni arête multiple)
- Vendredi 2 Décembre 2016 (à 10h):
András Gyárfás (Renyi Institute, Budapest) : Results and problems on chi-bounded graph classes
tba
- Jeudi 1er Décembre 2016 (à 10h):
Dieter Rautenbach (Université d'Ulm,
Allemagne) : Zero forcing
A set Z of vertices of a graph G is a zero forcing set of G if initially labeling all vertices in Z with 1 and all remaining vertices of G with 0, and then, iteratively and as long as possible, changing the label of some vertex u from 0 to 1 if u is the only neighbor with label 0 of some vertex with label 1, results in the entire vertex set of G. The zero forcing number Z(G), defined as the minimum order of a zero forcing set of G, was proposed as an upper bound of the corank of matrices associated with G, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. We discuss such bounds and some of the corresponding extremal graphs.
Joint work with M. Gentner, L.D. Penso, and U.S. Souza.
- Mardi 29 Novembre 2016 (à 14h30):
Vincent Cohen-Addad (ENS, Paris) : The power of local search for clustering
What are the performance guarantees of the algorithms used in practice for clustering problems? In a paper with Phil Klein and Claire Mathieu, we give the first polynomial-time approximation schemes for the following problems:
(1) uniform facility location in edge-weighted planar graphs;
(2) k-median and k-means in edge-weighted planar graphs;
(3) k-means in Euclidean space of bounded dimension.
The algorithm is a standard, widely-used local search heuristic where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/\eps^{O(1)} centers. In a second line of work with Chris Schwiegelshohn, we show that this algorithm also performs near-optimaly for several types of instances that aim at characterizing the structure of real-world instances stemming from machine learning and data analysis. Those results make a step toward understanding the success of local search heuristics in practice.
- Jeudi 10 novembre 2016 (à 14h30):
Hojin Choi (KAIST, Daejeon, Corée du Sud) : Online Ramsey theory for the cycle of length 3
Online Ramsey theory is a study on the online version of Ramsey theory, based on online Ramsey game. Given a fixed graph H and a class C of graphs, an online Ramsey game for H on C} is a game between two players Builder and Painter with the following rules: On each round, Builder draws a new edge with the constraint that the resulting graph must be in C, and Painter colors the new edge either red or blue.
Builder wins if Builder can force Painter to make a monochromatic copy of H at some point of the game, and Painter wins if a monochromatic copy of H can be avoided forever. Online Ramsey game was first investigated in 2004 by Grytczuk, Haluszczak, and Kierstead where they studied online Ramsey game on forests, k-colorable graphs, outerplanar graphs, and planar graphs. Recently, Petrickova continued the study on planar graphs further by disproving a conjecture by Grytczuk, Haluszczak, and Kierstead.
We focus on characterizing a graph F such that Painter wins the online Ramsey game for C_3 on F-free graphs, while a graph is F-free if the graph does not contain F as a subgraph; we succeed the characterization except for when F is one particular graph. We also prove that Painter wins the online Ramsey game for C_3 on K_4-minor-free graphs; this extends a result by Grytczuk, Haluszczak, and Kierstead.
This is joint work with Ilkyoo Choi, Jisu Jeong, and Sang-il Oum.
- Jeudi 3 novembre 2016 (à 14h30):
Quentin Fortier (G-SCOP) : Packing with matroid constraints
A theorem of Edmonds ensures that k-arc-connectivity in a rooted directed graph is equivalent to the existence of a packing of k spanning rooted arborescences. Frank conjectured a generalization of this theorem where the packing must verify an additional constraint, given by a matroid. We prove this conjecture for particular cases and provide a counterexample for the general case.
Joint work with Zoltán Szigeti, Csaba Király and Shin-ichi Tanigawa.
- Mardi 18 octobre 2016 (à 10h15):
Imre Barany (Renyi Institute, Budapest) : Curves in
R^d intersecting every hyperplane at most d+1 times
A partial result: if a planar curve intersects every line in at most 3 points, then it can be partitioned into 4 convex curves. This result can be extended to R^d: if a curve in R^d intersects every hyperplane at most d+1 times, then it can be split into M(d) convex curves. The extension implies a good, asymptotically precise, lower bound on a geometric Ramsey number.
Joint result with the late Jiri Matousek and Attila Por.
- Jeudi 22 septembre 2016 (à 14h30):
Marthe Bonamy (LaBRI, Bordeaux) : Tight lower bounds for the complexity of multicoloring
In the multicoloring problem, also known as (a:b) or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph with parameters a and b. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science. We study the complexity of determining whether a graph has an (a:b)-coloring. Nederlof showed in 2008 a (b+1)^n*n^O(1)-time algorithm for (a:b)-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time 2^o(log b)*n unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we also prove that the existing algorithms for the r-monomial detection problem are optimal under ETH.
This is joint work with Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala and Marcin Wrochna (University of Warsaw).
- Mardi 13 septembre 2016 (à 14h30):
Sylvia Boyd (Université d'Ottawa) : Experimenting with a New Set of Trees for the Best-of-Many Christofides
Algorithm for the Metric Travelling Salesman Problem
The well-known Christofides algorithm for the metric Travelling Salesman Problem (TSP) gives a 3/2-approximation for the problem, and involves finding a minimum cost spanning tree T of the graph, and then a minimum cost perfect matching of the odd degree nodes of T. In the best-of-many variation of this problem, one begins with a collection of spanning trees rather than just one, finds the minimum cost perfect matching for the odd degree nodes for each of these trees, and then keeps the best final TSP result. Recently Genova and Williamson showed empirically that this method performs significantly better than the Christofides method.
We explore the best-of-many Christofides idea for a different set of spanning trees. This set of trees is exponential in size, however it has the advantage that without generating the trees explicitly we can find the best TSP solution for the whole set with just one application of a minimum cost perfect matching algorithm.
Joint work with Nicholas Desjardin.
- Jeudi 8 septembre 2016 (à 14h):
Alantha Newman (G-SCOP) : The Alternating Stock Size Problem and the Gasoline Puzzle
Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms.
We consider a related problem, which we call the alternating stock size problem, where the number of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79.
Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovasz, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.
Joint work with Heiko Roeglin (Universitaet Bonn) and Johanna Seif (ENS Lyon).
- Jeudi 8 septembre 2016 (à 11h):
Michael Tarsi (Tel-Aviv University) : The structure of graphs with Circular flow number 5 or more, and the complexity of their recognition problem
We design an arsenal of methods for constructing graphs, in particular Snarks, with circular flow number at least 5. As one indication to the diversity and density of the obtained family of graphs. we show that it is sufficiently rich so that the corresponding recognition problem is NP-complete. At the core of our constructions is the Algebra of symmetric unions of integer open intervals in the ring R/5Z and its Graphic Sub-algebra. Introducing and studying these Algebras is a part of the talk.
Joint work with Louis Esperet and Giuseppe Mazzuoccolo.