Séminaires 2025 - 2026

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 H208 ou H202 ou C101. Le responsable est Moritz Mühlenthaler, n'hésitez pas à le contacter.

• Jeudi 22 janvier 2026 (14h30) : Etienne Moutot (Institut Fourier, Grenoble) : Pavages, dimères et diagrammes
  
  Dans cet exposé, je présenterai un modèle permettant de représenter des pavages comme des diagrammes. Ces diagrammes permettent de raisonner de manière purement graphique, en utilisant des règles de réécritures locales de graphes. L'exemple principal que j'utiliserai est celui des pavages par dimères (ou par des rectangles 2x1): dans ce cas, nous disposons d'un langage graphique permettant de compter le nombre exact de pavage par dimères de n'importe quel graphe, uniquement en ré-écrivant des diagrammes.   Ce langage nous permet d'obtenir un nouvel algorithme polynomial pour le comptage des couplages parfaits dans les graphes planaire. Ces travaux permettent également de créer un nouveau lien entre le ZW-calcul (un langage graphique pour le calcul quantique) et des problèmes de comptage beaucoup plus combinatoires.
  
  Exposé issu de travaux avec Titouan Carette, Marc de Visme, Vivien Ducros, Victor Lutfalla, Thomas Perez et Renaud Vilmart.
  
  
  
• Jeudi 15 janvier 2026 (14h30) : Tom McCormick (University of British Columbia, Vancouver, Canada) : Projecting Dual SFM Solutions for Max Flow Min Cut
  
  Motivated by an application to the quickest transshipment over time problem, we consider what dual solutions to the Submodular Function Minimization (SFM) LP look like when we project a given submodular function onto a subset of its elements. We mostly consider this problem specialized to the well-known submodular function given by cut capacity in a max flow network. We give characterizations and algorithms for determining if a given point is feasible, if it belongs to the base polytope, and if it is an optimal dual solution to SFM. Also, given a linear order on the subset, we show how to compute the corresponding Greedy vertex of the base polytope. Finally, we show how these results generalize to more general submodular functions when given an algorithmic oracle for minimization of the function translated by a vector.
  
  
  
• Mardi 6 janvier 2026 (14h30) : Clément Legrand-Duchesne (Jagiellonian University, Cracovie, Pologne) : Dirac’s theorem and the geometry of perfect matchings
  
  Dirac's theorem states that all n-vertex graphs with minimum degree n/2 contain a perfect matching. This is tight and graphs with minimum degree cn are more generally called c-Dirac graphs. In fact, a phase transition occurs at c=1/2: c-Dirac graphs with c <= 1/2 contain $(\frac{cn}{e+o(1)})^{n/2}$ perfect matchings [Cuckler, Kahn 2009]. Moreover, for any fixed c-Dirac graph G with c >= 1/2, there exist nice probability distributions on the perfect matchings of G called spread distributions [Pham, Sah, Sawhney, Simkin 2024]; as a result, if the edges of G are sampled with probability O(log(n)/n), the resulting graph still contains a perfect matching with good probability, thereby witnessing that these matchings are "everywhere" in G. With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of G, endowed with the graph metric such that  perfect matchings differing on at most k edges are at distance one. For any fixed k, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, has isolated perfect matchings, becomes connected, or becomes an expander.
  
  
  
• Jeudi 18 décembre 2025 (14h30) : Laure Morelle (Affiliation) : H-Planarity and Parametric Extensions: when Modulators Act Globally
  
  We introduce a series of graph decompositions based on the modulator/target scheme of modification problems. As such, we define H-Planarity as the problem of deciding whether a graph G contains a vertex set X such that the torso of X is planar and the connected components of G-X are in H. We prove that, if H is hereditary, CMSO-definable, and decidable in polynomial time, then H-Planarity is solvable in polynomial time. Additionally, we define two planar extensions of elimination distance to H and H-treewidth, namely H-planar treedepth and H-planar treewidth, for which we find FPT results under some mild conditions on H. All previous (meta) algorithmic studies on modulators deal with modulators of “low bidimensionality” in the sense that they cannot be spread along a grid-minor of the input graph. Our results are the first to handle the situation where the modulators act globally. For this, we introduce a new version of the “irrelevant vertex technique” that can deal with modulators that may act “everywhere” in the input graph.
  
  
  
• Jeudi 4 décembre 2025 (14h30) : Lucas Lorieau (LIMOS, Université Clermont Auvergne) : Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
  
  In the Geodetic Set problem, an input is a digraph G and integer k, and the objective is to decide whether there exists a vertex subset S of size k such that any vertex in V(G)\S lies on a shortest path between two vertices in S. In this talk, we focus our study of the problem on directed graphs and prove that Geodetic Set admits a polynomial-time algorithm on digraphs with possible 2-cycles when the underlying undirected graph is a tree (after deleting possible parallel edges). This positive result naturally leads us to investigate cases where the underlying undirected graph is `close to a tree'. Towards this, we show that Geodetic Set on digraphs without 2-cycles and whose underlying undirected graph has feedback edge set number fen , can be solved in time 2^O(fen) n^O(1), where n is the number of vertices. To complement this, we prove that the problem remains NP-hard on DAGs (which do not contain 2-cycles) even when the underlying undirected graph has constant feedback vertex set number. Our last result significantly strengthens the state of the art hardness results, stating that the problem is NP-hard on DAGs when the underlying undirected graph is either bipartite, cobipartite or split.
  
  
  
• Lundi 16 septembre 2025 (14h30) : William Cook (University of Waterloo) : TSP Cut Separation
  
  Cutting-plane methods have been used to solve large-scale instances of the traveling salesman problem. The key step requires algorithms for finding linear inequalities valid for all tours, but violated by the solution to the current linear-programming relaxation. This is known as the cut-separation problem. We discuss recent work in TSP cut separation that permitted earlier this year the computation of an optimal 81,998-stop tour using point-to-point walking distances obtained with the Open Source Routing Machine (OSRM). The focus of the talk will be on research questions that could drive further improvements in cutting-plane methods for the TSP and related discrete optimization models.