Séminaires 2017 - 2018

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.

• Vendredi 25 mai 2018 (à 11h): Jens Vygen (Université de Bonn) : Approaching 3/2 for the s-t-path TSP
  
  The s-t-path TSP is a variant of the traveling salesman problem in which the endpoints of the tour are given and distinct. The integrality ratio of the natural linear programming relaxation is known to be at least 1.5. Our main result is a polynomial-time algorithm with approximation guarantee 1.5+epsilon, for any epsilon>0. It is well known that Wolsey's analysis of Christofides' algorithm also works for the s-t-path TSP exce narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm ``guesses'' (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a k-stage recursive dynamic program, we can compute a spanning tree (V,S) and an LP solution y such that (1/2+O(2^{-k}))y is in the T-join polyhedron, where T is the set of vertices whose degree in S has the wrong parity.
  
  This is joint work with Vera Traub.
  
  
  
• Jeudi 26 avril 2018 (à 14h30): Nicolas Bousquet (G-SCOP) : EPTAS for Max Clique on Disks and Unit Balls
  
  We propose a polynomial-time algorithm which takes as input a finite set of points of R^3 and compute, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG '18]. In this paper, we use this forbidden structure to obtain a randomized EPTAS (and a deterministic PTAS).
  
  
  
• Jeudi 1er mars 2018 (à 14h30): Alantha Newman (G-SCOP, Grenoble) : Coloring and Dominating Set on Digraphs with Bounded Independence Number
  
  Some optimization problems exhibit the phenomena that a bound for the problem on tournaments can be transferred to a bound on general digraphs with an additional factor of alpha, where alpha is the size of the maximum independent set. This motivates studying problems, for which good bounds on tournaments exist, on digraphs with bounded independence number. In this talk, we present algorithms (and several open problems) for coloring and dominating sets on such digraphs.
  
  Based on joint work with A. Haratyunyan, T-N. Le, and S. Thomassé.
  
  
  
• Jeudi 25 janvier 2018 (à 14h30): Vincent Beffara (Institut Fourier, Grenoble) : Le modèle de dimères bi-périodique
  
  Une configuration de dimères, ou couplage parfait, sur un graphe biparti est une collection d'arêtes telles que chaque sommet soit incident à exactement une d'entre elles ; on s'intéresse au dénombrement de telles configurations, et au comportement typique d'une configuration choisie aléatoirement. Plus précisément, dans le cas où le couplage est choisi uniformément sur un domaine d'un réseau planaire périodique, le comportement asymptotique est bien compris : on voit apparaître une forme déterministe séparant une phase "gelée" près des bords du domaine et une région désordonnée "liquide" à l'intérieur, et les fluctuations de l'interface sont données par le processus d'Airy. Dans le cas d'une mesure donnée par des poids périodiques, on peut voir apparaître trois phases différentes, et les mêmes questions se posent. Je présenterai quelques techniques utilisées pour étudier ces objets, et un travail en commun avec S. Chhita et K. Johannsson visant à comprendre les interfaces entre la phase liquide et la phase gazeuse.
  
  
  
• Jeudi 18 janvier 2018 (à 14h30): Zoltán Király (Eötvös Loránd University, Budapest) : The MMS Parameter of Graphs and Degree Sequences
  
  An interesting graph parameter mu(G) is introduced which is connected to the Manickam-Miklós-Singhi Conjecture : mu(G) is the minimum number of edges whose deletion destroys all perfect fractional matchings.
  As determining mu(G) is NP-hard even for very special cases, we study the minimum and maximum of this parameter over realizations of a given degree sequence.
  Given a graphical degree sequence d, let mu(d) and \bar mu(d) denote the minimum and the maximum value of mu over all simple graphs realizing degree sequence d. We determine these for regular degree sequences. In our main result we show that there is a polynomial algorithm to determine mu(d) for an arbitrary graphical degree sequence d.
  
  Joint work with my students at BSM: Neeraja Kulkarni, Ian McMeeking and Joshua Mundinger.
  
  
  
• Jeudi 4 janvier 2018 (à 14h30): Ahmad Abdi (University of Waterloo) : Deltas, extended odd holes and their blockers
  
  A delta is the clutter over ground set {1,...,n} whose members are {1,2},{1,3},...,{1,n},{2,3,...,n}, where n is an integer at least 3. An extended odd hole is any clutter over ground set {1...n} whose minimum cardinality members are {1,2},{2,3},...,{n-1,n},{n,1}, where n is an odd integer at least 5. Deltas, extended odd holes and their blockers, pointed out as early as 1963 by Alfred Lehman, are the simplest classes of nonideal clutters.
  Now let C be a clutter where no element is contained in every member. If nonnegative weights can be assigned to the elements so that every member has weight more than half the total capacity, then C must have a delta or the blocker of an extended odd hole minor. I will sketch a proof of this result, which relies two tools, one for finding delta minors and another for finding extended odd hole minors.
  
  Joint work with Dabeen Lee.
  
  
  
• Lundi 18 décembre 2017 (à 14h30): Edouard Bonnet (Middlesex University, Hendon, London) : QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
  
  A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs. Since then, it has been an intriguing open question whether or not this tractability can be extended to the more general disk graphs. Even the existence of a subexponential algorithm or an pproximation algorithm with better ratio than the known 2-approximation were open.
  We present a QPTAS and subexponential algorithm for Maximum Clique on disk graphs. They both exploit that some cyclic structure cannot be found in the complement of a disk graph. In stark contrast, Maximum Clique in the intersection graph of ellipses or triangles is very unlikely to have such algorithms.
  
  
  
• Jeudi 14 décembre 2017 (à 14h30): Gábor Simonyi (Rényi Institute, Budapest) : Graph capacities: Shannon, Sperner, permutation
  
  The Shannon capacity of graphs is a classical graph parameter, defined by Shannon in 1956. Its definition is asymptotic, and this may explain that its value is sometimes very hard to determine, often still unknown, even for specific small graphs, like odd cycles of length at least seven. Sperner capacity is a generalization to directed graphs, introduced by Gargano, Körner, and Vacaro, Being more general, its determination is at least as hard in general, but for certain specific digraphs it still can make sense to ask the value of their Sperner capacity. On one hand it happens that the Shannon capacity problem is easy for some graph, while determining the Sperner capacity for some of its orientations is nontrivial. On the other hand, sometimes the Shannon capacity problem is unsolved, but we can still say something about the Sperner capacity of certain oriented versions. Permutation capacity is a further variant where we can consider both the undirected and the directed versions. In the talk I plan to give an overview of some of the results concerning these graph parameters.
  
  
  
• Vendredi 8 décembre 2017 (à 11h): Penny Haxell (University of Waterloo) : Chromatic index of random multigraphs
  
  Let G be a loopless multigraph with maximum degree d. It is clear that d is a lower bound for the chromatic index of G (the smallest k such that E(G) can be partitioned into k matchings). A long-standing conjecture due to Goldberg and (independently) Seymour states that the chromatic index of G takes one of only three possible values: d, d+1 or a certain other parameter of G, that is closely related to the fractional chromatic index of G (and is also a natural lower bound for the chromatic index). Here we prove this conjecture for random multigraphs. In fact we prove the stronger statement that the value d+1 is not necessary for the random case. We will discuss various graph theoretical tools that are used in the proof, in particular the method of Tashkinov trees (which has been a key component of much of the progress on this conjecture to date).
  
  This represents joint work with Michael Krivelevich and Gal Kronenberg.
  
  
  
• Jeudi 30 novembre 2017 (à 14h30): Pierre Aboulker (G-SCOP) : Generalizations of the geometric de Bruijn Erdős Theorem
  
  A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the euclidean plane determines at least n distinct lines. The line L(u,v) determined by two points u, v in the euclidean plane consists of all points p such that:
  - dist(p, u) + dist(u, v) = dist(p, v) (i.e. u is between p and v) or
  - dist(u, p) + dist(p, v) = dist(u, v) (i.e. p is between u and v) or
  - dist(u, v) + dist(v, p) = dist(u, p) (i.e. v is between u and p).
  With this definition of line L(u,v) in an arbitrary metric space (V, dist), Chen and Chvátal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points.
  The talk will survey results on and around this conjecture.
  
  
  
• Vendredi 20 octobre 2017 (à 14h30): Marthe Bonamy (LaBRI, Bordeaux) : Partitioning the vertices of a torus into isomorphic subgraphs
  
  Let H be an induced subgraph of the m-dimensional k-torus C_m^k. We show that when k >= 3 is even and |V (H)| divides k^m, then for sufficiently large n the vertices of C_n^k can be partitioned into disjoint copies of H. We also show that when k is the product of two coprime odd integers, then there exists H where |V (H)| divides k m but for no n can the vertices of C_n^k be partitioned into disjoint copies of H. This disproves a conjecture of Gruslys. We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph H of the k-dimensional hypercube Qk, such that there is no n for which the edges of Qn can be partitioned into copies of H.
  
  Joint work with Natasha Morrison and Alex Scott.
  
  
  
• Vendredi 20 octobre 2017 (à 11h): Nicolas Bousquet (G-SCOP) : Domination in structured tournaments
  
  There exist tournaments, such as random tournaments, for which the domination number is arbitrarily large. One can naturally ask what happens if we add some structure on the tournament, for instance if the tournament can be "covered" using a bounded number of partial orders. Alon et al. showed that k-majority tournaments have bounded domination number. Gyarfas and Palvolgyi conjectured that the following is true : If a tournament admits a partition of its arc set into k quasi orders, then its domination number is bounded in terms of k. We provide a short proof that the following more general conjecture of Erdos, Sands, Sauer and Woodrow: If the arcs of a tournament T are colored with k colors, there exist a set X of at most g(k) vertices such that for every vertex v of T, there is a monochromatic path from X to v.
  
  (joint work with William Lochet and Stéphan Thomassé)
  
  
  
• Vendredi 20 octobre 2017 (à 9h30): Victor Chepoi (LIF, Marseille) : On corner peelings and unlabeled compression schemes for ample concept classes
  
  Littlestone and Warmuth (1986) defined sample compression schemes and showed that the VC-dimension VC-dim(C) of a concept class C of {0,1}^X is a lower bound on the size of any compression scheme for C. Consequently, the existence of a compression scheme of bounded size implies learnability. They also asked whether the VC-dimension determines also an upper bound on the minimal size of a compression scheme: "Does every concept class of VC-dimension d have a sample compression scheme of size O(d)?" This is currently one of the oldest unsolved problems in computational learning theory.
  We will investigate this problem for the particular case of ample concept classes. Ample classes (also called lopsided or extremal classes) are the classes which contain the same number of concepts as the number of shattered sets (or the number of strongly shattered sets). They admit a multitude of combinatorial, geometric, and graph-theoretical properties and characterizations and contain several important combinatorial objects: maximum classes of given VC-dimension, median systems, convex geometries, etc. For ample classes C, was conjectured that a compression scheme can be obtained via a corner peeling of C, i.e., of a total ordering c_1,...,c_n of the concepts of C such that each c_i is a corner of the concept class C_i={c_1,...,c_i}, i.e., c_i belongs to a unique maximal cube of C_i.
  We prove that the existence of corners of ample classes is equivalent to the extendable shellability of the face complex of the octahedron, the dual to the cube {0,1}^X. Using this equivalence and a beautiful counterexample by H.T. Hall (PhD Thesis, 2004) of a non extendable partial shelling of a 11-dimensional octahedron, we establish the existence of ample classes without corners. Trying to circumvent this difficulty and to find compression schemes, we prove that the existence of compression schemes for ample classes is equivalent to orientations of edges of their 1-inclusion graphs satisfying two combinatorial conditions: (1) "for each concept c of C, the outgoing from c edges belong to a common cube of C" and (2) "the restriction of the orientation on each cube B of C is an Unique Sink Orientation (USO) on B." Nevertheless, the existence of such orientations is still open for us.
  
  The talk is based on an ongoing joint work with J. Chalopin, S. Moran, and M.K. Warmuth.
  
  
  
• Jeudi 19 octobre 2017 (à 11h): Tomas Kaiser (University of West-Bohemia) : Hamilton cycles in tough chordal graphs
  
  The toughness of a graph is an invariant introduced by Chvátal in 1973 and closely related to hamiltonian-type graph properties. In fact, Chvátal conjectured that every graph of sufficiently large toughness contains a Hamilton cycle. One class where the conjecture is known to be true is the class of chordal graphs; we will discuss the recent proof that 10-tough chordal graphs are hamiltonian, improving on the 1998 result of Chen et al. about 18-tough chordal graphs. (Such an improvement was one of the main problems mentioned in my talk about graph toughness at G-SCOP five years ago.) The proof uses Aharoni and Haxell's hypergraph extension of Hall's Theorem, together with the well-known representation of chordal graphs as intersection graphs of subtrees of a tree.
  
  Joint work with Adam Kabela.
  
  
  
• Jeudi 12 octobre 2017 (à 14h30): Maria Macekova (G-SCOP) : Light subgraphs in sparse graphs
  
  A class of graphs is called sparse, if the number of edges of its members is bounded by a linear function of the number of their vertices. Sparse graphs have, compared to dense graphs, specific properties - they contain vertices of low degrees, values of different color invariants are upper bounded by a constant. Within the family of sparse graphs plays an important role class of planar graphs, i.e. graphs that can be drawn in a plane without crossing. It is well known, that planar graphs contain a vertex of degree at most 5, but for searching for larger "light" configurations with given constant bounds on the degrees it is necessary to add more conditions. It is natural to require that all vertices have degree at least two; for containing a rich collection of light graphs, we will also suppose lower bounds on the girth of the graph. In this talk we give a summary of the results about light subgraphs in the family of planar graphs and we mention some results for other classes of sparse graphs (e.g. 1-planar graphs).
  
  
  
• Jeudi 5 octobre 2017 (à 14h30): Nikhil Kumar (IIT Delhi) : Multicommodity Flows and Cuts
  
  In the multiflow maximization problem we are given a graph with edge capacities and some terminal pairs of nodes (s_i,t_i). The goal is to route as much flow between the terminals as possible. The amount of flow that can be routed (not necessarily integer) between the terminals is clearly upper bounded by the total capacity of edges whose removal disconnects each terminal pair. Such a subset of edges is called a multicut and it is NP-Hard to minimize in general. In this talk, we will discuss the relationship between multiflow & multicut and some combinatorial algorithms for finding suitable multi cuts/flows.
  
  
  
• Jeudi 21 septembre 2017 (à 14h30): Roland Grappe (LIPN) : Principally box-integer polyhedra
  
  A polyhedron is box-integer if its intersection with any integer box is an integer polyhedron. We introduce principally box-integer polyhedra : they are the polyhedra whose dilatations are box-integer as soon as they are integer. We will present several characterizations of principally box-integer polyhedra, which involve matrices and strong integrality properties of linear sytems. Eventually, we will discuss connexions with combinatorial optimization problems.
  
  This is a joint work with Patrick Chervet and Louis-Hadrien Robert.