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 6 juillet 2023 (à 14h30): Francis Lazarus (G-SCOP, Grenoble) :
  
  
  
  
  
• Jeudi 29 juin 2023 (à 14h30): Diana Sasaki (Universidade Estadual do Rio de Janeiro) :
  
  
  
  
  
• Jeudi 22 juin 2023 (à 14h30): Alp Müyesser (University College London) : Perfect matchings in groups
  
  When can we find perfect matchings in hypergraphs whose vertices represent group elements and edges represent solutions to systems of linear equations? There are many problems expressible in this language, including the n-queens problem, the Hall-Paige conjecture, and the Graham-Sloane tree-labelling conjecture. Despite the apparent similarity of all these problems, until recently, they have been approached in completely different ways, using algebraic tools ranging from the combinatorial Nullstellensatz to Fourier analysis. In this talk, we present a unified approach coming from probabilistic combinatorics which has recently led to a resolution of many old problems in the area.
  
  
  
• Jeudi 15 juin 2023 (à 14h30): Frédéric Meunier (CERMICS, Marne-La-Vallée) : Coloring complements of line graphs
  
  A first objective of this talk is to show that complements of line graphs enjoy nice coloring properties. For instance, all complements of line graphs have their local chromatic number equal to their (usual) chromatic number. There is also an elementary sufficient condition for their chromatic number to be equal to a natural upper bound, with various consequences such as a complete characterization of all induced subgraphs of the Kneser graph KG(n, 2) that have a chromatic number equal to its chromatic number, namely n − 2. A second objective is to take this topic as an opportunity to discuss the limits of the topological method. This latter is especially suitable for the study of coloring properties of complements of line graphs. Nevertheless, there are clues showing that most of our results cannot be obtained by the topological method.
  
  Joint work with Hamid Reza Danehspajouh and Guilhem Mizrahi.
  
  
  
• Mardi 13 juin 2023 (à 14h): Felix Klingelhöfer (G-SCOP, Grenoble) : Coloring tournaments with few colors: Algorithms and complexity
  
  A k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds.
  We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.
  
  This is joint work with Alantha Newman.
  
  
  
• Jeudi 8 juin 2023 (à 15h): Mark Siggers (Kyungpook National University, South Korea) : Dismantlability and shortest path reconfiguration
  
  In 2000 Brightwell and Winkler showed that dismantlable (or cop-win) graphs are exactly the hom-trivial graphs H: graphs H such that the Hom-graph Hom(G,H) is connected for all graphs G. We prove a relative version of this. A graph H is relative-hom-trivial if the relative Hom-graph Hom(G,H;p) is connected for every H-pre-colouring p of a graph G. We show that a graph is relative-hom-trivial if it is NU. For context, we discuss a hierarchy of dismantlability properties, among which are the property of being NU.
  
  We then look at this result in the context of combinatorial reconfiguration. As the H-recolouring problem is trivial if and only if H is dismantlable, the H-extension-reconfiguration problem is trivial if and only if H is everywhere dismantlable. Using our result we show that the shortest path reconfiguration problem if trivial for any graph that can be made NU by adding loops. This generalises several recent results about shortest path reconfiguration.
  
  
  
• Jeudi 8 juin 2023 (à 14h): Anna Gujgiczer (Budapest University of Techology and Economics) : Circular chromatic number of generalised Mycielski graphs on odd cycles and other quadrangulations of the projective plane
  
  Generalised Mycielskians of odd cycles are relatively small graphs with high odd girth and chromatic number 4. In the literature there are many proofs using different techniques, like methods from algebraic topology, to show the second property. It is also proven by DeVos et al that these graphs have circular chromatic number 4. Using a result from about the same time of Simonyi and Tardos, namely that for a "topologically t-chromatic" graph $G$, where $t$ is even we have $\chi_c(G) = \chi(G) = t$, one can also get this strengthened statement.
  In this talk we present a new, relatively short direct proof for the circular chromatic number, using only a basic notion of algebraic topology, namely the winding number. Then we present another graph family with high odd girth and circular chromatic number 4. This construction is very similar to the generalised Mycielski, but on its first two layers it forms a M$\ddot{o}$bius ladder. We prove the statement about their circular chromatic number with similar techniques. Moreover we present a similar result for a family of signed graphs.
  
  This talk is based on a joint work with Reza Naserasr (Université de Paris, IRIF, CNRS, F-75006, Paris, France), Rohini S (Indian Institute of Technology Madras, India) and S Taruni (Indian Institute of Technology Dharwad, India).
  
  
  
• Mardi 6 juin 2023 (à 14h): Florian Hörsch (CISPA, Saarbrücken) : Decompositions into linear forests
  
  A linear forest is a graph each of whose connected components is a path. For some k, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,l)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests F_k,F_l where F_k is k-bounded and F_l is l-bounded.
  We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and l are at least 2, NP-complete if k>=2 and l=1, and is in P for (k,l)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984.
  We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs.
  
  This is joint work with Rutger Campbell and Benjamin Moore.
  
  
  
• Jeudi 11 mai 2023 (à 14h30): Oscar Defrain (LIS, Marseille) : Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree
  
  At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an n^{O(d)}-delay algorithm listing all minimal transversals of an n-vertex hypergraph of degeneracy d, for an appropriate definition of degeneracy. Recently at IWOCA 2019, Conte, Kanté, Marino, and Uno asked whether, even for a more restrictive notion of degeneracy, this XP-delay algorithm parameterized by d could be improved to an FPT-delay algorithm parameterized by d and the maximum degree ∆, i.e., an algorithm with delay f (d, ∆) · n^{O(1)} for some computable function f. We answer this question in the affirmative whenever the hypergraph corresponds to the closed neighborhoods of a given graph, i.e., we show that the intimately related problem of enumerating minimal dominating sets in graphs can be solved with FPT-delay parameterized by the degeneracy and the maximum degree.
  
  Joint work with Valentin Bartier and Fionn Mc Inerney.
  
  
  
• Jeudi 4 mai 2023 (à 14h30): Marthe Bonamy (LaBRI, Bordeaux) : Separating edges with few paths
  
  A path separates an edge from another if it contains the former and not the latter. How many paths do we need to separate any edge from any other in an arbitrary graph? This question is in line with the general study of separating systems initiated by Rényi in 1961. We discuss the tools involved in obtaining bounds that are tight up to a constant factor, as well as other related questions.
  
  
  
• Jeudi 27 avril 2023 (à 14h30): Florian 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 18 avril 2023 (à 14h45): Kristóf Bérczi (Eötvös Loránd University, Budapest) : Supermodularity in unweighted graph optimization: Algorithms
  
  In this talk, we present a min-max theorem on covering a supermodular function by a simple degree constrained bipartite graph. A specific feature of the result is that its minimum cost extension is already NP-hard, therefore classic polyhedral tools themselves definitely cannot be sufficient for solving the problem. We also develop a simple algorithm for determining a minimum covering that can be applied for a wide list of problems, for example, to compute k disjoint branchings B_1,...,B_k in a digraph with sizes mu_1,...,mu_k, or to determine an optimal solution to the matroidal degree-constrained augmentation version of the maximum term rank problem.
  
  Joint work with András Frank.
  
  
  
• Jeudi 18 avril 2023 (à 14h): Tamás Schwarcz (Eötvös Loránd University, Budapest) : Reconfiguration of the union of arborescences
  
  Given a digraph D, a root r and a fixed positive integer k, let us call a subset of arcs feasible, if it is the union of k arc-disjoint r-arborescences. We show that for any two feasible arc sets S and T, there exists a sequence T_0, T_1, ..., T_l such that T_0 = S, T_l = T, each T_i is feasible and |T_{i-1}-T_i| = |T_i-T_{i-1}| = 1 for each i.
  
  Based on joint work with Yusuke Kobayashi and Ryoga Mahara.
  
  
  
• 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?