Séminaires 2022 - 2023

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.

Depuis 2020, nous organisons également un séminaire virtuel (conjointement avec Lyon et Clermont-Ferrand), le Séminaire virtuel de théorie des graphes et combinatoire en Rhône-Alpes et Auvergne.

• Jeudi 23 mars 2023 (à 14h30): Florent Galliot (Institut Fourier, Grenoble) : The Maker-Breaker positional game
  
  The Maker-Breaker game is played on a hypergraph H. Maker and Breaker take turns coloring vertices of H, in red and blue respectively. Maker wins if she gets a monochromatic red edge at any point, otherwise Breaker wins. We present some state of the art around this game and then proceed with our own results. Our study is centered on the notion of danger at x, which is a subhypergraph representing an urgent threat that Breaker must hit with his next pick if Maker picks x. Applying this concept in hypergraphs of rank 3 i.e. in which all edges are of size at most 3, we provide a structural characterization of the winner with perfect play, as well as optimal strategies for both players based on danger intersections. A crucial corollary is that Maker has a winning strategy on H if and only if she can guarantee the appearance, within the first three rounds of play, of a very specific elementary subhypergraph on which she easily wins. As a consequence, we are able to determine the algorithmic complexity of deciding which player has a winning strategy on a given hypergraph: this problem, which is known to be PSPACE-complete on 6-uniform hypergraphs, is in polynomial time on hypergraphs of rank 3. Another consequence is that, if Maker has a winning strategy on a hypergraph H of rank 3, then she can get a monochromatic red edge in just O(log(|V(H)|)) rounds of play.
  
  
  
• Jeudi 16 mars 2023 (à 14h30): David Saulpic (University of Vienna) : Differential Privacy for Clustering
  
  Differential Privacy is a mathematical model for confidentiality: it helps quantifying how much noise it is necessary to inject in an algorithm in order to make its output "private", i.e., not dependent too much on any particular input data point. Only a few private datastructures are currently known, e.g, for counting or computing heavy hitters. To design a private algorithm, one option is therefore to reduce the target problem to those simple task. In this talk, I will illustrate this with k means clustering, and present a reduction from k-means to mere counting. Applying known results for private counting, this yields for differentially-private algorithm for k-means, when the input undergoes insertion and deletion of points.
  
  
  
• Jeudi 2 mars 2023 (à 14h): Pat Morin (Carleton University, Ottawa) : Linear Colouring, Centered Colouring, Treedepth, Treewidth, and Grids
  
  In this talk I will give an overview of recent results relating the linear chromatic number of a graph to its treedepth (aka, centered chromatic number) and discuss a bold conjecture of Kun, O'Brien, Pilipczuk, and Sullivan about a condition-free relationship between the linear and centered chromatic numbers of a graph. This will include recent joint work with Bose, Dujmović, Houdrouge, and Javarsineh that sharpens the upper bound on centered chromatic number as a function of linear chromatic number and provides further evidence in support of the conjecture.
  
  
  
• Jeudi 23 février 2023 (à 14h30): Jean-Florent Raymond (LIMOS, Clermont-Ferrand) : Long induced paths in minor-closed graph classes
  
  An induced path is a path, while the reverse is not true in general. Can we however guarantee that a graph has a "long" induced path if it has a "large" path, for a suitable definition of "long" and "large"? In this talk I will present results about this question in topological minor-closed graph classes (in particular graphs of bounded pathwidth or treewidth) and give directions for future research on this topic.
  This is joint work with Claire Hilaire.
  
  
  
• Jeudi 2 février 2023 (à 14h30): Louis Esperet (G-SCOP, Grenoble) : Testability and local certification
  
  The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property.
  During this talk, I will present the main results in the area of graph property testing and then focus on the sparse model. We prove that for any minor-closed class F, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from F in this model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with only finitely many forbidden subgraphs.
  I will also explain how our proof techniques can be used to extend a recent result of Elek on approximate proof labeling schemes.
  Joint work with Sergey Norin.
  
  
  
• Jeudi 26 janvier 2023 (à 14h30): Ugo Giocanti (G-SCOP, Grenoble) : Twin-width IV and V: ordered structures, modular counting and matrix multiplication
  
  Twin-width is a graph parameter recently discovered by Bonnet, Kim, Thomassé and Watrigant that aims at generalizing and unifying many previous notions from parameterized complexity. The original article introducing twin-width was the starting point of a series of papers setting the basis of the theory of twin-width. In this presentation, I will first give you a brief introduction to twin-width, and state the main results and questions. Then I will focus on ordered graphs, (i.e. graphs with a total order on their vertices) and show you that in this case there are many different ways to characterize twin-width boundedness, going from enumerative combinatorics to logics. In particular, from these characterizations we will see that there exists an FPT-algorithm to approximate the twin-width of ordered graphs, which is still not known to exist in the general case. In the remaining time, as an example of application I will explain you how to derive an efficient algorithm to compute in time O_{q,t}(n^2 log(n)) the product of two matrices of twin-width t over the finite field F_q.
  Joint work with Edouard Bonnet, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé and Szymon Torunczyk.
  
  
  
• Jeudi 19 janvier 2023 (à 14h30): Thomas McCormick (University of British Columbia) : Parametric Min Cut Complexity
  
  Consider the Max Flow / Min Cut problem where the arc capacities depend on one or more parameters. Then the max flow value as a function of the parameter(s) is a piecewise linear concave function. The complexity of a class of problems is the worst-case number of pieces in this function.
  It has been know since Carstensen (1983) that in general this function has exponential complexity. But Gallo, Grigoriadis, and Tarjan (1989) showed that when we restrict to Source-Sink Monotone (SSM) networks and a single parameter, the complexity is only linear, and this has been generalized by various authors.
  SSM networks are a special case of a general theory of parametric optimization by Topkis, which applies equally to more than one parameter. Our main result is that even with just two parameters, the complexity of SSM Min Cut is exponential.
  
  
  
• Jeudi 12 janvier 2023 (à 14h30): Caroline Brosse (LIMOS, Clermont-Ferrand) : Polynomial delay enumeration of minimal chordal completions
  
  Motivated by the problem of enumerating all tree decompositions of a graph, we consider the problem of listing all the minimal chordal completions of a graph. In 2017, Carmeli et al. proved that all minimal chordal completions or equivalently all proper tree decompositions of a graph can be listed in incremental polynomial time using exponential space. The total running time of their algorithm is quadratic in the number of solutions and the existence of an algorithm whose complexity depends only linearly on the number of solutions remained open. We close this question by providing a polynomial delay algorithm to solve this problem which, moreover, uses polynomial space. Our algorithm relies on Proximity Search, a framework recently introduced by Conte and Uno (Stoc 2019) which has been shown powerful to obtain polynomial delay algorithms, but generally requires exponential space. In order to obtain a polynomial space algorithm for our problem, we introduce a new general method called /canonical path reconstruction/ to design polynomial delay and polynomial space algorithms based on Proximity Search.
  
  
  
• Jeudi 15 décembre 2022 (à 14h30): Aurélie Lagoutte (G-SCOP, Grenoble) : Algorithmes d'énumération de réparations de graphes
  
  Contrairement aux problèmes d'optimation combinatoire classiques, résoudre un problème d'énumération nécessite de lister toutes les solutions à un problème donné, et pas seulement la meilleure. Ce type d'algorithmes est nécessaire dans certaines applications, par exemple en bioinformatique ou en bases de données. Après avoir introduit les différentes manières de compter la complexité d'un algorithme d'énumération (on attend en général un nombre exponentiel de solutions, donc la complexité classique n'est pas adaptée), nous verrons quelques méthodes classiques de mises en oeuvre d'un algorithme d'énumération, en particulier la Flashlight Search et la Proximity Search. Nous mettrons en oeuvre cette dernière pour énumérer des "réparations" d'un graphe G quelconque donné en entrée, où réparations s'entend comme la suppression de sommets ou arrêtes jusqu'à ce que le graphe vérifie une propriété voulue (par exemple, être un cographe).
  
  
  
• Jeudi 8 décembre 2022 (à 14h30): Florent Tallerie (G-SCOP, Grenoble) : Une triangulation universelle pour les tores plats
  
  Un célèbre théorème de Nash, complété par Kuiper, implique que toute surface riemannienne lisse admet un plongement isométrique C^1 dans l'espace euclidien à trois dimensions E^3. Un résultat analogue dû à Burago et Zalgaller établit que toute surface polyédrique, c'est à dire obtenue en recollant des triangles euclidiens le long de leurs arêtes, admet un plongement isométrique linéaire par morceaux (ou PL) dans E^3. En particulier, cela fournit des plongements isométriques PL pour chaque tore plat (un quotient du plan euclidien E^2 par un réseau de rang 2). Cependant, la preuve de Burago et Zalgaller est partiellement constructive, s'appuyant en particulier sur le procédé de Nash-Kuiper. En pratique, leur construction produit des plongements PL avec un très grand nombre de faces, de plus distincts pour chaque tore plat. A partir d'une autre construction de Zalgaller et de travaux récents d'Arnoux, Lelièvre et Málaga, nous présentons une triangulation universelle du tore à moins de 6 000 faces, réalisant géométriquement de façon polyédrale n'importe quel tore plat.
  
  
  
• Jeudi 1er décembre 2022 (à 13h30): Carla Groenland (Utrecht, Pays-Bas) : List Colouring Trees in Logspace
  
  A List Colouring instance consists of a graph and for each vertex v in the graph, a list L(v) of colours that it may be coloured with. I will explain some ideas behind our algorithm that decides whether an n-vertex tree admits a list colouring using O(log n) bits on the work tape. No knowledge of parameterized complexity is expected, but I will also outline some new parameterized complexity classes (XNLP and XALP) that can be described via List Colouring via the graph width measures pathwidth and treewidth.
  
  This talk is primarily based on joint work with Hans Bodlaender and Hugo Jacob.
  
  
  
• Jeudi 24 novembre 2022 (à 14h30): Benjamin Bergougnoux (Varsovie, Pologne) : A logic-based algorithmic meta-theorem for mim-width
  
  We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MS01 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions. Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.
  
  This is a joint work with Jan Dreier and Lars Jaffke.
  
  
  
• Jeudi 10 novembre 2022 (à 15h): Bartosz Walczak (Cracovie, Pologne) : Coloring ordered graphs with excluded induced ordered subgraphs
  
  A class of graphs is chi-bounded if the chromatic number of the graphs in the class is bounded by some function of the clique number. The well-known Gyarfas–Sumner conjecture asserts that the class of H-free graphs (i.e., graphs excluding H as an induced subgraph) is chi-bounded if and only if H is acyclic. An analogous question can be asked for ordered graphs, i.e., graphs equipped with a total order on the vertices. Say that an ordered graph H is chi-bounding if the class of H-free ordered graphs (i.e., ordered graphs excluding H as an induced ordered subgraph) is chi-bounded. So which ordered graphs are chi-bounding?
  In joint work with Piotr Mikolajczyk, we prove that a connected ordered graph is chi-bounding if and only if it is a star, and we characterize the crossing-free ordered graphs that are chi-bounding. In joint work with Marcin Brianski and James Davies, we prove that every ordered matching is chi-bounding, which confirms a conjecture by Istvan Tomon.
  Coloring ordered graphs with excluded (induced) ordered subgraphs has been little explored so far. In this talk, I will introduce the audience to this topic (and, in particular, to the above-mentioned results) with a focus on missing cases that prevent us from stating or conjecturing a full characterization of chi-bounding ordered graphs.
  
  
  
• Jeudi 10 novembre 2022 (à 14h): Daniel Gonçalves (LIRMM, Montpellier) : On comparable box dimension
  
  Two boxes in R^d are comparable if one of them is a subset of a translation of the other. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in R^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.
  
  Joint work with Zdenek Dvorak, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt
  
  
  
• Jeudi 20 octobre 2022 (à 14h30): James Davies (Cambridge, UK) : Ringel's circle problem
  
  A constellation is a finite collection of circles in the plane in which no three circles are tangent at the same point. In 1959, Ringel asked how many colours are required to colour the circles of a constellation so that tangent circles receive different colours. We present a solution to Ringel's circle problem by constructing constellations that require arbitrarily many colours.
  
  Joint work with Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak.
  
  
  
• Jeudi 13 octobre 2022 (à 14h30): Marthe Bonamy (LaBRI, Bordeaux) : Exploring the space of colourings with Kempe changes
  
  Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?