# 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 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.